DROPS

Document

DOI: 10.4230/LIPIcs.SoCG.2025.31

A Linear Time Algorithm for the Maximum Overlap of Two Convex Polygons Under Translation

Authors: Timothy M. Chan and Isaac M. Hair

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract

Given two convex polygons P and Q with n and m edges, the maximum overlap problem is to find a translation of P that maximizes the area of its intersection with Q. We give the first randomized algorithm for this problem with linear running time. Our result improves the previous two-and-a-half-decades-old algorithm by de Berg, Cheong, Devillers, van Kreveld, and Teillaud (1998), which ran in O((n+m)log(n+m)) time, as well as multiple recent algorithms given for special cases of the problem.

Cite as

Timothy M. Chan and Isaac M. Hair. A Linear Time Algorithm for the Maximum Overlap of Two Convex Polygons Under Translation. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 31:1-31:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chan_et_al:LIPIcs.SoCG.2025.31,
  author =	{Chan, Timothy M. and Hair, Isaac M.},
  title =	{{A Linear Time Algorithm for the Maximum Overlap of Two Convex Polygons Under Translation}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{31:1--31:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.31},
  URN =		{urn:nbn:de:0030-drops-231832},
  doi =		{10.4230/LIPIcs.SoCG.2025.31},
  annote =	{Keywords: Convex polygons, shape matching, prune-and-search, parametric search}
}

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}
}

Search Results

Documents authored by Hair, Isaac M.

A Linear Time Algorithm for the Maximum Overlap of Two Convex Polygons Under Translation

Abstract

Cite as

Convex Polygon Containment: Improving Quadratic to Near Linear Time

Abstract

Cite as

Thanks for your feedback!

Could not send message