Проблемы с близостью - Proximity problems - Wikipedia

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

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

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

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

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

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

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

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

Другой

• Кратчайший путь среди препятствий
• Расстояние ближайшего подхода

Рекомендации

• Франко П. Препарата и Майкл Ян Шамос (1985). Вычислительная геометрия - Введение. Springer-Verlag. 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.

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