Сферическая планиметрия (сферометрия?)

[slavav]

Ваши методы и мои существенно различаются только если есть полусфера свободная от точек. В этой полусфере будут получаться странные треугольники (многоугольники в случает множества точек не общего положения). Во всех других ситуациях можно рисовать кратчайшие дуги больших кругов.

[B@R5uk]

Поздравьте меня! Не прошло и двух недель, как у меня полностью заработало построение диаграммы добавлением точек по одной:



Единственное, что омрачает радость, это треугольники с пересекающимися рёбрами в случае, когда их длина больше $\pi$. Видимо, длинные рёбра правильным будет вообще не рисовать:



Теперь надо бы освоить объединение нескольких диаграмм для алгоритма "разделяй и властвуй".

[slavav]

Поздравляю! Отличный прогресс!

[B@R5uk]

Спасибо!

Только что ещё раз проглядел по-быстрому разные статейки про "разделяй и властвуй", что-то нигде ничего не говориться про то до какой степени разделять. А так же про то, как именно разделять. На мой взгляд делить диаграмму на число сайтов, меньшее 3-х будет перебор. Но деление пополам может приводить в таком случае к минимальному рабочему размеру, равному 3, 4 и 5 сайтов. Я правильно понимаю, что для 3-х сайтов диаграмма строится специальным образом, для 4-х и 5-и сайтов диаграмма делается через пополнение 3-сайтовой диаграммы по одной точке, а уже потом включается алгоритм объединения?

Кроме того, можно заметить, что резать исходное множество пополам может оказаться не эффективно, так как в худшем случае придётся делать порядка $2N/5$ операций пополнений, если каждая половинка при попытке деления "в лоб" приведёт к 5-сайтовым минимальным подмножествам. Это, конечно, не $O(N^2)$, но всё равно неприятный добавок. Не лучше ли будет сразу резать на части по три точки слева на право, а затем объединять в порядке 3+3=6, 6+6=12 и так далее?

И потом, если резать множества на подмножества только по одной координате, то большинство вершин диаграммы, которые образуются на начальном этапе не доживут до конечного результата. Всё потому, что сайты находятся редко на узких вертикальных полосках, что приводит к тому, что промежуточные вершины диаграммы оказываются от них удалены весьма значительно и при слиянии на следующих этапах будут обрезаны. В отличие, например, от трёх плотно упакованных точек, вершина диаграммы для которых оказывается между ними. Разве делить исходное множество на компактные подмножества не будет тогда более эффективным подходом?

И в конце-концов для сферы. Я правильно понимаю, что для двух соседних диаграмм Вороного, координаты $\theta$ сайтов которых лежат по разные стороны разделителя, каждый граничный сайт поучаствует в создании только двух вершин диаграммы? Или же их может быть больше?

[slavav]

"разделяй и властвуй" делит примерно пополам любое количество точек больше одной. Обработка малого количества точек другими методами - преждевременная оптимизация, пока у вас нет работающего алгоритма "разделяй и властвуй".

Вам придётся резать под одной координате, иначе алгоритм объединения поддиаграмм будет неоправданно сложным и медленным. Повторюсь, не оптимизируйте то что ещё не работает.

Любая точка может участвовать в образовании многих (почти всех) вершин диаграммы.