Maximum overlap area of a convex polyhedron and a convex polygon under translation

Abstract

Let $P$ be a convex polyhedron and $Q$ be a convex polygon with $n$ vertices in total in three-dimensional space. We present a deterministic algorithm that finds a translation vector $v\in {\mathbb{R}}^3$ maximizing the overlap area $|P\cap (Q+v)|$ in $O(n{\log }^{2}n)$ time. We then apply our algorithm to solve two related problems. We give an $O(n{\log }^{3}n)$ time algorithm that finds the maximum overlap area of three convex polygons with $n$ vertices in total. We also give an $O(n{\log }^{2}n)$ time algorithm that minimizes the symmetric difference of two convex polygons under scaling and translation.

arXiv comment20 pages, 7 figures