ВЫЧИСЛИТЕЛЬНАЯ СЛОЖНОСТЬ ЗАДАЧИ ОПТИМАЛЬНОГО ПЕРЕСЕЧЕНИЯ ОТРЕЗКОВ КРУГАМИ

Результат исследований: Вклад в журналСтатья

Аннотация

В работе изучается вычислительная сложность и строятся точные полиномиальные алгоритмы для задачи оптимального пересечения заданного набора отрезков на плоскости минимальным числом одинаковых кругов радиуса > 0, при этом отрезки задают множество ребер некоторого плоского графа и пересекаются не более чем в своих концевых точках. Близкие геометрические задачи возникают при анализе безопасности физических сетей. В работе сообщается -трудность задачи в сильном смысле для семейств отрезков, порождаемых триангуляциями Делоне, графами Габриеля и некоторыми другими их подграфами, часто возникающими в проектировании сетей, для и некоторой константы , где и являются (евклидовыми) длинами наидлиннейшего и наикратчайшего ребер графа .
Переведенное названиеComputational complexity for the problem of optimal intersections of straight line segments by disks
Язык оригиналаРусский
Страницы (с-по)171-181
Число страниц11
ЖурналТруды института математики и механики УрО РАН
Том23
Номер выпуска3
DOI
СостояниеОпубликовано - 2017

Предметные области WoS

  • Математика, Прикладная

ГРНТИ

  • 50.05.00 Теоретические основы программирования

Уровень публикации

  • Перечень ВАК

Цитировать