Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 21.04.2010, 22:08
Новичок

Отправить личное сообщение для ben_joyce Посмотреть профиль Найти все сообщения от ben_joyce
 
Регистрация: 21.04.2010
Сообщений: 2

Быстрый метод нахождения числа пар точек, находящихся ближе r друг от друга
Всех приветствую!

Задача: есть трёхмерный массив из ~160 000 точек (в трёхмерном пространстве). Необходимо посчитать число пар точек, находящихся на расстоянии меньше некоторого r (например 0,1). Растояние между точками задано Ro(т1, т2) = Max(|т1[1] - т2[1]|, |т1[2] - т2[2]|, |т1[3] - т2[3]). То есть нужно получить количество пар точек в массиве, для которых Ro < r.
Проблема в том, что при полном переборе точек в массиве выполняется 160 000 * 160 000 * 3 операций сравнения.

Есть ли известный алгоритм, позволяющий ускорить вычисления?

Следующее усовершенствование полного перебора ускорило вычисления в ~2 раза:
1. Произвожу сортировку по первой координате. Получаем отсортированный массив х.
2. i = 0, S = 0
3. X = x[i]
4. S = S + SUM(H[Ro(X, x[j]) < r]), для |X[1] - x[j][1]| < r j=i..N. H = 1, когда Ro < r, в противном случае 0.
5. Увеличиваем i = i + 1. И повторяем шаги 3, 4 пока i < N

Количество необходимых сравнений уменьшаяется из-за отсутствия необходимости сравнивать точки, которые уже по первой координате не удовлетворяют условию близости. Но все же алгоритм выполняется слишком долго.

Буду рад, если вы предложите более эффективный алгоритм.
Заранее благодарен!
  #2  
Старый 22.04.2010, 01:34
гость

 
Сообщений: n/a

Ну, есть такая структурка - range tree.

Обычно рассматривают ее двухмерный вариант, на плоскости. Там она позволяет для любого прямоугольника [x1, x2] x [y1, y2] за O(log^2 n) времени (кажется) и O(n log n) памяти посчитать число точек попадающих в него.

Структуру наверняка можно обощить на трехмерный случай. Тоже будет где-то логарифмическая сложность запроса, думаю.
  #3  
Старый 22.04.2010, 01:35
гость

 
Сообщений: n/a

Сообщение от гость Посмотреть сообщение
Структуру наверняка можно обощить на трехмерный случай. Тоже будет где-то логарифмическая сложность запроса, думаю.
имеет смысл гуглить что-то вроде "3d range tree"
  #4  
Старый 22.04.2010, 08:00
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

Равномерное ли распределение точек в пространстве и как соотносится r с размером облака точек?
  #5  
Старый 23.04.2010, 00:04
Новичок

Отправить личное сообщение для ben_joyce Посмотреть профиль Найти все сообщения от ben_joyce
 
Регистрация: 21.04.2010
Сообщений: 2

Сообщение от MBo Посмотреть сообщение
Равномерное ли распределение точек в пространстве и как соотносится r с размером облака точек?
Точки распределены равномерно. r достаточно мало, приблизительно 0,1% от размера облака.
  #6  
Старый 23.04.2010, 00:29
гость

 
Сообщений: n/a

Сообщение от ben_joyce Посмотреть сообщение
Точки распределены равномерно. r достаточно мало, приблизительно 0,1% от размера облака.
тогда можно воспользоваться еще kD-деревьями. Потребляют линейный объем памяти, пишутся проще чем range tree, но сложность запроса как минимум пропорциональна числу точек в ответе.
  #7  
Старый 23.04.2010, 06:38
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

>Точки распределены равномерно. r достаточно мало, приблизительно 0,1% от размера облака.

Тогда, если память есть, можно простейшее пространственное индексирование использовать - трехмерный массив с кубической ячейкой размером r. В каждой ячейке хранится список индексов точек, которые в нее попадают. Точки из одной ячейки - заведомо парные, кроме того, проверяются 26 соседних.
Ячеек по стороне L/r, где L - наибольший размер облака всего (L/r)^3, в одной ячейке в среднем N*(r/L)^3 точек, всего проверок 26*N^2 * (r/L)^3.
  #8  
Старый 28.04.2010, 19:53
Новичок

Отправить личное сообщение для Вальтер Посмотреть профиль Найти все сообщения от Вальтер
 
Регистрация: 28.04.2010
Сообщений: 1

Сообщение от MBo Посмотреть сообщение
>
Тогда, если память есть, можно простейшее пространственное индексирование использовать - трехмерный массив с кубической ячейкой размером r.
Мне кажется, размер ячейки равен r / 3^0.5, т.к. расстояние между противороложными углами куба со стороной r равно r*3^0.5 и не все точки в такой ячейке будут соседями.
  #9  
Старый 28.04.2010, 21:47
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

Вальтер, посмотрите, как "расстояние" в первом посте задано
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Математические алгоритмы, Метод Рунге_Куты и метод Эйлера для решения задач Коши TokiMoki Математические алгоритмы (другое) 0 26.03.2010 11:14
Подскажите алгоритм нахождения остатка от деления AsDf Криптография 5 23.04.2009 18:21
Алгоритм Уоршелла для нахождения транзитивного замыкания. ioioio Реализация, исходники, языки 1 20.05.2008 23:31
Быстрый алгоритм нахождения макспотока.. maksay Графы 4 11.12.2007 02:16
численные методы нахождения целичесленных решений dabeat_bf Математические алгоритмы 1 29.01.2007 14:32