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

DOI10.1007/S00224-018-9885-YzbMATH Open1431.68113arXiv1805.02570OpenAlexW3099711822MaRDI QIDQ2000002FDOQ2000002

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

Publication date: 27 June 2019

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

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.

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)

Cites Work

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

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)