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

3SUMgeometric optimizationpoints coveringpolygonpolyhedronrotation

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) 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.

Review text

Rotation of an \(n\)-vertex simple polygon \(P\) around a fixed center to cover a maximum (or minimum) number out of \(m\) given points of the plane is shown to be 3SUM-hard. A simple sweep over all critical angles where some given point crosses an edge of \(P\) solves this problem in \(O(nm\log(nm))\) time and \(O(nm)\) space. This complexity is often improved by way of a moving radius sweep-circle maintaining its intersection with \(P\). This latter idea is then adapted to the extended problem where the rotation center may be moved along a segment, resulting in a plane-arrangement searchable for optimal depth, all of this in \(O(n^2m^2\log(nm))\) time and \(O(n^2m^2)\) space. Finally, a method of this same complexity for the 3D version with fixed rotation center is outlined.

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

• Higher lower bounds from the 3SUM conjecture
• scientific article; zbMATH DE number 1947380 (Why is no real title available?)
• 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)

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

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)