Convex Polygon Containment: Improving Quadratic to Near Linear Time
<|reference_start|>Convex Polygon Containment: Improving Quadratic to Near Linear Time: 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 $\Omega(n^2)$ 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/\varepsilon)}n^{1+\varepsilon})$ running time for any $\varepsilon>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).<|reference_end|>
@article{chan2024convex,
    title={Convex Polygon Containment: Improving Quadratic to Near Linear Time},
    author={Timothy M. Chan and Isaac M. Hair},
    journal={arXiv preprint arXiv:2403.13292},
    year={2024},
    archivePrefix={arXiv},
    eprint={2403.13292},
    primaryClass={cs.CG}
}