Fast constant factor approximation algorithms are devised for an NP- and W 1%DIFDELCMD < ]%%% -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(n^4\log n\right)-time and O\left(n^2\log n\right)-space algorithm is given based on the modified Agarwal-Pan algorithm  . More accurate (34+242+ \varepsilon )- 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 .
 %DIFDELCMD < ]%%% An NP-hard problem is considered of intersecting a given set of n straight line segments on the plane 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 proper edge crossings. To the best of our knowledge, related work only tackles a setting where E consists of (generally, properly overlapping) axis-parallel segments, resulting in an O(n\log n)-time and O(n\log n)-space 8-approximation algorithm. Exploiting tough connection of the problem with the geometric Hitting Set problem, an \left(50+52\frac{12{13}}+ \nu \right)-approximate O\left(n^4\log n\right)-time and O\left(n^2\log n\right)-space algorithm is devised based on the modified Agarwal-Pan algorithm , which uses epsilon nets . More accurate (34+242+ \nu )- and \left( \frac{144 + 32\sqrt{\frac{3 + \nu \right)-approxi\-mate algorithms are also proposed for cases where G is any subgraph of either a generalized outerplane graph or a Delaunay triangulation respectively, which work within the same time and space complexity bounds, where \nu >0 is an arbitrarily small constant .
D
Fast constant factor approximation algorithms are devised for an NP- and W
D
1
R
-hard problem
An NP-hard problem is considered
A
given
A
on the plane
A
proper
A
To the best of our knowledge, related work only tackles a setting where E consists of (generally, properly overlapping) axis-parallel segments, resulting in an O(n\log n)-time and O(n\log n)-space 8-approximation algorithm.
R
\varepsilon
\nu
R
given
devised
A
, which uses epsilon nets
R
\varepsilon
\nu
R
34
\frac{144
R
44\sqrt{\frac{6
32\sqrt{\frac{3
R
\varepsilon
\nu
R
an
a generalized
R
\varepsilon
\nu
R
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
arbitrarily small constant