ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Stanislav Shwartsman                 2:400/520      21 Jan 2002  22:57:18
 To : Sergei Shelukhin
 Subject : Поиск ближайшей точки с координатами (x,y).
 -------------------------------------------------------------------------------- 
 

 
 21 Jan 02 20:45, you wrote to All:
 
  TA>> Трубуется найти ближайшую точку из этого массива (номер элемента)
  TA>> к зананной точке (например с координатами x0,y0). Как это сделать
  TA>> наиболее быстрым способом? Интересуют идеи, алгоритмы...
 
  SS> О! У меня похожий вопpос. Только тpебyется выбpать все точки с
  SS> pасстоянием меньше D. Это как-то кpоме тyпого пеpебоpа можно сделать?
 
  Тривиальное док-во того, что быстрее O(N) сделать это все равно не
  возможно если не предположить какой-то дополнительной информации кроме
  указанной выше:
 
  Пусть у тебя есть алгоритм, который за более быстрое время находит все
  точки, которые нужно. Это значит, что на часть точек ты даже ни разу
  не посмотрел (и соответственно не умеешь понятия о том, какие у них
  координаты). А среди этих непроверенных точек запросто может оказаться
  точка, которая удовлетворяет условию (в данном случае с рас-ием < D).
 
  Чтобы получить лучшую скорость как минимум массив точк должен быть
  как-то упорядочен. Без этого - ничего лучше никогда не будет.
 
     E-mail: gate@fidonet.org.il
     Voice Phones: 972-4-8330554 (home), 972-5-4481073 (cell)
 
 Bye !
 Stanislav     (AKA Night's Man)                        [Team Technion]
 ---
  * Origin: Gate From Another World ... From Haifa, Israel (2:400/520)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    Поиск ближайшей точки с координатами (x,y).   Trusov Alexey   21 Jan 2002 19:38:36   Re: Поиск ближайшей точки с координатами (x,y).   Dennis   21 Jan 2002 20:09:23   Re: Поиск ближайшей точки с координатами (x,y).   Yurij Zabelyshynskij   21 Jan 2002 20:23:43   Re[2]: Поиск ближайшей точки с координатами (x,y).   Dennis   21 Jan 2002 21:19:15   Re[3]: Поиск ближайшей точки с координатами (x,y).   Dennis   22 Jan 2002 11:59:02   Re[2]: Поиск ближайшей точки с координатами (x,y).   Ilia Kantor   22 Jan 2002 20:56:12   Re: Re[2]: Поиск ближайшей точки с координатами (x,y).   Nick Kovaliov   23 Jan 2002 10:33:22   Поиск ближайшей точки с координатами (x,y).   Stanislav Shwartsman   21 Jan 2002 21:54:53   Re: Поиск ближайшей точки с координатами (x,y).   Antony Victoroff   22 Jan 2002 14:34:29   Поиск ближайшей точки с координатами (x,y).   Stanislav Shwartsman   22 Jan 2002 20:16:25   Re: Поиск ближайшей точки с координатами (x,y).   Antony Victoroff   23 Jan 2002 18:20:49   Re: Поиск ближайшей точки с координатами (x,y).   Trusov Alexey   25 Jan 2002 18:48:37   Re: Поиск ближайшей точки с координатами (x,y).   Antony Victoroff   28 Jan 2002 00:41:00   Re: Поиск ближайшей точки с координатами (x,y).   Antony Victoroff   22 Jan 2002 11:53:35   Поиск ближайшей точки с координатами (x,y).   Sergei Shelukhin   21 Jan 2002 21:45:02   Поиск ближайшей точки с координатами (x,y).   Stanislav Shwartsman   21 Jan 2002 22:57:18   Re: Поиск ближайшей точки с координатами (x,y).   Dennis   22 Jan 2002 10:50:59   Поиск ближайшей точки с координатами (x,y).   Stanislav Shwartsman   22 Jan 2002 19:23:04   Поиск ближайшей точки с координатами (x,y).   Ilia Kantor   23 Jan 2002 20:27:18   Re: Поиск ближайшей точки с координатами (x,y).   Antony Victoroff   22 Jan 2002 15:06:14   Поиск ближайшей точки с координатами (x,y).   Nickita A Startcev   30 Jan 2002 01:34:28   Re: Поиск ближайшей точки с координатами(x,y).   Andrey Sapozhnikov   30 Jan 2002 20:46:34