DROPS

Document

DOI: 10.4230/LIPIcs.FSTTCS.2021.19

Largest Similar Copies of Convex Polygons in Polygonal Domains

Authors: Taekang Eom, Seungjun Lee, and Hee-Kap Ahn

Published in: LIPIcs, Volume 213, 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)

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.

Cite as

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)

Copy BibTex To Clipboard

@InProceedings{eom_et_al:LIPIcs.FSTTCS.2021.19,
  author =	{Eom, Taekang and Lee, Seungjun and Ahn, Hee-Kap},
  title =	{{Largest Similar Copies of Convex Polygons in Polygonal Domains}},
  booktitle =	{41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)},
  pages =	{19:1--19:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-215-0},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{213},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Chekuri, Chandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2021.19},
  URN =		{urn:nbn:de:0030-drops-155300},
  doi =		{10.4230/LIPIcs.FSTTCS.2021.19},
  annote =	{Keywords: Polygon placement, Largest similar copy, Polygonal domain}
}

Search Results

Documents authored by Eom, Taekang

Largest Similar Copies of Convex Polygons in Polygonal Domains

Abstract

Cite as

Thanks for your feedback!

Could not send message