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( %DIFDELCMD < \left(%%% |E|^2+\frac{|E|\log|E|{\varepsilon^2}+\log|E|{\varepsilon^3}}  \right) |E|^2\log |E|%DIFDELCMD < \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+242+\varepsilon)- ,%DIFDELCMD < \left(%%% 12+6\sqrt{3+\varepsilon}%DIFDELCMD < \right)%%% - and \left(34+ 38\sqrt{\frac{15 +\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.
Fast constant factor approximation algorithms are devised for an NP- and W[1]-hard 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 tough connection of the problem with the geometric Hitting Set problem, an \left(50+52\frac{12{13}}+\varepsilon\right)-approximate O\left( %DIFDELCMD < \left(%%% {\varepsilon^2}+\log|E|{\varepsilon^3}} n^4\log n \right) %DIFDELCMD < \right)%%% -time and O\left( {\varepsilon}} n^2\log n \right)-space algorithm is given based on the modified Agarwal-Pan algorithm. More accurate (34+242+\varepsilon)- %DIFDELCMD < \left(%%% +\varepsilon}%DIFDELCMD < \right)%%% and \left(34+ 44\sqrt{\frac{6 +\varepsilon\right) -approxi\-mate algorithms are also proposed for cases where G is any subgraph of either an outerplane graph or a Delaunay triangulation respectively, which work within the same time and space complexity bounds, where \varepsilon>0 is an arbitrary small constant. Moreover, an 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. To the best of our knowledge, related work only tackles the case where E consists of axis-parallel segments, resulting in an O( n\log n )-time and O( n\log n )-space 8-approximation.
A
n
D
|E|^2+\frac{|E|\log|E|
A
n^4\log n
D
|E|^2\log |E|
D
\frac{|E|^2\log|E|
A
n^2\log n
D
,
D
12+6\sqrt{3
D
-
R
38\sqrt{\frac{15
44\sqrt{\frac{6
R
-approximate
-approxi\-mate
R
the case
cases
D
or a Gabriel
R
Related
Moreover, an 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. To the best of our knowledge, related
R
|E|\log |E|
n\log n
R
|E|\log |E|
n\log n