Что это за структура данных / концепция, где график точек определяет разбиение на пространство

15

Я столкнулся с алгоритмом, чтобы решить реальную проблему, и я помню класс, который я взял, где я сделал что-то очень похожее для некоторых для домашней работы. это выглядит так

По сути, это график точек, и линии нарисованы так, чтобы они были равноудалены между двумя точками. Он образует идеальное разделение, где линии вокруг точки образуют форму области, которая ближе всего к этой точке. Это звонит кому-нибудь? Мне было тяжело гуглить описания и получать результаты. И я не знаю, как еще это описать. Надеюсь, картина поможет.

Брайан
источник
Просмотрено 1667 раз со вчерашнего дня? SE взломан?
HEKTO
@HEKTO это было отображено как один из "Горячих Сетевых Вопросов".
Джон Л.

Ответы:

31

То, что вы описали, это диаграмма Вороного .

Вот выдержка из Википедии.

Изображение диаграммы Вороного из Википедии

п1,,пNпКрКпКменьше или равно его расстоянию до любых других точек. Каждая такая клетка получается из пересечения полупространств и, следовательно, является выпуклым многоугольником. Сегментами линии диаграммы Вороного являются все точки на плоскости, которые равноудалены от двух ближайших точек. Вершины (узлы) Вороного - это точки, равноудаленные от трех (или более) узлов.

Джон Л.
источник
4
+1. Я воздержался от упоминания о них и пошел на реализацию, потому что я помню, как мои профессора упоминали их со сноской, что диаграммы Вороного в вычислительном отношении довольно сложны для реализации в более высоких измерениях. Простые реализации KNN делают работу намного лучше. Однако условие, что «линии нарисованы так, чтобы они были равноудалены между двумя точками», может не выполняться.
Сагник