The Largest Empty Rectangle problem is defined as the following:
Given a rectangle and points inside it, compute the largest axis parallel
subrectangle that lies within the rectangle
and contains no points in its interior.
Although the paper on which we base the implementation does not deal with
degeneracies (two or more points
which have the same X or Y value), we made some modification to handle
them.
An implementation of the algorithm to compute the largest empty rectangle
has been added to the CGAL distribution.
Links
-
M. Orlowski,
A new algorithm for the largest empty rectangle,
Algorithmica, volume 5, 1990, pages 65-73.
Contact
| Eli Packer
|
|
|
![[Projects Page]](../images/icons/projects.gif)
![[Top]](../images/icons/top.gif)
Site is maintained by
Efi Fogel.
Last modified: June 01 2004.
