Approximating the maximum overlap of polygons under translation

Sariel Har-Peled, Subhro Roy

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.

Original languageEnglish (US)
Title of host publicationAlgorithms, ESA 2014 - 22nd Annual European Symposium, Proceedings
Number of pages12
ISBN (Print)9783662447765
StatePublished - 2014
Event22nd Annual European Symposium on Algorithms, ESA 2014 - Wroclaw, Poland
Duration: Sep 8 2014Sep 10 2014

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8737 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other22nd Annual European Symposium on Algorithms, ESA 2014

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Approximating the maximum overlap of polygons under translation'. Together they form a unique fingerprint.

Cite this