УДК 519.856
MSC: 90C15
DOI: 10.21538/0134-4889-2017-23-3-171-181
Полная версия статьи
Исследования поддержаны Российским научным фондом, грант № 14-11-00109.
В работе изучается вычислительная сложность и строятся точные полиномиальные алгоритмы для задачи оптимального пересечения заданного набора отрезков на плоскости минимальным числом одинаковых кругов радиуса r > 0, при этом отрезки задают множество ребер некоторого плоского графа G = (V,E) и пересекаются не более чем в своих концевых точках. Близкие геометрические задачи возникают при анализе безопасности физических сетей. В работе сообщается NP-трудность задачи в сильном смысле для семейств отрезков, порождаемых триангуляциями Делоне, графами Габриеля и некоторыми другими их подграфами, часто возникающими в проектировании сетей, для r ∈ [dmin,ηdmax] и некоторой константы η, где dmax и dmin являются (евклидовыми) длинами наидлиннейшего и наикратчайшего ребер графа G.
Ключевые слова: вычислительная сложность, задача Hitting Set, задача Continuous Disk Cover, триангуляция Делоне.
СПИСОК ЛИТЕРАТУРЫ
1. The resilience of WDM networks to probabilistic geographical failures / P. K. Agarwal, A. Efrat, S. K. Ganjugunte, D. Hay, S. Sankararaman, G. Zussman // IEEE/ACM Trans. on Networking. 2013. Vol. 21, no. 5. P. 1525–1538. doi: 10.1109/TNET.2012.2232111 .
2. Probabilistic bounds on the length of a longest edge in Delaunay graphs of random points in d dimensions / E. M. Arkin, A. F. Anta, J. S. Mitchell, M. A. Mosteiro // Comput. Geom. 2015. Vol. 48, no. 2. P. 134–146. doi: 10.1016/j.comgeo.2014.08.008 .
3. Optimal algorithms for some intersection radius problems / B. K. Bhattacharya, S. Jadhav, A. Mukhopadhyay, J. M. Robert // Computing. 1994. Vol. 52, no. 3. P. 269–279.
doi: 10.1007/BF02246508 .
4. Competitive online routing on Delaunay triangulations / P. Bose, J. L. Carufel, S. Durocher, P. Taslakian // Algorithm theory — SWAT 2014: Proc. Cham: Springer, 2014. P. 98–109 (Lecture Notes in Comput. Sci.; vol. 8503). doi: 10.1007/978-3-319-08404-6_9 .
5. Bose P., Kirkpatrick D. G., Li Z. Worst-case-optimal algorithms for guarding planar graphs and polyhedral surfaces // Comput. Geom. 2003. Vol. 26, no. 3. P. 209–219.
doi: 10.1016/S0925-7721(03)00027-0 .
6. Chan T. M., Grant E. Exact algorithms and APX-hardness results for geometric packing and covering problems // Comput. Geom. 2014. Vol. 47, no. 2. P. 112–124. doi: 10.1016/j.comgeo.2012.04.001 .
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. 1981. Vol. E64, no. 2. P. 57–64.
8. Marx D. Efficient approximation schemes for geometric problems? // Algorithms — ESA 2005: Proc. Berlin; Heidelberg: Springer, 2005. P. 448–459 (Lecture Notes in Comput. Sci.; vol. 3669).
doi: 10.1007/11561071_41 .
9. Quanrud K., Har-Peled S. Approximation algorithms for polynomial-expansion and low-density graphs // Algorithms — ESA 2015: Proc. Berlin; Heidelberg: Springer, 2015. P. 717–728 (Lecture Notes in Comput. Sci.; vol. 9294). doi: 10.1007/978-3-662-48350-3_60 .
10. O’Rourke J. Art gallery theorems and algorithms. Oxford: Oxford University Press, 1987. 282 p.
11. Routing with guaranteed delivery in ad hoc wireless networks / I. Stojmenovic, J. Urrutia, P. Bose, P. Morin // Wireless Networks. 2001. Vol. 7, no. 6. P. 609–616.
12. Tamassia R., Tollis I. G. Planar grid embedding in linear time // IEEE Trans. Circuits and Systems. 1989. Vol. 36. P. 1230–1234. doi: 10.1109/31.34669 .
Поступила 19.05.2017
Кобылкин Константин Сергеевич
канд. физ.-мат. наук, старший науч. сотрудник
Институт математики и механики им. Н.Н. Красовского УрО РАН,
Уральский федеральный университет,
г. Екатеринбург
e-mail: kobylkinks@gmail.com
English
K. S. Kobylkin. Computational complexity for the problem of optimal intersections of straight line segments by disks.
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 ∈ [dmin,ηdmax] and some constant η, where dmax and dmin are the Euclidean lengths of the longest and shortest graph edges, respectively.
Keywords: computational complexity, Hitting Set Problem, Continuous Disk Cover problem, Delaunay triangulations.
The paper was received by the Editorial Office on May 19, 2017.
Konstantin Sergeevich Kobylkin, Cand. Phys.-Math. Sci., Krasovsky Institute of Mathematics and Mechanics, Ural branch of Russian Academy of Sciences, Ekaterinburg, 620990 Russia; Ural Federal University, Yekaterinburg, 620002 Russia, e-mail: kobylkinks@gmail.com.
