Я не уверен что вы и я используем одно и то же определение диаграммы Вороного.
Я использую определение через ближайшие точки или через максимальную пустую окружность.
Диаграмма Вороного - это функция определённая на сфере. Пусть

множество точек на сфере для которого определяется диаграмма. Тогда диаграмма по точке

сферы возвращает подмножество

состоящее из наиболее близких точек:

, где

.
Тогда вершина диаграммы для точек

это

. На плоскости вершина - пустое или одноточечное множество. На сфере вершина может состоять из пары точек, но это вырожденный случай.
Ребро определяется аналогично. С таким определением ребра ясно как выбрать нужный участок полного круга. Пусть даны точки

. Полный круг для точек

:

. Для любой точки круга если

, то это точка на ребре, иначе нет. На каждом из полукругов достаточно проверить одну точку.
-- 02.01.2018, 15:51 --Вы правильно подметили про треугольники. Есть такая микролемма: если треугольник остроугольный, то он содержит вершину диаграммы. Но это тупик. Вы дальше продвинетесь если будете работать только с расстояниями. Функции

и

позволяют получить больше результатов в более общей форме.