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

摘要

Let S denote a set of line segments in the plane. We say that a polygon P intersects S if every segment in S has a non-empty intersection with the interior or boundary of P. Currently, the best known algorithm finding a minimum perimeter polygon intersecting a set of line segments has a worst case exponential running time. It is also still unknown whether this problem is NP-hard. In this note we explore several approximation algorithms. We present efficient approximation algorithms that yield good empirical results, but can perform very poorly on pathological examples. We also present an O(n log n) algorithm with a guaranteed worst case performance bound that is at most π/2 times that of the optimum.