Capturing points with a rotating polygon (and a 3D extension)

DOI10.1007/s00224-018-9885-yzbMath1431.68113arXiv1805.02570OpenAlexW3099711822MaRDI QIDQ2000002

Leonidas Palios, Carlos Seara, Jorge Urrutia, Carlos Alegría-Galicia, David Orden

Publication date: 27 June 2019

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1805.02570

zbMATH Keywords

rotationpolyhedronpolygongeometric optimization3SUMpoints covering

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Offset polygon and annulus placement problems
• Optimal placement of convex polygons to maximize point containment
• On a class of \(O(n^ 2)\) problems in computational geometry
• Subquadratic algorithms for 3SUM
• Translating a convex polygon to contain a maximum number of points.
• Towards polynomial lower bounds for dynamic problems
• Threesomes, Degenerates, and Love Triangles
• Higher Lower Bounds from the 3SUM Conjecture
• POLYGON CONTAINMENT AND TRANSLATIONAL IN-HAUSDORFF-DISTANCE BETWEEN SEGMENT SETS ARE 3SUM-HARD
• Polygon decomposition for efficient construction of Minkowski sums

This page was built for publication: Capturing points with a rotating polygon (and a 3D extension)