Computing the largest inscribed isothetic rectangle

Helmut Alt
Freie Universit?at Berlin
David Hsu
University of British Columbia
Jack Snoeyink?

University of British Columbia

Abstract
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.

1 Introduction

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 [2] 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 [4]. 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 [4]; 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 [1].) 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.