Субквадратичные приближенные алгоритмы для NP-трудной задачи оптимального покрытия множества отрезков кругами

Рассматривается $NP$-трудная задача оптимального покрытия заданного множества отрезков на плоскости, пересекающихся не более, чем в своих концевых точках, минимальным числом одинаковых кругов. Для специальных случаев этой задачи, когда множество отрезков совпадает с множеством ребер некоторых специальных плоских графов (графов Габриеля, графов относительных окрестностей и минимальных евклидовых остовных деревьев), известны квадратичные по времени работы приближенные алгоритмы с небольшими константными факторами аппроксимации 14, 12 и 10 соответственно. Используя специальную структуру данных на основе диаграмм Вороного для систем отрезков, удалось получить субквадратичные приближенные алгоритмы для этих специальных случаев задачи с теми же факторами аппроксимации 14, 12 и10, но работающие за время $O(n^{3/2}\log^2n)$ в среднем, где $n$ - число отрезков.