Personal tools
You are here: Home → Projects → In-house Projects → Largest Empty Rectangle
« October 2021 »
October
SuMoTuWeThFrSa
12
3456789
10111213141516
17181920212223
24252627282930
31
Log in


Forgot your password?
 

Largest Empty Rectangle

Largest Empty Rectangle
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,  5: 65-73, 1990 [link]

Contact

Eli Packer http://www.math.tau.ac.il/~elip elip@post.tau.ac.il
Document Actions