2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Ближайшая пара точек
Сообщение31.03.2013, 23:23 
Аватара пользователя
Задача поиска двух ближайших точек из данного набора может быть решена с помощью стратегии "разделяй и властвуй" за время $O(n \log n)$. Описание этого алгоритма (на английском) можно поглядеть здесь (pdf).

Ключевой момент алгоритма состоит в том, что на прямоугольнике $\delta \times {\delta \over 2}$ можно расположить не более 6 точек так, чтобы расстояние между любыми двумя из них не превышало $\delta$. Поэтому в отсортированном массиве точек проверяются расстояния от каждой точки только до пяти последующих.

Но расположить шесть точек можно лишь единственным образом: вот так. И в этом случае минимальное расстояние между точками будет в точности равно $\delta$. Но ведь $\delta$ определена как минимальное найденное на данный момент расстояние. Следовательно, нам нужно искать лишь расстояния, строго меньшие, чем $\delta$. Значит, в алгоритме достаточно проверять не далее четырёх точек от текущей.

Я прав? Если нет, то где ошибка? Если да, то почему везде в Интернете предлагают проверять 5 (а то и даже 7) точек?

 
 
 
 Re: Ближайшая пара точек
Сообщение01.04.2013, 09:20 
Аватара пользователя
Цитата:
Следовательно, нам нужно искать лишь расстояния, строго меньшие, чем . Значит, в алгоритме достаточно проверять не далее четырёх точек от текущей.
Если ты возьмёшь 4 то есть вероятность что они будут располагаться в углах четырёх угольника, когда как минимальная эта та, что на стороне.
Как ты определишь какая точка где располагается не проверяя их все?
Можно проверить 5 и методом исключения найти 6. Хотя точи с минимальным расстоянием мы так и определим, но расстояние не вычислили, так что по любому надо вычислять расстояние для всех 6 точек.

 
 
 
 Re: Ближайшая пара точек
Сообщение01.04.2013, 09:48 
Аватара пользователя
Pavia в сообщении #704212 писал(а):
Как ты определишь какая точка где располагается не проверяя их все?

На данном шаге алгоритма точки лежат в массиве и они отсортированы по координате $y$. Проверяется расстояние от каждой точки до следующих пяти в массиве.

Я говорю о том, что если даже все последующие 5 точек и лежат в данном прямоугольнике (вместе с текущей, то есть всего 6 штук), то расстояния, меньшего чем $\delta$, мы среди них не найдём. Поэтому есть смысл проверять только 4 точки.

 
 
 
 Re: Ближайшая пара точек
Сообщение01.04.2013, 12:50 
Аватара пользователя
qx87 в сообщении #704218 писал(а):
Поэтому есть смысл проверять только 4 точки.

Да всё верно. Только эти точки из множества $S_2$, а в массиве у тебя точки из $S_2$ и $S_1$, что
в сумме даёт 8 точек из которых одна $P$. Итого 7 точек. Разумеется те 3 проверять не нужно они и так проверены, но тут опять вопрос. Как отличить кто из какого множества? Самое простое не разбирать, а проверять всех из общей "кучи". т.е все 7 точек

http://algolist.manual.ru/maths/geom/closest_points.php

 
 
 [ Сообщений: 4 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group