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