Polygon containment and translational min-Hausdorff-distance between segment sets are 3sum-hard

Gill Barequet, Sariel Har-Peled

Research output: Contribution to journalArticlepeer-review

Abstract

The 3SUM problem represents a class of problems conjectured to require Ω(n2) time to solve, where n is the size of the input. Given two polygons P and Q in the plane, we show that some variants of the decision problem, whether there exists a transformation of P that makes it contained in Q, are 3SUM-hard. In the first variant P and Q are any simple polygons and the allowed transformations are translations only; in the second and third variants both polygons are convex and we allow either rotations only or any rigid motion. We also show that finding the translation in the plane that minimizes the Hausdorff distance between two segment sets is 3SUM-hard.

Original languageEnglish (US)
Pages (from-to)465-474
Number of pages10
JournalInternational Journal of Computational Geometry and Applications
Volume11
Issue number4
DOIs
StatePublished - Aug 2001

Keywords

  • 3SUM-hardness
  • Computational complexity
  • Hausdorff distance
  • Polygon containment
  • Segment sets

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Computational Theory and Mathematics
  • Computational Mathematics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Polygon containment and translational min-Hausdorff-distance between segment sets are 3sum-hard'. Together they form a unique fingerprint.

Cite this