Approximation algorithms with guaranteed performance for the intersection of edge sets of some metric graphs with equal disks

K. S. Kobylkin

Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 25 (2019) no. 1, pp. 62-77

Résumé

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.

Détail

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

Bibliographie

[1] Agarwal P., Pan J., “Near-linear algorithms for geometric hitting sets and set covers”, Proc. of 30th Ann. Symp. on Comput. Geom., 2014, 271–279 | MR | Zbl

[2] Alon N., “A Non-linear lower bound for planar epsilon-nets”, Discr. Comput. Geom., 47:2 (2012), 235–244 | DOI | MR | Zbl

[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), no. 87, 2017, 8:1-8:13 | DOI | MR

[4] Biniaz A., Liu P., Maheshwari A., Smid M., “Approximation algorithms for the unit disk cover problem in 2D and 3D”, Comput. Geom., 60 (2017), 8–18 | DOI | MR | Zbl

[5] Bus N., Garg S., Mustafa N., Ray S., “Limits of local search: Quality and efficiency”, Discr. Comput. Geom., 57:3 (2017), 607–624 | DOI | MR | Zbl

[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, 19:5 (2013), 857–870 | DOI

[7] Efrat A., Katz M. J., Nielsen F., Sharir M., “Dynamic data structures for fat objects and their applications”, Comput. Geom., 15 (2000), 215–227 | DOI | MR | Zbl

[8] Jaromczyk J. W., Toussaint G. T., “Relative neighborhood graphs and their relatives”, Proc. IEEE, 80:9 (1992), 1502–1517 | DOI

[9] Kobylkin K. S., “Stabbing line segments with disks: Complexity and approximation algorithms”, Lect. Notes Comp. Sci, 10716 (2017), 356–367 | DOI

[10] Kobylkin K. S., “Constant factor approximation for intersecting line segments with disks”, Lect. Notes Comp. Sci, 11353 (2019), 447–454 | DOI

[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., 12:3 (1980), 205–222 | DOI

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

[13] Mustafa N., Ray S., “Improved results on geometric hitting set problems”, Discr. Comput. Geom., 44:4 (2010), 883–895 | DOI | MR | Zbl

[14] Pyrga E., Ray S., “New existence proofs for $\varepsilon$-nets”, Proc. of 24th Ann. Symp. on Comput. Geom., 2008, 199–207 | DOI | MR | Zbl