2025/04/25 by Chan, Timothy M., Hair, Isaac M.
#Computational Geometry (cs.CG) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2504.18352
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.