TY - GEN

T1 - Approximating the maximum overlap of polygons under translation

AU - Har-Peled, Sariel

AU - Roy, Subhro

PY - 2014

Y1 - 2014

N2 - 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(cn) 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.

AB - 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(cn) 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.

UR - http://www.scopus.com/inward/record.url?scp=84958529920&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84958529920&partnerID=8YFLogxK

U2 - 10.1007/978-3-662-44777-2_45

DO - 10.1007/978-3-662-44777-2_45

M3 - Conference contribution

AN - SCOPUS:84958529920

SN - 9783662447765

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 542

EP - 553

BT - Algorithms, ESA 2014 - 22nd Annual European Symposium, Proceedings

PB - Springer

T2 - 22nd Annual European Symposium on Algorithms, ESA 2014

Y2 - 8 September 2014 through 10 September 2014

ER -