Document Open Access Logo

Largest Similar Copies of Convex Polygons in Polygonal Domains

Authors Taekang Eom, Seungjun Lee, Hee-Kap Ahn

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2021.19.pdf
  • Filesize: 0.96 MB
  • 13 pages

Document Identifiers

Author Details

Taekang Eom
  • Department of Computer Science and Engineering, Pohang University of Science and Technology, South Korea
Seungjun Lee
  • Department of Computer Science and Engineering, Pohang University of Science and Technology, South Korea
Hee-Kap Ahn
  • Department of Computer Science and Engineering, Graduate School of Artificial Intelligence, Pohang University of Science and Technology, South Korea

Funding

This research was partly supported by the Institute of Information & communications Technology Planning & Evaluation(IITP) grant funded by the Korea government(MSIT) (No. 2017-0-00905, Software Star Lab (Optimal Data Structure and Algorithmic Applications in Dynamic Geometric Environment)) and (No. 2019-0-01906, Artificial Intelligence Graduate School Program(POSTECH)).

Cite As Get BibTex

Taekang Eom, Seungjun Lee, and Hee-Kap Ahn. Largest Similar Copies of Convex Polygons in Polygonal Domains. In 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 213, pp. 19:1-19:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.FSTTCS.2021.19

Abstract

Given a convex polygon with k vertices and a polygonal domain consisting of polygonal obstacles with n vertices in total in the plane, we study the optimization problem of finding a largest similar copy of the polygon that can be placed in the polygonal domain without intersecting the obstacles. We present an upper bound O(k²n²λ₄(k)) on the number of combinatorial changes occurred to the underlying structure during the rotation of the polygon, together with an O(k²n²λ₄(k)log n)-time deterministic algorithm for the problem. This improves upon the previously best known results by Chew and Kedem [SoCG89, CGTA93] and Sharir and Toledo [SoCG91, CGTA94] on the problem in more than 27 years. Our result also improves the time complexity of the high-clearance motion planning algorithm by Chew and Kedem.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
Keywords
  • Polygon placement
  • Largest similar copy
  • Polygonal domain

Metrics

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

Related Versions

References

  1. Pankaj K. Agarwal, Nina Amenta, and Micha Sharir. Largest placement of one convex polygon inside another. Discrete & Computational Geometry, 19(1):95-104, 1998. Google Scholar
  2. Pankaj K. Agarwal, Boris Aronov, and Micha Sharir. Motion planning for a convex polygon in a polygonal environment. Discrete & Computational Geometry, 22(2):201-221, 1999. Google Scholar
  3. Pankaj K. Agarwal, Haim Kaplan, and Natan Rubin. Kinetic Voronoi diagrams and Delaunay triangulations under polygonal distance functions. Discrete & Computational Geometry, 54:871-904, 2015. Google Scholar
  4. Mikhail J. Atallah. Dynamic computational geometry. In Proceedings of the 24th Annual Symposium on Foundations of Computer Science (FOCS 1983), pages 92-99. IEEE, 1983. Google Scholar
  5. Francis Avnaim and Jean Daniel Boissonnat. Polygon placement under translation and rotation. In Robert Cori and Martin Wirsing, editors, STACS 88, pages 322-333, 1988. Google Scholar
  6. Sang Won Bae and Sang Duk Yoon. Empty squares in arbitrary orientation among points. In Proceedings of the 36th International Symposium on Computational Geometry (SoCG 2020). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020. Google Scholar
  7. Bernard Chazelle. The polygon containment problem. In F.P. Preparata, editor, Advances in Computing Research, Vol I: Computational Geometry, pages 1-33. JAI Press Inc., 1983. Google Scholar
  8. L Paul Chew and Klara Kedem. Placing the largest similar copy of a convex polygon among polygonal obstacles. In Proceedings of the 5th Annual Symposium on Computational Geometry (SoCG 1989), pages 167-173, 1989. Google Scholar
  9. L Paul Chew and Klara Kedem. A convex polygon among polygonal obstacles: Placement and high-clearance motion. Computational Geometry, 3(2):59-89, 1993. Google Scholar
  10. Rudolf Fleischer, Kurt Mehlhorn, Günter Rote, Emo Welzl, and Chee Yap. Simultaneous inner and outer approximation of shapes. Algorithmica, 8(1):365, 1992. Google Scholar
  11. Steven Fortune. A fast algorithm for polygon containment by translation. In Proceedings of the 12th International Colloquium on Automata, Languages, and Programming (ICALP 1985), pages 189-198, 1985. Google Scholar
  12. Jacob E. Goodman, Joseph O'Rourke, and Csaba D. Tóth, editors. Handbook of Discrete and Computational Geometry. CRC Press LLC, 3rd edition, 2017. Google Scholar
  13. Klara Kedem and Micha Sharir. An efficient motion-planning algorithm for a convex polygonal object in two-dimensional polygonal space. Discrete & Computational Geometry, 5:43-75, 1990. Google Scholar
  14. Seungjun Lee, Taekang Eom, and Hee-Kap Ahn. Largest triangles in a polygon. Computational Geometry, 98:101792, 2021. Google Scholar
  15. Daniel Leven and Micha Sharir. Planning a purely translational motion for a convex object in two-dimensional space using generalized Voronoi diagrams. Discrete & Computational Geometry, 2:9-31, 1987. Google Scholar
  16. Nimrod Megiddo. Applying parallel computation algorithms in the design of serial algorithms. Journal of the ACM, 30(4):852-865, 1983. Google Scholar
  17. Colm Ó'Dúnlaing and Chee K Yap. A retraction method for planning the motion of a disc. Journal of Algorithms, 6(1):104-111, 1985. Google Scholar
  18. Natan Rubin. On kinetic Delaunay triangulations: A near quadratic bound for unit speed motions. Journal of the ACM, 62(3):25:1-25:85, 2015. Google Scholar
  19. Micha Sharir and Sivan Toledo. Extremal polygon containment problems. Computational Geometry, 4(2):99-118, 1994. Google Scholar
  20. Endre Szemerédi. On a problem by Davenport and Schinzel. Acta Arithmetica, 25:213-224, 1974. Google Scholar
  21. Sivan Toledo. Extremal polygon containment problems. In Proceedings of the 7th Annual Symposium on Computational Geometry (SoCG 1991), pages 176-185, 1991. 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
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact