Minimum-perimeter intersecting polygons

DOI10.1007/S00453-011-9516-3MaRDI QIDQ2429366zbMATH OpenOpenAlexFDO

Authors Adrian Dumitrescu, Minghui 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 programmingapproximation algorithmconvex polygonNP-hardness

Mathematics Subject Classification ID

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

Recommendations

• Minimum-perimeter intersecting polygons
• Approximation Algorithms for Finding a Minimum Perimeter Polygon Intersecting a Set of Line Segments
• MINIMUM POLYGON TRANSVERSALS OF LINE SEGMENTS
• Computing nonsimple polygons of minimum perimeter
• Minimum-perimeter enclosures

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A Lower Bound for the Volume of Strictly Convex Bodies with many Boundary Lattice Points
• An Asymptotic Expression for the Number of Solutions of a General Class of Diophantine Equations
• Approximating largest convex hulls for imprecise points
• Approximation Algorithms for Finding a Minimum Perimeter Polygon Intersecting a Set of Line Segments
• Approximation algorithms for TSP with neighborhoods in the plane
• Approximation algorithms for the Geometric Covering Salesman Problem
• Largest and smallest convex hulls for imprecise points
• MINIMUM POLYGON TRANSVERSALS OF LINE SEGMENTS
• On the Number of Convex Lattice Polygons
• TSP with neighborhoods of varying size

Cited in

(12)

• Computing nonsimple polygons of minimum perimeter
• Minimum area circumscribing polygons
• Minimum-perimeter intersecting polygons
• Approximation Algorithms for Finding a Minimum Perimeter Polygon Intersecting a Set of Line Segments
• Opaque sets
• New results on stabbing segments with a polygon
• The touring rays and related problems
• Polynomial-time algorithms for the touring rays and related problems
• MINIMUM POLYGON TRANSVERSALS OF LINE SEGMENTS
• The traveling salesman problem for lines and rays in the plane
• Extremal polygons with minimal perimeter
• Convex transversals

This page was built for publication: Minimum-perimeter intersecting polygons

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