Search Results

Documents authored by Hair, Isaac M.

Document
DOI: 10.4230/LIPIcs.SoCG.2024.34
Convex Polygon Containment: Improving Quadratic to Near Linear Time

Authors: Timothy M. Chan and Isaac M. Hair

Published in: LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)

Abstract
We revisit a standard polygon containment problem: given a convex k-gon P and a convex n-gon Q in the plane, find a placement of P inside Q under translation and rotation (if it exists), or more generally, find the largest copy of P inside Q under translation, rotation, and scaling. Previous algorithms by Chazelle (1983), Sharir and Toledo (1994), and Agarwal, Amenta, and Sharir (1998) all required Ω(n²) time, even in the simplest k = 3 case. We present a significantly faster new algorithm for k = 3 achieving O(n polylog n) running time. Moreover, we extend the result for general k, achieving O(k^O(1/ε) n^{1+ε}) running time for any ε > 0. Along the way, we also prove a new O(k^O(1) n polylog n) bound on the number of similar copies of P inside Q that have 4 vertices of P in contact with the boundary of Q (assuming general position input), disproving a conjecture by Agarwal, Amenta, and Sharir (1998).
Cite as

Timothy M. Chan and Isaac M. Hair. Convex Polygon Containment: Improving Quadratic to Near Linear Time. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 34:1-34:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{chan_et_al:LIPIcs.SoCG.2024.34,
  author =	{Chan, Timothy M. and Hair, Isaac M.},
  title =	{{Convex Polygon Containment: Improving Quadratic to Near Linear Time}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{34:1--34:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-316-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{293},
  editor =	{Mulzer, Wolfgang and Phillips, Jeff M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.34},
  URN =		{urn:nbn:de:0030-drops-199795},
  doi =		{10.4230/LIPIcs.SoCG.2024.34},
  annote =	{Keywords: Polygon containment, convex polygons, translations, rotations}
}
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact