|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Stanislav Shwartsman 2:400/520 22 Jan 2002 20:16:25
To : Antony Victoroff
Subject : Поиск ближайшей точки с координатами (x,y).
--------------------------------------------------------------------------------
22 Jan 02 13:34, you wrote to me:
TA>>>> Имеется массив координат точек.
TA>>>> Трубуется найти ближайшую точку из этого массива (номер
TA>>>> элемента)
TA>>>> к зананной точке (например с координатами x0,y0).
TA>>>> Как это сделать наиболее быстрым способом?
D>>> Построить триангуляцию Делоне (O(N*logN)), получить по ней
D>>> полигоны
D>>> Вороного (O(N)?) /*а можно и не получать?*/, найти полигон,
D>>> которому
D>>> будет принадлежать заданная точка (O(N)). Итого: O(N*logN) ---
D>>> быстрее
D>>> не получится.
SS>> А просто измерить расстояние между заданной точкой и всеми
SS>> точками массива O(N) уже не прокатит ?
AV> это неинтересный подход. ненаучный :) и долгий. а если надо постоянно
AV> искать ближайших соседей ? :))
А если не нужно постоянно ничего искать ?
Посмотри начальное условие задачи !
AV> тады можно использовать память O(N),
AV> затратив время O(NlogN) на предобработку и потом искать ближайшего
AV> соседа за время всего-то O(logN). во как. опять же используя
Уметь надо не воротить горы ненужных алгоритмов и наворотов, когда
задача этого не требует. Или ты будешь утверждать, что O(N log N)
круче, чем O(N) ? ;)))
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 |
|
|
