Geodesic
Computational complexity for the problem of optimal intersections of straight line segments by disks
Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 23 (2017) no. 3, pp. 171-181
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

Computational complexity and exact polynomial algorithms are reported for the problem of stabbing a set of straight line segments with a least 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. Similar geometric problems arise in network security applications (Agarwal et al., 2013). We establish the strong NP-hardness of the problem for edge sets of Delaunay triangulations, Gabriel graphs, and other subgraphs (which are often used in network design) for $r\in [d_{\min},\eta d_{\max}]$ and some constant $\eta$, where $d_{\max}$ and $d_{\min}$ are the Euclidean lengths of the longest and shortest graph edges, respectively.
Keywords: computational complexity, Hitting Set Problem, Continuous Disk Cover problem
Mots-clés : Delaunay triangulations. 
@article{TIMM_2017_23_3_a14,
     author = {K. S. Kobylkin},
     title = {Computational complexity for the problem of optimal intersections of straight line segments by disks},
     journal = {Trudy Instituta matematiki i mehaniki},
     pages = {171--181},
     year = {2017},
     volume = {23},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TIMM_2017_23_3_a14/}
}
TY  - JOUR
AU  - K. S. Kobylkin
TI  - Computational complexity for the problem of optimal intersections of straight line segments by disks
JO  - Trudy Instituta matematiki i mehaniki
PY  - 2017
SP  - 171
EP  - 181
VL  - 23
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/TIMM_2017_23_3_a14/
LA  - ru
ID  - TIMM_2017_23_3_a14
ER  - 
%0 Journal Article
%A K. S. Kobylkin
%T Computational complexity for the problem of optimal intersections of straight line segments by disks
%J Trudy Instituta matematiki i mehaniki
%D 2017
%P 171-181
%V 23
%N 3
%U http://geodesic.mathdoc.fr/item/TIMM_2017_23_3_a14/
%G ru
%F TIMM_2017_23_3_a14
K. S. Kobylkin. Computational complexity for the problem of optimal intersections of straight line segments by disks. Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 23 (2017) no. 3, pp. 171-181. http://geodesic.mathdoc.fr/item/TIMM_2017_23_3_a14/

[1] P. K. Agarwal, A. Efrat, S. K. Ganjugunte, D. Hay, S. Sankararaman, G. Zussman, “The resilience of WDM networks to probabilistic geographical failures”, IEEE/ACM Trans. on Networking, 21:5 (2013), 1525–1538 | DOI

[2] E. M. Arkin, A. F. Anta, J. S. Mitchell, M. A. Mosteiro, “Probabilistic bounds on the length of a longest edge in Delaunay graphs of random points in d dimensions”, Comput. Geom., 48:2 (2015), 134–146 | DOI | MR | Zbl

[3] B. K. Bhattacharya, S. Jadhav, A. Mukhopadhyay, J. M.Robert, “Optimal algorithms for some intersection radius problems”, Computing, 52:3 (1994), 269–279 | DOI | MR | Zbl

[4] P. Bose, J. L. Carufel, S. Durocher, P. Taslakian, “Competitive online routing on Delaunay triangulations”, Algorithm theory - SWAT 2014: Proc., Lecture Notes in Comput. Sci., 8503, Springer, Cham, 2014, 98–109 | DOI | MR | Zbl

[5] Bose P., Kirkpatrick D. G., Li Z., “Worst-case-optimal algorithms for guarding planar graphs and polyhedral surfaces”, Comput. Geom., 26:3 (2003), 209–219 | DOI | MR | Zbl

[6] Chan T. M., Grant E., “Exact algorithms and APX-hardness results for geometric packing and covering problems”, Comput. Geom., 47:2 (2014), 112–124 | DOI | MR | Zbl

[7] Hasegawa T., Masuyama S., Ibaraki T., “Computational complexity of the m-center problems on the plane”, Trans. of the Institute of Electronics and Communication Engineers of Japan. Section E, E64:2 (1981), 57–64

[8] Marx D., “Efficient approximation schemes for geometric problems?”, Algorithms - ESA 2005: Proc., Lecture Notes in Comput. Sci., 3669, Springer, Berlin; Heidelberg, 2005, 448–459 | DOI | MR | Zbl

[9] Quanrud K., Har-Peled S., “Approximation algorithms for polynomial-expansion and low-density graphs”, Algorithms - ESA 2015: Proc., Lecture Notes in Comput. Sci., 9294, Springer, Berlin; Heidelberg, 2015, 717–728 | DOI | MR | Zbl

[10] O'Rourke J., Art gallery theorems and algorithms, Oxford University Press, Oxford, 1987, 282 pp. | MR | Zbl

[11] I. Stojmenovic, J. Urrutia, P. Bose, P. Morin, “Routing with guaranteed delivery in ad hoc wireless networks”, Wireless Networks, 7:6 (2001), 609–616 | DOI | Zbl

[12] Tamassia R., Tollis I. G., “Planar grid embedding in linear time”, IEEE Trans. Circuits and Systems, 36 (1989), 1230–1234 | DOI | MR