Approximating the maximum overlap of polygons under translation

Sariel Har-Peled, Subhro Roy

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

Abstract

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
PublisherSpringer-Verlag
Pages542-553
Number of pages12
ISBN (Print)9783662447765
DOIs
StatePublished - Jan 1 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

Other

Other22nd Annual European Symposium on Algorithms, ESA 2014
CountryPoland
CityWroclaw
Period9/8/149/10/14

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

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

  • Cite this

    Har-Peled, S., & Roy, S. (2014). Approximating the maximum overlap of polygons under translation. In Algorithms, ESA 2014 - 22nd Annual European Symposium, Proceedings (pp. 542-553). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8737 LNCS). Springer-Verlag. https://doi.org/10.1007/978-3-662-44777-2_45