Цель вычислительной геометрии — создание алгоритмов, эффективно отвечающих на вопросы, возникающие в прикладных областях, которые манипулируют дискретными геометрическими объектами. Один из таких вопросов — вопрос о фигуре определенного типа, которая прокалывает (stabs) множество простых объектов. Например, определить, есть ли для данного множества из n отрезков на плоскости прямая, прокалывающая их все, можно за время O(n log n) c использованием двойственного преобразования на плоскости.[2] Если мы спросим о прокалывающей окружности (вместо прямой), элегантный результат из учебника превратится в открытую задачу. Используя другой тип двойственного преобразования, мы показали связь этой проблемы и обобщенных диаграмм Вороного (диаграммы Вороного в Хаусдорфовой метрике (Hausdorff Voronoi diagram) и диаграммы Вороного дальнего цвета (farthest-color Voronoi diagram).[1] Специальные свойства этих диаграмм позволили нам создать новый алгоритм для решения задач о прокалывающей окружности. Временная сложность решения данных задач понизилась сO(n^2) до O(n log^2 n) в случае если все отрезки множества колинеарны. В случае произвольных отрезков, наш метод понизил сложность с O(n^2 log^2 n) до O(n^2).

Основано на:
[1] M. Claverol, E. Khramtcova, E. Papadopoulou, M. Saumell, C. Seara, Stabbing circles for sets of segments in the plane. XVI EGC, Barcelona, 2015
[2] H. Edelsbrunner, L.J. Guibas, M. Sharir, The upper envelope of piecewise linear functions: algorithms and applications, Discrete Comput. Geom. 4 (1989), 311– 336.