K.S. Kobylkin. Approximation algorithms with guaranteed performance for the intersection of edge sets of some metric graphs with equal disks ... P. 62-77

Vol. 25, no. 1, 2019

Polynomial-time approximation algorithms with constant approximation ratio are proposed for the problem of intersection of a given set of $n$ planar straight line segments with the least number of equal disks. In the case where the segments have at most $k$ different orientations, a simple 4$k$-approximate algorithm with time complexity $O(n\log n)$ is known. In addition, a 100-approximate algorithm with time complexity $O(n^4\log n)$ is known for the case of the problem on the edge sets of plane graphs. In this paper, for instances of the problem on the edge sets of Gabriel graphs, relative neighbourhood graphs, and Euclidean minimum spanning trees, in which the number of different edge orientations is, in general, unbounded, we construct simple $O(n^2)$-time approximation algorithms with approximation ratios 14, 12, and 10, respectively. These algorithms outperform the aforementioned approximation algorithm for the general setting of the problem for edge sets of plane graphs.

Keywords: combinatorial optimization, approximation algorithm, geometric Hitting Set problem on the plane, straight line segment, Gabriel graph, relative neighborhood graph, Euclidean minimum spanning tree

Received November 19, 2018

Revised January 23, 2019

Accepted February 4, 2019

Funding Agency: This work was supported by the Russian Science Foundation (project no. 14-11-00109).

Konstantin Sergeevich Kobylkin, Cand. Sci. (Phys.-Math.), Krasovsky Institute of Mathematics and Mechanics of the Ural Branch of the Russian Academy of Sciences, Ekaterinburg, 620108 Russia; Ural Federal University, Yekaterinburg, 620002 Russia, e-mail: kobylkinks@gmail.com

Cite this article as:   Approximation algorithms with guaranteed performance for the intersection of edge sets of some metric graphs with equal disks, Trudy Instituta Matematiki i Mekhaniki URO RAN, 2019, vol. 25, no. 1, pp. 62–77. 

REFERENCES

1.   Agarwal P., Pan J. Near-Linear Algorithms for Geometric Hitting Sets and Set Covers. Proc. of 30th Ann. Symp. on Comput. Geom., 2014, pp. 271–279.

2.   Alon N. A Non-linear Lower Bound for Planar Epsilon-nets. Discr. Comput. Geom., 2012, vol. 47, no. 2, pp. 235–244. doi: 10.1007/s00454-010-9323-7 

3.   Antunes D., Mathieu C., Mustafa N. Combinatorics of Local Search: An Optimal 4-Local Hall’s Theorem for Planar Graphs. Proc. of 25th Ann. Eur. Symp. on Alg. (ESA), 2017, vol. 87, pp. 8:1–8:13. doi: 10.4230/LIPIcs.ESA.2017.8 

4.   Biniaz A., Liu P., Maheshwari A., Smid M. Approximation algorithms for the unit disk cover problem in 2D and 3D. Comput. Geom., 2017, vol. 60, pp. 8–18. doi: 10.1016/j.comgeo.2016.04.002 

5.   Bus N., Garg S., Mustafa N., Ray S. Limits of Local Search: Quality and Efficiency. Discr. Comput. Geom., 2017, vol. 57, no. 3, pp. 607–624. doi: 10.1007/s00454-016-9819-x 

6.   Dash D., Bishnu A., Gupta A., Nandy S.C. Approximation algorithms for deployment of sensors for line segment coverage in wireless sensor networks. Wireless Networks, 2013, vol. 19, no. 5, pp. 857–870. doi: 10.1007/s11276-012-0506-4 

7.   Efrat A., Katz M.J., Nielsen F., Sharir M. Dynamic data structures for fat objects and their applications. Comput. Geom., 2000, vol. 15, no. 4, pp. 215–227. doi: 10.1016/S0925-7721(99)00059-0 

8.   Jaromczyk J.W., Toussaint G.T. Relative neighborhood graphs and their relatives. Proc. IEEE, 1992, vol. 80, no. 9, pp. 1502–1517. doi: 10.1109/5.163414 

9.   Kobylkin K.S. Stabbing Line Segments with Disks: Complexity and Approximation Algorithms. Lect. Notes in Comp. Sci., 2017, vol. 10716, pp. 356–367. doi: 10.1007/978-3-319-73013-4_33 

10.   Kobylkin K.S. Constant factor approximation for intersecting line segments with disks. Lect. Notes in Comp. Sci., 2019, vol. 11353, pp. 447–454. doi: 10.1007/978-3-030-05348-2_39 

11.   Matula D.W., Sokal R.R. Properties of Gabriel graphs relevant to geographic variation research and clustering of points in the plane. Geogr. Anal., 1980, vol. 12, no. 3, pp. 205–222. doi: 10.1111/j.1538-4632.1980.tb00031.x 

12.   Madireddy R.R., Mudgal A. Stabbing line segments with disks and related problems. Proc. of 28th Canadian Conf. Comput. Geom., 2016, pp. 201–207.

13.   Mustafa N., Ray S. Improved Results on Geometric Hitting Set Problems. Discr. Comput. Geom., 2010, vol. 44, no. 4, pp. 883–895.

14.   Pyrga E., Ray S. New Existence Proofs for $\varepsilon$-nets. Proc. of 24th Ann. Symp. on Comput. Geom., 2008, pp. 199–207. doi: 10.1145/1377676.1377708