🔖 Как связаны диаграммы Вороного и параболоиды

Диаграмму Вороного можно получить через геометрическую интерпретацию в 3D. Для каждой точки xᵢ строится поверхность yᵢ(x) = D(xᵢ, x), где D — функция расстояния.

Диаграмма Вороного возникает как вертикальная проекция нижней оболочки всех этих поверхностей.

Если выбрать расстояние D(x, x′) = ‖x − x′‖², то поверхности yᵢ становятся параболоидами. В этом случае их нижняя оболочка образует плоские границы, а ячейки диаграммы Вороного получаются с линейными рёбрами.

Именно поэтому при квадратичном расстоянии диаграммы Вороного выглядят «прямыми», несмотря на параболическую природу построения.

tags: #полезное

➡ Data Scientist | Чат