Key points are not available for this paper at this time.
We consider the following problem: Given a rectangle containing N points, find the largest area subrectangle with sides parallel to those of the original rectangle which contains none of the given points. If the rectangle is a piece of fabric or sheet metal and the points are flaws, this problem is finding the largest-area rectangular piece which can be salvaged. A previously known result 13 takes O (N²) worst-case and O (N ² N) expected time. This paper presents an O (N ³ N) time, O (N N) space algorithm to solve this problem. It uses a divide-and-conquer approach similar to the ones used by Bentley 1 and introduces a new notion of Voronoi diagram along with a method for efficient computation of certain functions over paths of a tree.
Chazelle et al. (Sat,) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: