Efficient constant factor approximation algorithms for stabbing line segments with equal disks
share
Fast constant factor approximation algorithms are devised for a problem of intersecting a set of 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 (50+52√(12/13)+ε)-approximate O(|E|^4|E|)-time and O(|E|^2|E|) space algorithm based on the modified Agarwal-Pan algorithm. More accurate (34+24√(2)+ε)-, (12+6√(3)+ε)- and (34+38√(15/19)+ε)-approximate algorithms are proposed for the case where G is any subgraph of either an outerplane or a Gabriel graph or a Delaunay triangulation respectively, which work within the same time and space complexity bounds, where ε>0 is an arbitrary small constant.
READ FULL TEXT