Есть множество точек на плоскости.. нужно организовать быстрый поиск точки ближайшей к заданной.
Тупой перебор всех точек и вычисление расстояния от каждой до заданной — требует N операций где N — число точек. Интуиция подсказывает что должно быть решение Log N.. ссылочки кто нить не подскажет?

Здравствуйте, barn_czn, Вы писали:

_>Есть множество точек на плоскости.. нужно организовать быстрый поиск точки ближайшей к заданной.
_>Тупой перебор всех точек и вычисление расстояния от каждой до заданной — требует N операций где N — число точек. Интуиция подсказывает что должно быть решение Log N.. ссылочки кто нить не подскажет?


Я бы сказал, что не N а значительно больше C*N, где С = 4. Я полагаю, что алгоритм можно существенно упростить, просто проведя предварительный отбор точек сравнением координат 2*N и только после этого вычислять растояния для небольшого количества точек. Возможно есть более лучшие способы, но мне о них не приходилось слышать.

Здравствуйте, SteMage, Вы писали:

SM>Я бы сказал, что не N а значительно больше C*N, где С = 4.
Количество операцией все равно измеряют с точностью до константы. Так что это одно и то же.

Здравствуйте, barn_czn, Вы писали:

_>Есть множество точек на плоскости.. нужно организовать быстрый поиск точки ближайшей к заданной.
Ускорить можно при условии, что набор точек фиксированный, а количество операций поиска для него велико. Ключевое слово здесь -- диаграмма Вороного. Почитать по нее можно в книге Препарата, Шеймос "Вычислительная геометрия: введение". Посмотрите еще здесь:
http://algolist.netimperia.com/maths/geom/index.php

Здравствуйте, barn_czn, Вы писали:

_>Есть множество точек на плоскости.. нужно организовать быстрый поиск точки ближайшей к заданной.
_>Тупой перебор всех точек и вычисление расстояния от каждой до заданной — требует N операций где N — число точек. Интуиция подсказывает что должно быть решение Log N.. ссылочки кто нить не подскажет?

ANN Approximate Nearest Neighbour, там реализации различных методов.

Здравствуйте, Mab, Вы писали:

Mab>Здравствуйте, SteMage, Вы писали:

SM>>Я бы сказал, что не N а значительно больше C*N, где С = 4.
Mab>Количество операцией все равно измеряют с точностью до константы. Так что это одно и то же.

Константа то же имеет значение . Не верите смотрите статью о преждевременной оптимизации на RSDN. А о том как измеряется сложность алгоритма я в курсе. Лично у меня после просмотра предложенных вариантов сложилась впечатление, что если операцию сравнения считать за операцию, то никуда мы от N не уходим. Все равно мы в том или ином виде выполняем операцию сравнения для всех точек. Хотя это конечно офтоп, поскольку вопрос был о ссылках.

Здравствуйте, SteMage, Вы писали:
SM>А о том как измеряется сложность алгоритма я в курсе.

Раз так, то понимаете, что поправка
SM>Я бы сказал, что не N а значительно больше C*N, где С = 4
никакого точного смысла не имеет, т.к. зависит от того, что считать элементарной операцией. Все это, конечно, не исключает возможности того, что нахождение ближайшей точки можно сделать быстрее (с точностью до константы), чем вычислением расстояний. Например, можно использовать нижнюю оценку через манхэттенскую норму, которая вычисляется быстрее, чем эвклидова. Но автора вопроса интересовала существенно лучшая асимптотика, а не ускорение линейного алгоритма.

Здравствуйте, Mab, Вы писали:

Mab>Здравствуйте, SteMage, Вы писали:
SM>>А о том как измеряется сложность алгоритма я в курсе.

Mab>Раз так, то понимаете, что поправка
SM>>Я бы сказал, что не N а значительно больше C*N, где С = 4
Mab>никакого точного смысла не имеет, т.к. зависит от того, что считать элементарной операцией. Все это, конечно, не исключает возможности того, что нахождение ближайшей точки можно сделать быстрее (с точностью до константы), чем вычислением расстояний. Например, можно использовать нижнюю оценку через манхэттенскую норму, которая вычисляется быстрее, чем эвклидова. Но автора вопроса интересовала существенно лучшая асимптотика, а не ускорение линейного алгоритма.

Да я неправильно выразился в поправке. Должен признать оплошность.