Approximation Algorithms for Finding a Minimum Perimeter Polygon Intersecting a Set of Line Segments

DOI10.1007/978-3-642-03367-4_32zbMath1253.68337OpenAlexW1525225516MaRDI QIDQ3183469

Farzad Farnoud Hassanzadeh, David Rappaport

Publication date: 20 October 2009

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-03367-4_32

zbMATH Keywords

approximation algorithmcomputational geometryline segmentintersecting polygon

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Related Items (3)

Minimum-perimeter intersecting polygons ⋮ New results on stabbing segments with a polygon ⋮ The maximal distance between imprecise point objects

Cites Work

• Unnamed Item
• Unnamed Item
• Shortest polygonal paths in space
• Farthest line segment Voronoi diagrams
• Optimal output-sensitive convex hull algorithms in two and three dimensions
• On intersecting a set of parallel line segments with a convex polygon of minimum area
• An efficient algorithm for determining the convex hull of a finite planar set
• On the identification of the convex hull of a finite set of points in the plane
• Largest Bounding Box, Smallest Diameter, and Related Problems on Imprecise Points
• Improved Complexity Bounds for Center Location Problems on Networks by Using Dynamic Data Structures
• Efficient Algorithms for the (Weighted) Minimum Circle Problem
• MINIMUM POLYGON TRANSVERSALS OF LINE SEGMENTS
• Stabbing parallel segments with a convex polygon
• Approximating Largest Convex Hulls for Imprecise Points
• Largest and Smallest Tours and Convex Hulls for Imprecise Points

This page was built for publication: Approximation Algorithms for Finding a Minimum Perimeter Polygon Intersecting a Set of Line Segments