Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2504.18352 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866912346554761216 |
|---|---|
| author | Chan, Timothy M. Hair, Isaac M. |
| author_facet | Chan, Timothy M. Hair, Isaac M. |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_18352 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Linear Time Algorithm for the Maximum Overlap of Two Convex Polygons Under Translation Chan, Timothy M. Hair, Isaac M. Computational Geometry 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. |
| title | A Linear Time Algorithm for the Maximum Overlap of Two Convex Polygons Under Translation |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2504.18352 |