Существует довольно много алгоритмов нахождения диаграммы Вороного с евклидовым расстоянием. Однако я не нашел алгоритмов других функций расстояния, например, манхэттенского расстояния (возможно, из-за отсутствия практического применения).
Вы можете увидеть пример в Википедии:
https://en.wikipedia.org/wiki/Voronoi_diagram#/media/File:Manhattan_Voronoi_Diagram.svg
Манхэттенская диаграмма Вороного тоже состоит из многоугольников (но невыпуклых), поэтому я предполагаю, что этот алгоритм похож на Fortune's алгоритм может быть построен. Однако при использовании более сложных функций расстояния границы больше не будут полигонами. Там будет потребность в другой структуре данных и алгоритме.
Существуют ли какие-либо алгоритмы для нахождения диаграммы Вороного с определенной функцией расстояния (в 2D для простоты)?
Примечание: мне не нужен алгоритм, работающий с пикселями, он довольно прост, мне нужен алгоритм, который находит границы ячеек.
Примечание 2 Практически мне нужна диаграмма Вороного с функцией расстояния abs(dx)^3 + abs(dy)^3, однако теоретически меня интересует, как можно составить алгоритм для других функций расстояния. Вот как выглядит Вороной с abs(dx)^3 + abs(dy)^3. Сайты непрерывны, а их ребра напоминают графики y=x^3 (просто предположение).
