Computing the largest inscribed isothetic rectangle
Freie Universit?at Berlin
University of British Columbia
University of British Columbia
This paper describes an algorithm to compute, in ?(log n) time, a rectangle that is contained in a convex n-gon, has sides parallel to the coordinate axes, and has maximum area. With a slight modification it will compute the smallest perimeter. The algorithm uses a tentative prune-and-search approach, even though this problem does not appear to fit into the functional framework of Kirkpatrick and Snoeyink.
In this paper, we give a logarithmic-time solution to the following problem: Given the list vertices of a convex polygon P in counterclockwise (ccw) order, stored in an array or balanced binary search tree, compute the rectangle R ae P with maximum area (or maximum perimeter) whose sides are parallel to the x and y coordinate axes.
Fischer and H?offgen  solved the maximum area problem by a nested binary search in O(log2 n) time. To obtain a ?(log n) algorithm, we characterize the maximum rectangles, then use the tentative pruneand-search technique of Kirkpatrick and Snoeyink . In some cases we are able to frame the search for a rectangle as a problem of computing a fixed-point and apply a theorem of ; in others we must use tentative prune-and-search directly.
In general, the prune-and-search technique for multiple lists looks at local information in O(1) time to discard a fraction of some list. Tentative prune-and-search can sometimes be used when local information is insufficient to determine which fraction to discard. This technique makes tentative decisions that are later be certified or revoked.
Suppose that P is in general position: no two vertices on the same vertical or horizontal line and no two boundary edges parallel. (This can be simulated by perturbation methods if necessary .) We can decompose @P , the boundary of P , into four pieces by breaking at the horizontally and vertically extreme points. We name the pieces A, B, C, and D in counterclockwise order, starting from the southwest.
If a rectangle R ae P has only one corner on @P , or has only two corners from the same side of R on @P , then one can enlarge R by translating a side (figure 1a). Therefore a rectangle R with maximum area or perimeter either has two diagonally opposite corners, a and c, on @P , or has three corners a, b, and c, on @P . These two cases are illustrated in figure 1b and 1c, and characterized in the next two lemmas. We denote the slope of a line segment ac by mac.
Lemma 1 Suppose that the maximum area or perimeter rectangle R ae P has exactly two corners on @P , namely a 2 A and c 2 C. Then P has parallel tangents at a and c with slope m, where m = 1 in the perimeter case and m = ?mac in the area case.
Proof : Fix a at the origin, and consider the curve where c = (x; y) can lie for the rectangle with diagonal ac to have perimeter or area F . In the perimeter case x + y = ?F=2 is a diamond with sides of slope 1 and ?1. In the area case xy = ?F is a hyperbola.
?Supported in part by an NSERC Research Grant and a B.C. Advanced Systems Institute Fellowship.