эталонный алгоритм для взвешенных диаграмм Вороного?

Для аддитивно взвешенной диаграммы Вороного: Помните, что диаграмма мощности в размерности n есть только (n невзвешенная) диаграмма Вороного в размерности n + 1.

Для этого просто вспомните, что диаграмма Вороного набора точек инвариантна, если вы добавляете любую константу к координатам, и что взвешенная диаграмма Вороного, таким образом, может быть записана как невзвешенная диаграмма Вороного с использованием координат, например, в 2D, поднятая до 3D:
(x_i, y_i, sqrt (C - w_i))
где w_i - вес начального числа, а C - любая произвольно большая константа (на практике достаточно малая такая, что C-w_i является положительный).
Как только ваша диаграмма будет вычислена, просто отбросьте последний компонент.

Итак, по сути, вам нужно только найти библиотеку, которая способна обрабатывать диаграммы Вороного в размерности n + 1 по сравнению с вашей проблемой. CGAL может это сделать. Это также делает реализацию чрезвычайно простой.

Это непростое вычисление, но оно доступно в CGAL. См. страницы руководства здесь.

Существует мало "готового" открытого исходного кода для случая, когда расстояния до центров взвешиваются с множительным коэффициентом. Насколько мне известно, ни один из текущих пакетов CGAL не охватывает этот случай.

Красиво красочный веб-сайт Такаши Охьямы предоставляет java-реализации http://www.nirarebakun.com/voro/emwvoro.html до 100 точек с помощью ПРОСТОГО алгоритма (евклидово и манхэттенское расстояния). Также есть документ, описывающий этот простой алгоритм пересечения и примерную реализацию в течение O (n ^ 3) времени в качестве плагина к TerraView. Однако я не могу найти источник этого плагина в репозитории TerraView / TerraLib: http://www.geoinfo.info/geoinfo2011/papers/mauricio1.pdf

Ауренхаммер и Эдельсбруннер описывают оптимальный алгоритм времени n ^ 2, но мне неизвестен его доступный код.

Если вам удобно копаться в Octave, вы можете сослаться на код, предоставленный в их библиотеке.