минимальный график на пространственных точках

Question

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

---

Мне нужен минимальный граф для точек в виде вершин, который имеет следующее свойство:

Между любыми 2 точками P1, P2: есть путь, по которому для всей внутренней точки P3:

расстояние (P1, P3) <= расстояние (P1, P2). </p>

---

Хотя моя проблема в том, что я не могу понять, как вычислить этот минимальный график в доступное время.

Answer 1

Звучит так, будто все, что вы просите, это точки на некотором расстоянии от другой точки. d (P1, P2) - это просто число, поэтому все точки на этом расстоянии от P1 будут соответствовать вашим критериям.

Если вам нужно многократно выполнять поиск с нескольких начальных точек, вам следует взглянуть на стандартные структуры данных, такие как деревья kd. Если вы выполняете его только один раз, то лучшим вариантом будет просто итерация по всем точкам.

Какое приложение вы имели в виду?

Answer 2

7 лет спустя я думаю, что смогу ответить на свой вопрос:

---

Граф, который я искал, называется монотонным графом близости - наиболее известным примером является триангуляция / тетраэдризация Делоне.

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

Из-за этих проблем я думаю, что в целом их применение для ускорения запросов KNN не рекомендуется, и нужно просто использовать kd-деревья.

Answer 3

Это потому, что нет серебряной пули.

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