19. Поиск ближайшей пары и всех ближайших соседей с использованием диаграммы Вороного.

Диаграмма Вороного порядка 2 – диаграмма, содержащая области близости, внутри которых любая точка ближе к 2 точкам множества (к обоим!!!), чем к любой другой точке множества.

Очевидно, что диаграмма Вороного порядка N-1 – это то же самое, что диаграмма Вороного дальних точек порядка.

1. Т.е. VNk=VFn-k

А на построение всех диаграмм Вороного нужно O(N2).