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.
Divide and conquer approach is described here http://www.cs.princeton.edu/~chazelle/pubs/ComputLargestEmptyRectangle.pdf
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 :)
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:
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
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!
