Largest empty rectangle

The case when the sought rectangle is an axis-oriented square may be treated using Voronoi diagrams in

metrics for the corresponding obstacle set, similarly to the largest empty circle problem.

In particular, for the case of points within rectangle an optimal algorithm of time complexity

[8] A problem first discussed by Naamad, Lee and Hsu in 1983[1] is stated as follows: given a rectangle A containing n points, find a largest-area rectangle with sides parallel to those of A which lies within A and does not contain any of the given points.

Naamad, Lee and Hsu presented an algorithm of time complexity

and gave an example in which s is quadratic in n. Afterwards a number of papers presented better algorithms for the problem.

[10] Later a more general problem of empty isothetic rectangles among non-isothetic obstacles was considered.

Maximum Empty Rectangles (in green) with different bounding objects (with black outline) . The light green rectangle would be suboptimal (non-maximal) solution. A-C are axis oriented - parallel to axes of the light blue "floor" and also examples of. [ 1 ] E shows a maximal empty rectangle with arbitrary orientation