Minimum-perimeter intersecting polygons

DOI10.1007/s00453-011-9516-3zbMath1236.68084OpenAlexW2046670590MaRDI QIDQ2429366

Adrian Dumitrescu, Ming-Hui Jiang

Publication date: 26 April 2012

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-011-9516-3

zbMATH Keywords

linear programmingconvex polygonapproximation algorithmNP-hardness

Mathematics Subject Classification ID

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

Related Items

The touring rays and related problems ⋮ Convex transversals ⋮ New results on stabbing segments with a polygon ⋮ THE TRAVELING SALESMAN PROBLEM FOR LINES AND RAYS IN THE PLANE ⋮ Opaque sets ⋮ Polynomial-time algorithms for the touring rays and related problems

Cites Work

• Unnamed Item
• Largest and smallest convex hulls for imprecise points
• Approximating largest convex hulls for imprecise points
• Approximation algorithms for the Geometric Covering Salesman Problem
• Approximation Algorithms for Finding a Minimum Perimeter Polygon Intersecting a Set of Line Segments
• An Asymptotic Expression for the Number of Solutions of a General Class of Diophantine Equations
• On the Number of Convex Lattice Polygons
• Approximation algorithms for TSP with neighborhoods in the plane
• MINIMUM POLYGON TRANSVERSALS OF LINE SEGMENTS
• TSP with neighborhoods of varying size
• A Lower Bound for the Volume of Strictly Convex Bodies with many Boundary Lattice Points