Проблемы близости

Проблемы близости — это класс задач вычислительной геометрии , которые включают оценку расстояний между геометрическими объектами.

Подмножество этих задач, сформулированных только в терминах точек, иногда называют задачами ближайших точек . ^[1] хотя термин «проблема ближайшей точки» также используется как синоним поиска ближайшего соседа .

Общей чертой многих из этих задач является возможность установить Θ ( n log n ) нижнюю границу их вычислительной сложности путем перехода от проблемы уникальности элемента на основе наблюдения, что если существует эффективный алгоритм для вычисления некоторого рода минимального расстояние для набора объектов, проверить, равно ли это расстояние 0, несложно.

Атомные проблемы

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

Расстояние между парой отрезков линии . Его нельзя выразить одной формулой, в отличие, например, от расстояния от точки до линии . Его расчет требует тщательного перечисления возможных конфигураций, особенно в 3D и более высоких измерениях. ^[2]
Ограничивающая рамка — минимальный гиперпрямоугольник , выровненный по оси , который содержит все геометрические данные.

Проблемы по баллам

Ближайшая пара точек : по N точкам найти две с наименьшим расстоянием между ними.
Запрос ближайшей точки / запрос ближайшего соседа : учитывая N точек, найдите точку с наименьшим расстоянием до заданной точки запроса.
Задача всех ближайших соседей (построение графа ближайших соседей ): по N точкам найти ближайшую для каждой из них.
Диаметр набора точек : по N точкам найти две с наибольшим расстоянием между ними.
Ширина набора точек : по N точкам найти две (гипер)плоскости с наименьшим расстоянием между ними и со всеми точками между ними.
Минимальное остовное дерево для набора точек
- Евклидово минимальное остовное дерево
Триангуляция Делоне
Диаграмма Вороного
Наименьшая охватывающая сфера : по N точкам найдите наименьшую сферу (круг), охватывающую их все.
Самый большой пустой круг : по N точкам на плоскости найдите самый большой круг с центром в их выпуклой оболочке и не включающий ни одну из них.
Наименьший охватывающий прямоугольник : в отличие от проблемы с ограничивающей рамкой, упомянутой выше, прямоугольник может иметь любую ориентацию.
Самый большой пустой прямоугольник
Геометрический ключ — взвешенный граф с набором точек в качестве вершин, который для каждой пары вершин имеет путь между ними, вес которого не превышает «k», умноженного на пространственное расстояние между этими точками для фиксированного «k».

Другой

Ссылки

Франко П. Препарата и Майкл Ян Шамос (1985). Вычислительная геометрия. Введение . Спрингер-Верлаг . ISBN 0-387-96131-3 . 1-е издание: ISBN 0-387-96131-3 ; 2-е издание, исправленное и дополненное, 1988 г.: ISBN 3-540-96131-3 ; Русский перевод, 1989: ISBN 5-03-001041-6 . Проблемы близости рассматриваются в главах 6 и 7.

^ Дж. Р. Сак и Дж. Уррутиа (ред.) (2000). Справочник по вычислительной геометрии . Северная Голландия . ISBN 0-444-82537-1 . {{cite book}}: |author= имеет общее имя ( справка )
^ В.Я. Лумельский (1985). «О быстром вычислении расстояния между отрезками». Инф. Процесс. Летт. 21 (2): 55–61. дои : 10.1016/0020-0190(85)90032-8 .

[1] Дж. Р. Сак и Дж. Уррутиа (ред.) (2000). Справочник по вычислительной геометрии . Северная Голландия . ISBN 0-444-82537-1 . {{cite book}}: |author= имеет общее имя ( справка )

[2] В.Я. Лумельский (1985). «О быстром вычислении расстояния между отрезками». Инф. Процесс. Летт. 21 (2): 55–61. дои : 10.1016/0020-0190(85)90032-8 .

[1]

[2]