POLYGON CONTAINMENT AND TRANSLATIONAL IN-HAUSDORFF-DISTANCE BETWEEN SEGMENT SETS ARE 3SUM-HARD

DOI10.1142/S0218195901000596zbMath1074.68629MaRDI QIDQ4682166

Gill Barequet, Sariel Har-Peled

Publication date: 10 June 2005

Published in: International Journal of Computational Geometry & Applications (Search for Journal in Brave)

zbMATH Keywords

Computational complexityHausdorff distancepolygon containment3SUM-hardnesssegment sets

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational aspects related to convexity (52B55) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (12)

Matching Triangles and Basing Hardness on an Extremely Popular Conjecture ⋮ Faster All-Pairs Shortest Paths via Circuit Complexity ⋮ Subquadratic algorithms for algebraic 3SUM ⋮ A zonotopic characterization of cyber‐physical system vulnerabilities ⋮ Unnamed Item ⋮ Scandinavian thins on top of cake: new and improved algorithms for stacking and packing ⋮ Approximating the maximum overlap of polygons under translation ⋮ Capturing points with a rotating polygon (and a 3D extension) ⋮ Hardness of comparing two run-length encoded strings ⋮ Approximate Matching for Run-Length Encoded Strings Is 3sum-Hard ⋮ Improved Bounds for 3SUM, k-SUM, and Linear Degeneracy ⋮ From Circuit Complexity to Faster All-Pairs Shortest Paths

Cites Work

• The upper envelope of Voronoi surfaces and its applications
• On a class of \(O(n^ 2)\) problems in computational geometry
• Applications of Parametric Searching in Geometric Optimization

This page was built for publication: POLYGON CONTAINMENT AND TRANSLATIONAL IN-HAUSDORFF-DISTANCE BETWEEN SEGMENT SETS ARE 3SUM-HARD