Вычислительная сложность задачи оптимального пересечения отрезков кругами

В работе изучается вычислительная сложность и строятся точные полиномиальные алгоритмы для задачи оптимального пересечения заданного набора отрезков на плоскости минимальным числом одинаковых кругов радиуса $r>0,$ при этом отрезки задают множество ребер некоторого плоского графа $G=(V,E)$ и пересекаются не более чем в своих концевых точках. Близкие геометрические задачи возникают при анализе безопасности физических сетей. В работе сообщается $NP$-трудность задачи в сильном смысле для семейств отрезков, порождаемых триангуляциями Делоне, графами Габриеля и некоторыми другими их подграфами, часто возникающими в проектировании сетей, для $r\in [d_{\min},\eta d_{\max}]$ и некоторой константы $\eta,$ где $d_{\max}$ и $d_{\min}$ являются (евклидовыми) длинами наидлиннейшего и наикратчайшего ребер графа $G.$