|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Dmitriy Goldobin 2:5020/400 10 Jul 2003 12:52:03
To : Serge Nozhenko
Subject : Re: Перетаскивание ребер и вершин. Может попроще сначала задачку?
--------------------------------------------------------------------------------
Hi!
> Ввести линейную упорядоченность типа less((x1, y1), (x2, y2)) = (x1 < x2
||
> x1 == x2 && y1 < y2), и использовать обычные сортировку/бинарный поиск.
точки расположены по окружности, искомая точка близко к ее центру. Чем такая
сортировка поможет? Hачинаешь двигаться по x в обе стороны от искомой, но с
увеличением dx уменьшается dy и получается O(N+logN), поскольку logN нужно
для поиска начальной точки по X. Мне вот и интересно, есть ли способ
добиться меньшего значения для _всех_ случаев, а не для большинства. Для
большинства случаем можно вообще сделать регулярную сетку, в каждой ячейке
которой список точек, которые могут быть ближайшими - в большинстве случаев
можно добиться вообще O(1), но в частных опять же O(N).
попытаюсь разобраться с триангуляцией и с kd-tree. интересно стало.
Bye.
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
