1 Search Results for "Eom, Taekang"

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-dev.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}
}
  • Refine by Author
  • 1 Ahn, Hee-Kap
  • 1 Eom, Taekang
  • 1 Lee, Seungjun

  • Refine by Classification
  • 1 Theory of computation → Computational geometry

  • Refine by Keyword
  • 1 Largest similar copy
  • 1 Polygon placement
  • 1 Polygonal domain

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2021

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 Imprint Privacy Contact