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 \left(50+52\frac{12{13}}+\varepsilon\right)-approximate O ( \left(\left( |E| ^4\log{\varepsilon^2}+\log|E|{\varepsilon^3}}\right) |E| )-time and O(|E| ^2\log|E| ) spa\-ce algorithm \right)\left({\varepsilon}}\right) based on the modified Agarwal-Pan algorithm. More accurate (34+24\sqrt{2}+\varepsilon)-, \left(12+6\sqrt{3}+\varepsilon\right)- and \left(34+38\sqrt{\frac{15}{19}}+\varepsilon\right) -ap\-pro\-xi\-mate 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 \varepsilon>0 is an arbitrary small constant  .
Fast constant factor approximation algorithms are devised for an NP- and W 1]-hard 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 tough connection of the problem with the geometric Hitting Set problem , an \left(50+52\frac{12{13}}+\varepsilon\right)-approximate O \left(\left( |E| ^2+\frac{|E|\log|E|{\varepsilon^2}+\log|E|{\varepsilon^3}}\right) |E| ^2\log|E| \right)-time and O\left(\frac{|E|^2\log|E|{\varepsilon}}\right)-space algorithm is given based on the modified Agarwal-Pan algorithm. More accurate (34+24\sqrt{2}+\varepsilon)-, \left(12+6\sqrt{3}+\varepsilon\right)- and \left(34+38\sqrt{\frac{15}{19}}+\varepsilon\right) -approximate algorithms are also 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 \varepsilon>0 is an arbitrary small constant . Related work only tackles the case where E consists of axis-parallel segments, resulting in an O(|E|\log|E|)-time and O(|E|\log|E|)-space 8-approximation .
R
a
an NP- and W
A
1
A
-hard
R
its tough connection
tough connection of the problem
R
we give
, an
D
(
R
^4\log
^2+\frac{|E|\log|E|
D
)-time and O(|E|
D
) spa\-ce algorithm
A
-time and O
A
\frac{|E|^2\log|E|
A
-space algorithm is given
R
-ap\-pro\-xi\-mate algorithms are
-approximate algorithms are also
A
. Related work only tackles the case where E consists of axis-parallel segments, resulting in an O(|E|\log|E|)-time and O(|E|\log|E|)-space 8-approximation