2014/06/22 by Sariel Har-Peled, Har-Peled, Sariel, Subhro Roy +1 · 3 citations
Computer Science · #Algorithms and Data Compression #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #FOS: Computer and information sciences #Graph Theory and Algorithms #cs.CG
paper · pdf · doi:10.48550/arxiv.1406.5778
arxiv created 2014/06/22 · openalex publication_date 2014/06/22 · arxiv updated 2014/06/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
Let P and Q be two simple polygons in the plane of total complexity n, each of which can be decomposed into at most k convex parts. We present an (1-ε)-approximation algorithm, for finding the translation of Q, which maximizes its area of overlap with P. Our algorithm runs in O(c n) time, where c is a constant that depends only on k and ε. This suggest that for polygons that are "close" to being convex, the problem can be solved (approximately), in near linear time.