Approximating the Maximum Overlap of Polygons under Translation

Sariel Har-Peled, Subhro Roy

Research output: Contribution to journalArticle

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 a (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 suggests that for polygons that are “close” to being convex, the problem can be solved (approximately), in near linear time.

Original languageEnglish (US)
Pages (from-to)147-165
Number of pages19
JournalAlgorithmica
Volume78
Issue number1
DOIs
StatePublished - May 1 2017

Keywords

  • Approximation algorithms
  • Computational geometry
  • Polygon overlap

ASJC Scopus subject areas

  • Computer Science(all)
  • Computer Science Applications
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Approximating the Maximum Overlap of Polygons under Translation'. Together they form a unique fingerprint.

  • Cite this