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

DOI10.1007/S00224-018-9885-YMaRDI QIDQ2000002zbMATH OpenOpenAlexFDO

Authors Carlos Alegría-Galicia, David Orden, Leonidas Palios, Carlos Seara, J. Urrutia

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

polyhedron3SUMgeometric optimizationrotationpolygonpoints covering

Mathematics Subject Classification ID

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

Abstract: We study the problem of rotating a simple polygon to contain the maximum number of elements from a given point set in the plane. We consider variations of this problem where the rotation center is a given point or lies on a line segment, a line, or a polygonal chain. We also solve an extension to 3D where we rotate a polyhedron around a given point to contain the maximum number of elements from a set of points in the space.

Recommendations

• Optimal placement of convex polygons to maximize point containment
• scientific article; zbMATH DE number 871906
• Translating a convex polygon to contain a maximum number of points.
• Covering points with a polygon
• Rotational polygon containment and minimum enclosure using only robust 2D constructions

Cites work

• scientific article; zbMATH DE number 1947380 (Why is no real title available?)
• Higher lower bounds from the 3SUM conjecture
• Offset polygon and annulus placement problems
• On a class of \(O(n^ 2)\) problems in computational geometry
• Optimal placement of convex polygons to maximize point containment
• POLYGON CONTAINMENT AND TRANSLATIONAL IN-HAUSDORFF-DISTANCE BETWEEN SEGMENT SETS ARE 3SUM-HARD
• Polygon decomposition for efficient construction of Minkowski sums
• Subquadratic algorithms for 3SUM
• Threesomes, degenerates, and love triangles
• Towards polynomial lower bounds for dynamic problems
• Translating a convex polygon to contain a maximum number of points.

Cited in

(2)

• The maximum cover with rotating field of view
• Covering points with a polygon

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2000002)