Constant Factor Approximation for Intersecting Line Segments with Disks

摘要

Fast constant factor approximation algorithms are devised for a problem of intersecting a set of n straight line segments with the smallest cardinality set of disks of fixed radii r > 0 where the set of segments forms a straight line drawing G = (V, E) of a planar graph without edge crossings. Exploiting its tough connection with the geometric Hitting Set problem we give (100 + ε)-approximate O(n~4 log n)-time and O(n~2 log n)-space algorithm based on the modified Agarwal-Pan reweighting algorithm, where e > 0 is an arbitrary small constant. Moreover, O(n~2 log n)-time and O(n~2)-space 18-approximation is designed for the case where G is any subgraph of a Gabriel graph.