Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2019.12
URN: urn:nbn:de:0030-drops-115745
URL: https://drops.dagstuhl.de/opus/volltexte/2019/11574/
Choi, Yujin ; Lee, Seungjun ; Ahn, Hee-Kap
Maximum-Area Rectangles in a Simple Polygon
| pdf-format: |
|
Abstract
We study the problem of finding maximum-area rectangles contained in a polygon in the plane. There has been a fair amount of work for this problem when the rectangles have to be axis-aligned or when the polygon is convex. We consider this problem in a simple polygon with n vertices, possibly with holes, and with no restriction on the orientation of the rectangles. We present an algorithm that computes a maximum-area rectangle in O(n^3 log n) time using O(kn^2) space, where k is the number of reflex vertices of P. Our algorithm can report all maximum-area rectangles in the same time using O(n^3) space. We also present a simple algorithm that finds a maximum-area rectangle contained in a convex polygon with n vertices in O(n^3) time using O(n) space.
BibTeX - Entry
@InProceedings{choi_et_al:LIPIcs:2019:11574,
author = {Yujin Choi and Seungjun Lee and Hee-Kap Ahn},
title = {{Maximum-Area Rectangles in a Simple Polygon}},
booktitle = {39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)},
pages = {12:1--12:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-131-3},
ISSN = {1868-8969},
year = {2019},
volume = {150},
editor = {Arkadev Chattopadhyay and Paul Gastin},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2019/11574},
URN = {urn:nbn:de:0030-drops-115745},
doi = {10.4230/LIPIcs.FSTTCS.2019.12},
annote = {Keywords: Maximum-area rectangle, largest rectangle, simple polygon}
}
| Keywords: | Maximum-area rectangle, largest rectangle, simple polygon | |
| Seminar: | 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019) | |
| Issue date: | 2019 | |
| Date of publication: | 04.12.2019 |
