Largest rectangle within a given rectangle with holes

Question

You are given a rectangle of length 'L' and breadth 'B'. Consider the rectangle to be a grid containing LxB cells. You are also given the positions of those cells which are to be considered as holes.

The task is to find the largest rectangle within this given rectangle such that this rectangle contains no holes.

I know I can do this using brute force, but that will take too much time. Is there any other faster algorithm?

PS: "largest rectangle" means rectangle having maximum area.

Answer 1

Here's an alternate method:-

create list of rectangles
add one rectangle, size LxB
for each hole
  get rectangles containing hole
  remove rectangles from list
  for each rectangle
    create 0-4 child rectangles
    add child rectangles to list
find largest rectangle in list

To create the child rectangles:-

|-------|   parent rectangle with hole under consideration (x)
|       |
|  x    |
|       |
|-------|

Create four child rectangles thus:-

|-|-----|   
|.|     |
|.|x    |
|.|     |
|-|-----|

|---|---|   
|   |...|
|  x|...|
|   |...|
|---|---|

|-------|   
|-------|
|  x    |
|       |
|-------|

|-------|   
|       |
|  x    |
|-------|
|-------|

If the hole is adjacent to an edge, the child will have zero width or height and so it doesn't get added into the list.

Don't know why this was down voted. Anyway, here's an implementation in C#:-

    using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    using System.Drawing;
    using System.Diagnostics;

    namespace LargestRectangle
    {
        class Program
        {
            static Rectangle FindLargestRectangle(Rectangle bounds, List<Point> holes)
            {
                LinkedList<Rectangle>
                    rectangles = new LinkedList<Rectangle>();

                rectangles.AddLast(bounds);

                foreach (Point hole in holes)
                {
                    for (LinkedListNode<Rectangle> rect = rectangles.First, next=null; rect != null; rect = next)
                    {
                        next = rect.Next;

                        if (rect.Value.Contains(hole))
                        {
                            rectangles.Remove(rect);

                            if (rect.Value.Left < hole.X)
                            {
                                rectangles.AddFirst(new Rectangle(rect.Value.Left, rect.Value.Top, hole.X - rect.Value.Left, rect.Value.Height));
                            }

                            if (rect.Value.Right - 1 > hole.X)
                            {
                                rectangles.AddFirst(new Rectangle(hole.X + 1, rect.Value.Top, rect.Value.Right - hole.X - 1, rect.Value.Height));
                            }

                            if (rect.Value.Top < hole.Y)
                            {
                                rectangles.AddFirst(new Rectangle(rect.Value.Left, rect.Value.Top, rect.Value.Width, hole.Y - rect.Value.Top));
                            }

                            if (rect.Value.Bottom - 1 > hole.Y)
                            {
                                rectangles.AddFirst(new Rectangle(rect.Value.Left, hole.Y + 1, rect.Value.Width, rect.Value.Bottom - hole.Y - 1));
                            }
                        }
                    }
                }

                Rectangle
                    largest = new Rectangle(0, 0, 0, 0);

                int
                    max_area = 0;

                foreach (Rectangle rect in rectangles)
                {
                    int
                        area = rect.Width * rect.Height;

                    if (area > max_area)
                    {
                        largest = rect;
                        max_area = area;
                    }
                }

                return largest;
            }

            static void Main(string[] args)
            {
                int
                    max_holes = 100,
                    size = 50;

                Rectangle
                    bounds = new Rectangle(0, 0, size, size);

                List<Point>
                    holes = new List <Point> ();

                Random
                    random = new Random ();

                for (int i = 0; i < max_holes; ++i)
                {
                    holes.Add(new Point(random.Next(size), random.Next(size)));
                }

                List<string>
                    area = new List<String>();

                for (int i = 0; i < size; ++i)
                {
                    area.Add(new String('.', size));
                }

                foreach (Point p in holes)
                {
                    area[p.Y] = area[p.Y].Substring(0, p.X) + '*' + area[p.Y].Substring(p.X + 1);
                }

                Console.WriteLine("Map:-");
                Console.WriteLine("");
                foreach (string s in area)
                {
                    Console.WriteLine(s);
                }

                Stopwatch
                    execution_time = new Stopwatch();

                execution_time.Start();

                Rectangle
                    largest_rect = FindLargestRectangle(bounds, holes);

                execution_time.Stop();

                for (int y = largest_rect.Top; y < largest_rect.Bottom; ++y)
                {
                    area[y] = area[y].Substring(0, largest_rect.Left) + new string('#', largest_rect.Width) + area[y].Substring(largest_rect.Right);                        string
                }

                Console.WriteLine("");
                Console.WriteLine("Map:-");
                Console.WriteLine("");
                foreach (string s in area)
                {
                    Console.WriteLine(s);
                }

                Console.WriteLine("");
                Console.WriteLine("Largest rectangle: (" + largest_rect.Left + "," + largest_rect.Top + ")-(" + (largest_rect.Right - 1) + "," + (largest_rect.Bottom - 1) + ")");
                Console.WriteLine("Execution time = " + execution_time.ElapsedMilliseconds);
            }
        }
    }

Built using DevStudio 2008.

On my machine, it takes 59ms to do the 100 holes in a 50x50 grid. I originally used List<Rectangle> instead of LinkedList<Rectangle> but that took over 1000ms!

Answer 2

Here's a DP based approach.. Not necessarily better than the one in the paper, but definitely simpler to understand.

Make a memoization table where x and y values correspond to end points of cells. Fill in the table like so..

dp[x][y] = max( increment_x( dp[x-1][y] ),

             increment_y( dp[x][y-1] ) ;

The increment function will not increment if incrementing the coordinates adds a hole as in (d)...and simply return max( x- , y-).

Note: When incrementing, causes complete engulfing of a hole as in e) .. Two rectangle may need to be compared, the one before the hole and the one after the hole, and on tie the one with more freedom may be kept..

You could also optimize by only taking steps of 'valid lattice points' rather than every lattice point..

This is a raw idea and probably has flaws. Do point :)

Answer 3

Divide and conquer approach is described here http://www.cs.princeton.edu/~chazelle/pubs/ComputLargestEmptyRectangle.pdf

Answer 4

You could try a scan-line approach.

First initialize a list with the positions and sizes of possible starting positions on one edge of your parent rectangle. Now you will save all possible rectangles for now which will have the following attributes: start, end, width. With width beeing 0 in the beginning.

Now you iterate and in every step you check the following things:

• check for all current, active rectangles if they are still possible, if yes update their width. if not do the following things:
  • duplicate the current rectagle and mark one as inactive. The other one will get reduced so it fits again. It gets updted the following way: start = (currentHoleStart - start < end - currentHoleEnd) ? currentHoleStart : start and same for the end
  • check for new possible rectangles and add them to the active list

In the end just check the list of rectangles for the largest. If you're very limited on memory you could improve the solution by just keeping the largest inactive rectangle

A little representation of the algorithm, where x denotes a hole:

-----
|x   |
|    |
-----

initial:

1,2,0, active

step 1:

1,2,1 active
0,1,0 active

step 2:

1,2,2 inactive
0,1,1 inactive