Приближенные алгоритмы с гарантированными оценками точности для пересечения множеств ребер некоторых метрических графов равными кругами

В статье предлагаются полиномиальные приближенные алгоритмы с константным фактором аппроксимации для задачи пересечения заданного набора $n$ отрезков на плоскости наименьшим числом одинаковых кругов. Если число различных направлений отрезков, входящих в набор, не превосходит $k$, для этой задачи известен простой $4k$-приближенный алгоритм с временной сложностью $O(n\log n).$ Также для случая задачи на множествах ребер произвольных плоских графов известен 100-приближенный алгоритм с временем работы $O(n^4\log n)$. В настоящей работе для частных случаев задачи на множествах ребер графов Габриеля, графов относительных окрестностей и минимальных евклидовых остовных деревьев, число различных ориентаций ребер в которых, вообще говоря, не ограничено сверху, удается построить несложные алгоритмы с факторами аппроксимации, равными соответственно 14, 12 и 10, имеющие существенно меньшую трудоемкость $O(n^2)$ по сравнению с вышеупомянутым алгоритмом для общего случая задачи на множествах ребер произвольных плоских графов.