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

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

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

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

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

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

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

Другой

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

  • Франко П. Препарата и Майкл Ян Шамос (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.CS1 maint: дополнительный текст: список авторов (связь)
  2. ^ В. Я. Лумельский (1985). «О быстром вычислении расстояния между отрезками». Инф. Процесс. Lett. 21 (2): 55–61. Дои:10.1016/0020-0190(85)90032-8.