Maximum-Area Rectangles in a Simple Polygon

Authors Yujin Choi, Seungjun Lee, Hee-Kap Ahn



PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2019.12.pdf
  • Filesize: 0.64 MB
  • 14 pages

Document Identifiers

Author Details

Yujin Choi
  • Technische Universität Berlin, Germany
Seungjun Lee
  • Pohang University of Science and Technology, Pohang, Korea
Hee-Kap Ahn
  • Pohang University of Science and Technology, Pohang, Korea

Acknowledgements

This research was supported by the MSIT (Ministry of Science and ICT), Korea, under the SW Starlab support program (IITP-2017-0-00905) supervised by the IITP (Institute for Information & communications Technology Promotion).

Cite AsGet BibTex

Yujin Choi, Seungjun Lee, and Hee-Kap Ahn. Maximum-Area Rectangles in a Simple Polygon. In 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 150, pp. 12:1-12:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.FSTTCS.2019.12

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
Keywords
  • Maximum-area rectangle
  • largest rectangle
  • simple polygon

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Alok Aggarwal and Joel Martin Wein. Computational Geometry Lecture Notes for MIT, 1988. Google Scholar
  2. Helmut Alt, David Hsu, and Jack Snoeyink. Computing the Largest Inscribed Isothetic Rectangle. In Proceedings of 7th Canadian Conference on Computational Geometry (CCCG 1995), pages 67-72. University of British Columbia, 1995. Google Scholar
  3. Nina Amenta. Bounded Boxes, Hausdorff Distance, and a New Proof of an Interesting Helly-type Theorem. In Proceedings of 10th Annual Symposium on Computational Geometry (SoCG 1994), pages 340-347, 1994. Google Scholar
  4. Sang Won Bae, Chunseok Lee, Hee-Kap Ahn, Sunghee Choi, and Kyung-Yong Chwa. Computing minimum-area rectilinear convex hull and L-shape. Computational Geometry, 42(9):903-912, 2009. Google Scholar
  5. Ralph P. Boland and Jorge Urrutia. Finding the Largest Axis-Aligned Rectangle in a Polygon in O(nlog n) time. In Proceedings of 13th Canadian Conference on Computational Geometry (CCCG 2001), pages 41-44, 2001. Google Scholar
  6. Sergio Cabello, Otfried Cheong, Christian Knauer, and Lena Schlipf. Finding largest rectangles in convex polygons. Computational Geometry, 51:67-74, 2016. Google Scholar
  7. Danny Z. Chen and Haitao Wang. Visibility and ray shooting queries in polygonal domains. Computational Geometry, 48(2):31-41, 2015. Google Scholar
  8. Karen Daniels, Victor Milenkovic, and Dan Roth. Finding the largest area axis-parallel rectangle in a polygon. Computational Geometry, 7(1):125-148, 1997. Google Scholar
  9. Paul Fischer and Klaus-Uwe Höffgen. Computing a maximum axis-aligned rectangle in a convex polygon. Information Processing Letters, 51(4):189-193, 1994. Google Scholar
  10. Partha P. Goswami, Sandip Das, and Subhas C. Nandy. Triangular range counting query in 2D and its application in finding k nearest neighbors of a line segment. Computational Geometry, 29(3):163-175, 2004. Google Scholar
  11. Olaf Hall-Holt, Matthew J. Katz, Piyush Kumar, Joseph S. B. Mitchell, and Arik Sityon. Finding Large Sticks and Potatoes in Polygons. In Proceedings of 17th Annual ACM-SIAM Symposium on Discrete Algorithm (SODA 2016), pages 474-483, 2006. Google Scholar
  12. Christian Knauer, Lena Schlipf, Jens M. Schmidt, and Hans Raj Tiwary. Largest inscribed rectangles in convex polygons. Journal of Discrete Algorithms, 13:78-85, 2012. Google Scholar
  13. Michael McKenna, Joseph O'Rourke, and Subhash Suri. Finding the largest rectangle in an orthogonal polygon. In Proceedings of 23rd Allerton Conference on Communication, Control and Computing, pages 486-495, 1985. Google Scholar
  14. Derick Wood and Chee K. Yap. The orthogonal convex skull problem. Discrete & Computational Geometry, 3(4):349-365, 1988. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail