Computing the largest inscribed isothetic rectangle
Helmut Alt, David Hsu, Jack Scott Snoeyink · 1994
This paper describes an algorithm to compute, in \\Theta(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 Hoffgen [2] solved the maximum area problem by a nested binary search in O(log 2 n) time. To obtain a \\Theta(log n) algorithm, we characterize the maximum rectangles, then use the tentative pruneand -search technique of...