Technical Reports

The ICICS/CS Reading Room

UBC CS TR-94-28 Summary

Computing the largest inscribed isothetic rectangle, December 1994 Helmut Alt, David Hsu and Jack Snoeyink, 6 pages

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.

If you have any questions or comments regarding this page please send mail to