Регіональний пошук для множини рухомих точок
В роботі запропоновано структури даних у вигляді Вх-дерев для побудови ефективних алгоритмів регіонального пошуку на множині рухомих точок в евклідовому просторі Ed. В работе предложены структуры данных в виде Вх-деревьев для построения эффективных алгоритмов регионального поиска на множестве движущ...
Saved in:
| Published in: | Математичні машини і системи |
|---|---|
| Date: | 2011 |
| Main Authors: | , |
| Format: | Article |
| Language: | Ukrainian |
| Published: |
Інститут проблем математичних машин і систем НАН України
2011
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/83514 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Регіональний пошук для множини рухомих точок / В.М. Терещенко, С.Є Скляровський // Мат. машини і системи. — 2011. — № 2. — С. 73-80. — Бібліогр.: 5 назв. — укр. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859640432991928320 |
|---|---|
| author | Терещенко, В.М. Скляровський, С.Є. |
| author_facet | Терещенко, В.М. Скляровський, С.Є. |
| citation_txt | Регіональний пошук для множини рухомих точок / В.М. Терещенко, С.Є Скляровський // Мат. машини і системи. — 2011. — № 2. — С. 73-80. — Бібліогр.: 5 назв. — укр. |
| collection | DSpace DC |
| container_title | Математичні машини і системи |
| description | В роботі запропоновано структури даних у вигляді Вх-дерев для побудови ефективних алгоритмів регіонального пошуку на множині рухомих точок в евклідовому просторі Ed.
В работе предложены структуры данных в виде Вх-деревьев для построения эффективных алгоритмов регионального поиска на множестве движущихся точек в эвклидовом пространстве Ed.
A modification of data structures in the form of Bx-trees for constructing effective algorithms of regional search on the set of moving points in Euclidean space Ed is proposed.
|
| first_indexed | 2025-12-07T13:20:58Z |
| format | Article |
| fulltext |
© Терещенко В.М., Скляровський С.Є., 2011 73
ISSN 1028-9763. Математичні машини і системи, 2011, № 2
УДК 004.519.712 +004.92
В.М. ТЕРЕЩЕНКО, С.Є. СКЛЯРОВСЬКИЙ
РЕГІОНАЛЬНИЙ ПОШУК ДЛЯ МНОЖИНИ РУХОМИХ ТОЧОК
Анотація. У роботі запропоновано структури даних у вигляді Вх-дерев для побудови ефективних
алгоритмів регіонального пошуку на множині рухомих точок в евклідовому просторі Ed.
Ключові слова: структури даних, регіональний пошук, Вх-дерево, множина рухомих точок.
Аннотация. В работе предложены структуры данных в виде Вх-деревьев для построения эффек-
тивных алгоритмов регионального поиска на множестве движущихся точек в эвклидовом про-
странстве Ed.
Ключевые слова: структуры данных, региональный поиск, Вх-дерево, множество движущихся
точек.
Abstract. A modification of data structures in the form of Bx-trees for constructing effective algorithms of
regional search on the set of moving points in Euclidean space Ed is proposed.
Keywords: data structures, regional search, Bx-tree, set of moving points.
1. Вступ
Постановка проблеми. Однією із важливих задач обчислювальної геометрії є задача
регіонального пошуку для множин рухомих точок. Вона має широке застосування в
системах обробки інформації в реальному часі, системах моніторингу, системах
управління базами даних, системах балансування навантажень на мережах. У роботі
розглядаються ефективні підходи до представлення й обробки множини рухомих точок
(об’єктів) та застосування відповідних структур даних в алгоритмах регіонального
пошуку. Проте ця задача є малодослідженою, за винятком окремих випадків для
фіксованих регіонів пошуку та малої розмірності простору (задачі на площині та в
тривимірному просторі). Це пов’язано, перш за все, з динамічністю системи, по-друге, з
слабо розробленими моделями представлення динамічних даних реального часу в
обчислювальних машинах.
Аналіз останніх досліджень. На сьогоднішній день для розв’язання задачі
регіонального пошуку на множині рухомих точок використовують два основних підходи,
які ґрунтуються на структурах даних типу збалансованих дерев. Перший підхід, відомий
як підхід без урахування часу [1, 2], представляє час як додатковий вимір простору,
зберігає й працює з траєкторіями рухомих точок. Перевага даного підходу в тому, що
структури даних, які він використовує, змінюються лише при зміні траєкторії точки або
при додаванні чи видаленні точки. Недолік даного підходу очевидний: через використання
простору більшої розмірності зростає час запиту [2]. В основі другого підходу [1, 6]
лежить використання кінетичних структур даних [4] та динамічних дерев для рухомих
точок. Він підтримує структуру даних у реальному часі: коли точки рухаються, структура
змінюється. Не дивлячись на те, що точки рухаються неперервно, структура даних
оновлюється лише в певні дискретні моменти часу, коли відбуваються деякі події,
наприклад, коли координати деяких двох точок співпадають. Такий підхід дає ефективний
час пошуку, проте потребує перебудови структури, навіть якщо траєкторія жодної точки
не змінилась. Ще одним недоліком даного підходу є те, що він дає можливість відповідати
лише на запити щодо поточної конфігурації точок. Звісно, можна використовувати
перебудови для отримання результатів запитів з майбутнього, але при цьому до часу
запиту додається час перебудови структури. Зазначимо, відповідно до робіт [1, 4, 6], що
якщо множина S складається з n точок в 1ℜ , то, використовуючи кінетичні В-дерева,
74 ISSN 1028-9763. Математичні машини і системи, 2011, № 2
можна отримати результати запиту за час )(log knO + , де k – кількість точок, що
потрапляють у запитний регіон. Перебудова структури даних здійснюється для )( 2nO
подій, кожна перебудова потребує )(lognO часу. При зміні розмірності зростає лише час
перебудови. Наприклад, для 2ℜ він складає )(log2 nO , але, як зазначено в роботі [6],
використовуючи бінарний пошук, його можна зменшити до часу )
loglog
log
(
2
n
n
O .
З практичної точки зору, використання В-дерев досить складне. Можна
використовувати dk − -дерева, не дивлячись на те, що їх використання залишає пошуковий
час незмінним, але загальний час погіршується, так як dk − -дерева потребують більше
перебудов, ніж В-дерева [3, 5, 6].
Зазначимо, що в загальній постановці (без суттєвих обмежень на функції руху,
пошукові регіони та розмірність простору) задача є малодослідженою. Всі відомі
алгоритми дозволяють виконувати регіональний пошук лише при умові, що закони руху
об’єктів лінійно залежать від часу [1]. В роботах [5, 6] розглядаються варіанти нелінійного
руху, але отримані результати мають теоретичний характер, так як клас нелінійних
функцій руху, що розглянуто, дуже вузький. В роботах [1, 4, 6] визначено обчислювальну
складність розв’язків даної задачі в просторах розмірності більше трьох та вказано оцінки
пам’яті, що дозволяють будувати ефективні пошукові алгоритми. На основі розв’язків
даної геометричної задачі в роботах [4–6] розглянуто можливе використання відповідних
алгоритмів обчислювальної геометрії для побудови ефективних алгоритмів та структур
даних для обробки швидкоплинної інформації в дискових системах управління базами
даних.
Новизна та ідея. В роботі запропоновано модифікацію існуючих підходів для
випадку евклідового d -вимірного простору ( )2≥d шляхом побудови структур даних, що
дозволяють ефективно використовувати дискову пам’ять, зменшуючи кількість операцій
читання-запису та зберігаючи в оперативній пам’яті лише невелику кількість сторінок
даних.
Мета роботи. Розробка ефективної модифікації алгоритмів регіонального пошуку
для множини рухомих точок у двовимірному просторі та відповідних структур даних в
евклідовому d-вимірному просторі ( )2≥d .
2. Побудова розв’язку задачі регіонального пошуку для множини рухомих точок
Нехай { }npppS ,...,, 21= – множина з n точок у просторі 2ℜ , кожна з яких перебуває у
неперервному русі. Нехай )(tpi положення точки i в момент часу t , а
( ) ( ) ( ) ( ){ }tptptptS n,...,, 21= – множина точок у момент часу t . Припустимо, що кожна точка
рухається з постійною швидкістю, тобто tbatp iii +=)( , де 2, ℜ∈ii ba , а траєкторія кожної
точки є відрізком ip . Нехай задано запитний регіон R (паралелепіпед) і L – множину
відрізків, що відповідають траєкторіям точок з S . Необхідно для заданого регіону R та
відповідного часу запиту qt знайти всі точки з множини S , які знаходяться всередині
регіонуR у час qt , тобто знайти ( ) RtS q ∩ .
2.1. Структури даних
Множину рухомих точок будемо представляти у вигляді Вх-дерева, яке, у свою чергу, є
розвиненням ідеї пошукового В-дерева. З точки зору зовнішнього логічного представлен-
ня, Вх-дерево – збалансоване, дуже гіллясте, може зберігатись у зовнішній пам’яті. Збалан-
ISSN 1028-9763. Математичні машини і системи, 2011, № 2 75
Рис. 1. Приклад Вх-дерева
сованість означає, що довжина шляху від кореня дерева до будь-якого з листів однакова.
Гіллястість дерева – властивість кожного вузла дерева посилатись на велику кількість вуз-
лів-нащадків. З точки зору фізичної організації, Вх-дерево представляється як мультиспис-
кова структура сторінок зовнішньої пам’яті, тобто кожному вузлу дерева відповідає блок
зовнішньої пам’яті (сторінка). Внутрішні та листові сторінки мають різну структуру.
Застосування модифікованих В-дерев зумовлено логарифмічними оцінками основ-
них операцій та пристосованістю В-дерев для обробки великої кількості даних, об’єм яких
може бути настільки великим, що унеможливлює зберігання цих даних в оперативній
пам’яті.
Покажемо, що ми маємо справу саме з великими об’ємами даних. Будь-яку задачу
над множиною рухомих точок (динамічну задачу) можна подати як набір статичних задач.
Для цього достатньо спроектувати нашу задачу на вісь часу й розглядати кожну проекцію
окремо. У випадку регіонального пошуку часова оцінка не погіршиться, так як для задано-
го пошукового регіону та часу буде розглядатися не більше, ніж 3 проекції, а задача на
проекції є звичайною пошуково-регіональною задачею, для якої відомі оцінки складності
та алгоритми, що їх забезпечують. Але оцінка пам’яті у випадку використання проекцій
дуже зростає і стає рівною ( )
⋅
∆
)( 0tNM
t
T
O , де
t
T
∆
– кількість проекцій, а ( ))( 0tNM – оці-
нка необхідної пам’яті для статичної задачі. Отже, виникає ідея застосувати Вх-дерева для
представлення відповідної великої кількості даних більш ефективно, але залишивши лога-
рифмічними часові оцінки складності. Опишемо більш детально структуру Вх-дерева.
Означення. Вх-деревом будемо називати дерево з одним коренем:
1. Кожна вершина x містить поля, в яких зберігаються:
а) кількість [ ]xn ключів, що містяться у вершині;
б) ключі [ ] [ ] [ ][ ]xkeyxkeyxkey xn≤≤≤ ...21 (у неспадному порядку).
2. Якщо x – внутрішня вершина, то вона містить [ ] 1+xn вказівників
[ ] [ ] [ ] [ ]xcxcxc xn 121 ,...,, + на її нащадків. У листків діти відсутні, тому відповідні поля для них
не визначені.
3. Ключі [ ]xkeyi служать границями, що розділяють значення ключів у піддеревах:
k1 ≤ key1[x] ≤ k1 ≤ key2 [x] ≤ … ≤ keyn[x][x]≤ kn[x]+1 ,
де ik – довільний з ключів, що зберігається в піддереві з коренем [ ]xci .
4. Усі листки знаходяться на однаковій глибині, яка дорівнює висоті дерева.
5. Кількість ключів, що містяться в одній вершині, обмежена зверху та знизу; гра-
ниці задаються єдиним для всього дерева числом 2≥m , яке називається мінімальним сту-
пенем вершини Вх-дерева. А саме:
а) кожна вершина, за виключенням кореня, містить, принаймні, 1−m ключів. Та-
ким чином, внутрішні вершини (крім кореня) мають не менше, ніж m дітей. Якщо дерево
не є порожнім, то в корені повинен зберігатись, принаймні, один ключ;
б) у вершині зберігається не більше, ніж 12 −m ключів. Відповідно, внутрішня ве-
ршина має не більше, ніж m2 дітей. Вер-
шину, в якій зберігається рівно 12 −m
ключів, будемо називати повною.
На рис. 1 показано приклад Вх-
дерева для випадку 3=m . Усі ключі збері-
гаються в листках, там же зберігається ін-
формаційна частина вузла. У внутрішніх
вузлах зберігаються лише копії ключів, які
76 ISSN 1028-9763. Математичні машини і системи, 2011, № 2
необхідні для ефективного пошуку потрібного листка. Причому лівий вказівник веде до
ключів, які менші заданого, правий – до ключів, які не менші за заданий. Варто звернути
увагу на те, що, наприклад, ключ 22 повторюється в листку, де зберігаються відповідні
йому дані. Під час вставки або видалення необхідно коректно модифікувати батьківські
вузли. Коли ключ, що модифікується, перший у листі, здійснюється прохід по дереву від
листа до кореня. Останній із вказівників, що не менший за даний, знайдений при спуску по
дереву, є той, який необхідно модифікувати, щоб відобразити нове значення ключа. Оскі-
льки усі ключі повторюються в листках, можна прошити (зв’язати) їх для послідовного до-
ступу.
2.2. Основні операції на структурі
Операції на Вх-деревах аналогічні операціям на В-деревах, які, у свою чергу, є просто роз-
виненням операцій на бінарних деревах, з урахуванням більшої кількості дітей та специфі-
ки вказівників. Розглянемо їх більш детально.
Розбиття вершини Вх-дерева на дві. Додавання елемента в Вх-дерево – більш скла-
дна операція у порівнянні з бінарними деревами. Ключовим моментом є розділення повної
вершини y з 12 −m ключами на дві з 1−m ключами в кожній. При цьому ключ-медіана
][ykeym відправляється до батька x вершини y та стає роздільником отриманих двох ве-
ршин. Це можливо, якщо вершина x – неповна. Якщо y – корінь, процедура виконується
аналогічно. В цьому випадку висота дерева збільшується на одиницю.
Додавання вершини Вх-дерева. Додавання елемента в Вх-дерево проходить у два
етапи. Спочатку здійснюється пошук вершини, до якої додається задана. Далі, якщо ця ве-
ршина неповна, виконується додавання, в іншому випадку вершина розчіплюється на дві й
виконується додавання до відповідної щойно одержаної вершини. Процедура видалення
аналогічна відповідній процедурі для бінарних дерев з урахуванням більшої кількості ді-
тей кожної вершини.
Представлення рухомих точок у Вх-дереві. Так як Вх-дерево представляє кінетичну
(динамічну) структуру даних, то рухомі точки представляються в Вх-дереві як листки з їх
поточними координатами. Всі проміжні вершини представляють собою прошиті інтервали,
кожний з яких містить впорядкований список точок по іншій координаті (у тривимірному
випадку – список списків) аналогічно структурі дерева регіонів. Кожна проміжна вершина
також містить упорядковані списки подій, які характеризують часові точки перетину трає-
кторій рухомих точок та впорядковані списки подій, які характеризують перехід рухомої
точки в сусідній інтервал. Зауважимо, що кожна поточна вершина може містити не більше,
ніж nn +2 подій.
Процедура впорядкування Вх-дерева. Так як корінь Вх-дерева містить упорядкований
список з усіх подій, причому цей список не містить подій, які вже відбулись, то для визна-
чення гілок дерева, які необхідно перевпорядкувати, переглянемо цей список, починаючи з
першої мітки, до мітки, яка більша за поточний час. Кожна поточна подія вимагає впоряд-
кування відповідної їй гілки дерева. Для поточної події, що відповідає перетину траєкторій
точок, виконується перестановка відповідних точок місцями у впорядкованих списках (так
як подія полягає в зміні порядку точок). Для події, що характеризує перехід точки до сусі-
днього інтервалу, необхідно виконати перенаправлення вказівників на дану точку з поточ-
ної гілки до гілки, що характеризує інтервал, в який потрапляє точка, видалення точки зі
списків старої гілки та додавання до списків нової гілки.
Пошуковий регіональний запит до Вх-дерева. Пошуковий регіональний запит повер-
тає всі рухомі точки, що попадають у пошуковий регіон q , який є паралелепіпедом, у за-
питний час qt . Для виконання цього запиту достатньо виконати звичайний регіональний
ISSN 1028-9763. Математичні машини і системи, 2011, № 2 77
запит до Вх-дерева, яке в даному контексті можна вважати деревом регіонів. Зазначимо,
що перед виконанням пошукового запиту потрібно виконати процедуру впорядкування
дерева.
2.3. Побудова розв’язку задачі регіонального пошуку для множини рухомих точок
Алгоритм розв’язку задачі регіонального пошуку складається з двох основних моментів: з
попередньої обробки рухомих точок та основного алгоритму.
2.3.1. Попередня обробка рухомих точок
На етапі попередньої обробки виконується побудова для заданих рухомих точок Вх-дерева,
визначаються списки подій для перебудови дерева й прошиваються відповідні інтервали.
Опишемо більш конструктивно етап попередньої обробки:
1. Для заданих рухомих точок будуємо впорядковані по відповідній координаті спи-
ски точок.
2. На основі одного впорядкованого списку будуємо дерево, яке відповідає дереву
регіонів, але інтервали ділимо не бінарно, а на m частин, до кожної вершини пришиваємо
впорядковані списки вершин за іншими координатами, які отримуються як елементарна
вибірка зі списків, отриманих на першому кроці.
3. Знаходимо впорядкований за часом список подій типу перетин інтервалу для ко-
жної точки та кожного інтервалу дерева, а саме: для кожної точки знаходимо час, в який
вона вийде зі свого інтервалу й перейде у сусідній. Прошиваємо відповідні події до відпо-
відного інтервалу (інтервалу, з якого точка буде переходити). Під подією розуміємо трій-
ку: час події, рухома точка та напрямок переходу (в лівий чи правий інтервал). Зазначимо,
що для задачі спостереження в реальному часі додаються події виходу точок за межі поля
зору.
4. Знаходимо впорядкований за часом список подій типу перетин траєкторій для
кожної пари точок. А саме, визначаємо з закону руху точок (нагадаємо, що закони лінійні
відносно часу) точку перетину траєкторій, розв’язуючи систему лінійних рівнянь. Зазна-
чимо, що система має вигляд:
+=+
+=+
2211
2211
ytbytb
xtaxta
,
де невідомою змінною є лише t . Для кожної такої події визначаємо інтервал, в якому вона
відбудеться, та зв’язуємо її з вершиною дерева відповідного інтервалу.
Після виконання зазначених вище 4 кроків отримуємо пошукове дерево в початко-
вий момент часу. Опишемо попередню обробку на прикладі двовимірного простору та
двох рухомих точок. Нехай задано дві рухомі точки: ( ) ( )( )1,1,0,0=A та ( ) ( )( )2,2,1,10 −−=B ,
тобто точки в початковий момент часу знаходяться за координатами ( )0,0 та ( )1,10 − , ру-
хаються у напрямку векторів ( )1,1 та ( )2,2− , причому перша рухається зі швидкістю 2 , а
друга – зі швидкістю 2. Тобто закони руху точок ( )tt, та ( )12,102 −+− tt , а траєкторії ру-
хомих точок – відповідні промені прямих xy = та
4
6 x
y
−= . Впорядкуємо точки за зна-
ченням абсциси у список { }BAU x ,= , за ординатами – у список { }ABU y ,= . Так як дерево-
основа є дерево регіонів для інтервалу [ ]10,0 з двома точками, то воно матиме вигляд (рис.
2) (так як точок лише 2, то немає сенсу розглядати дерево з 2>m ).
78 ISSN 1028-9763. Математичні машини і системи, 2011, № 2
[0,10]
[0,5] [6,10]
A B
{B,A}
{A} {B}
( ) ( ){ }RALB ,,6,,,3
( ){ }LB,,3 (3,A,B) ( ){ }RA,,6
Рис. 2. Дерево-основа
Відповідно до даного спис-
ку припишемо першу подію до ін-
тервалу [ ]10,6 , а другу подію – до
інтервалу [ ]5,0 , загальний список
запишемо в корінь дерева.
Знайдемо впорядкований за часом
список подій типу перетин траєк-
торій рухомих точок. В даному
випадку він складається з однієї
події (тому що точок 2), для ви-
значення якої прирівняємо закони руху і знайдемо з системи з 2 рівнянь та 1 змінної час t
=11/4=3 (зазначимо, розв’язок знаходимо з одного рівняння, а друге слугує для перевірки,
якщо знайдений розв’язок не задовольняє друге рівняння, траєкторії точок не перетина-
ються). Так як час у нас квантується одиницею (дискретний запитний час), то точки помі-
няють свій порядок лише в можливий запитний момент 3=t . Визначаємо інтервал, в яко-
му точки змінять порядок, це інтервал [ ]5,0 . Зв’язуємо подію з цим інтервалом та посилан-
ня до цієї події на точки A та B . Зв’язуємо також подію з усіма вершинами верхнього рів-
ня (в нашому випадку кореня). Одержимо бажане нам дерево пошуку.
2.3.2. Основний цикл алгоритму
Основний цикл алгоритму складається з послідовного виконання операцій впорядкування
дерева та виконання запиту:
1. Впорядкування дерева (згідно з розд. 2.4). Для впорядкування дерева спочатку пе-
реглядаємо список подій типу перетин траєкторій, який знаходиться у корені дерева. Так
як список впорядкований за часом подій, то достатньо переглянути події, час яких менший
за поточний. Нехай поточний час 5=t , і в списку є одна подія для заданого часу. Нехай
вона має вигляд ( )21,,5 AA . Тоді видаляємо цю подію зі списку та переставляємо точки 1A
та 2A місцями у списках впорядкування за координатами, що зв’язані з інтервалом, в яко-
му відбувається подія і з яким, у свою чергу, зв’язана подія ( )21,,5 AA . Далі переглядаємо
список подій типу перетин інтервалу, який зв’язаний з коренем дерева. Нехай для заданого
часу є одна подія типу перетин інтервалу ( )LA ,,5 1 , зв’язана з відповідним інтервалом I ,
який рухома точка 1A перетне з лівого кінця. Для обробки цієї події видаляємо її зі списку
подій, видаляємо точку 1A зі списків впорядкування за координатою в інтервалі I та дода-
ємо до списків впорядкування за координатою в інтервал LI , який є найближчим лівим су-
сідом інтервалу I і знаходиться на одному рівні з ним. Переносимо зв’язок точки 1A з ін-
тервалу I в інтервал LI (додаємо до списку вершин, що містяться в ньому). Після обробки
цих двох списків дерево відповідає дереву пошуку в поточний момент часу, що дозволяє
обробляти пошуковий запит.
2. Пошуковий запит (згідно з розд. 2.5). Нехай задано пошуковий регіон
),,,( 2211 yxyxq = . Здійснюємо спуск по дереву до вершин, інтервали яких перетинаються з
інтервалом [ ]21, xx , для кожного такого інтервалу найнижчого рівня (не рахуючи рівень ли-
стів-точок) перевіряємо, відповідно до списку впорядкованих за координатами точок, на-
лежність точок запитному регіону та формуємо відповідь. Тобто, з точки зору пошуку, де-
рево, що розглядається, є звичайним деревом регіонів.
ISSN 1028-9763. Математичні машини і системи, 2011, № 2 79
Рис. 3. Залежність часу пошуку
від розмірності задачі
3. Обґрунтування складності
Теорема 1. Часова оцінка складності розв’язку задачі регіонального пошуку для множини
з n рухомих точок у просторі dℜ становить ( )nO dlog операцій, за умови, що ( )nnO dd log
операцій необхідно для попередньої побудови кінетичної структури даних (у початковий
момент часу) та в процесі роботи для ( )2nO подій відбувається впорядкування структури,
яке складає ( )nO dlog операцій.
Доведення. Часова оцінка пошуку є тривіальною, так як являє собою оцінку пошуку
статичної задачі регіонального пошуку для пошукового регіону типу паралелепіпед, яка
виконується методом регіонального дерева. Оцінка часу попередньої обробки побудови
кінетичної структури даних у початковий момент часу теж тривіальна (побудова В-дерева,
доведення часової оцінки побудови приведені в роботах [3, 4]). Так як впорядкування
структури відбувається лише в моменти перетину траєкторій рухомих точок, зрозуміло,
що впорядкування потрібно виконати ( )2nO в найгіршому випадку, при умові попарного
перетину всіх траєкторій. Остання оцінка слідує з властивостей побудованого В-дерева.
Так як кожна перебудова представляє перечеплення місцями всіх дітей для гілки дерева,
листками якої є точки, траєкторії яких перетнулись у поточний момент часу, з урахуван-
ням збалансованості дерева, прохід по гілці дерева потребує часу, пропорційного висоті
дерева, і, з урахуванням константного часу операції, перечеплення складає ( )nO dlog .
Теорема 2. Мінімальна часова оцінка складності розв’язку задачі регіонального пошуку на
множині з n рухомих точок у просторі dℜ дорівнює ( )ndlogΩ .
Доведення. Для зведення задачі регіонального пошуку на множині рухомих точок
(динамічної задачі регіонального пошуку – ДЗРП) до задачі регіонального пошуку на ста-
тичній множині точок (статичної задачі регіонального пошуку – СЗРП) розглянемо проек-
ції ДЗРП на вісь часу. Тоді пошуковий запит ДЗРП представляє звичайний регіональний
пошуковий запит типу паралелепіпед на деякій часовій проекції ДЗРП. Відповідно до ре-
зультатів [1], мінімальна часова оцінка складності розв’язку СЗРП у просторі dℜ для
множини з n точок та пошукового регіону типу паралелепіпеда складає ( )ndlogΩ . Зрозу-
міло, що перетворення звідності лінійне, так як кожна часова проекція представляє собою
СЗРП, тому для отримання результату достатньо знайти відповідну проекцію серед упоря-
дкованої множини. Очевидно, що такий пошук можна виконати навіть за логарифмічний
час (використовуючи, наприклад, бінарний пошук).
4. Практична частина
Алгоритм реалізовано лише для двовимірного та тривимірного простору, які
представляють на даний момент часу надзвичайний інтерес з практичної точки зору (задачі
моніторингу та балансування навантажень. Зазначимо, що існуючі підходи здебільшого
розглядають лише двовимірний випадок.
Нижче наведено графіки залежності часу
роботи від розмірності задачі для
двовимірного та тривимірного випадків
(рис. 3, 4). Випадки розмірності більше
трьох потребують великих обсягів пам’яті
та в контексті комп’ютерної геометрії не є
показовими (не є наочними).
Звичайно алгоритм та структуру даних реалізовано з урахуванням можливості
поширення на простори розмірності більше трьох.
80 ISSN 1028-9763. Математичні машини і системи, 2011, № 2
Рис. 4. Залежність часу попере-
дньої обробки від розмірності
задачі
В-дерева представляють можливість ефективно будувати
індекси, які використовують зовнішню пам’ять, але в
наведеній реалізації структури даних не використовують
зовнішню пам’ять в початковому сенсі (є припущення,
що кількість точок дозволяє зберігати все дерево в
оперативній пам’яті). У випадку багатовимірних
просторів в оперативній пам’яті зберігається кожне
дерево зі списками подій та посиланнями на область
зовнішньої пам’яті, яка містить структуру дерева
кожного вузла. Подібна реалізація описана в [4, 6]. Зазначимо, що через відсутність
готових реалізацій інших підходів практичне порівняння результатів і продуктивності не
проводилось.
5. Висновки
У роботі запропоновано метод розв’язання задачі регіонального пошуку для множини
рухомих точок, заснований на поєднанні статичних регіональних дерев та В-дерев, що
дало змогу ефективно представляти динамічні дані про рухомі точки й ефективно
виконувати регіональний пошук. На відміну від попередніх робіт розглянуто та приведено
реалізацію відповідного підходу для тривимірного простору, що дозволяє поширити
відповідні алгоритми та структури даних на простори більших розмірностей. У роботі
показано проблемні місця в існуючих алгоритмах регіонального пошуку на динамічних
даних та запропоновано метод часткового вирішення проблем, заснований на використанні
оптимізуючих структур даних типу В-дерев, що дозволяють побудову ефективних індексів
і використання зовнішньої пам’яті.
Методом звідності встановлено нижню оцінку складності алгоритмів розв’язання
поставленої задачі та наведено часові оцінки складності запропонованого підходу й оцінки
пам’яті, необхідної для відповідних структур даних. Реалізація підходу, що розглядається
в роботі, демонструє прикладну цінність ефективних алгоритмів розв’язання задачі, а саме
використання в біологічних дослідженнях для спостережень за мікроорганізмами. У цей
час у більшості передових країн світу інформаційно-психологічні засоби здійснення пси-
хологічних операцій розглядаються як пріоритетні при досягненні поставлених цілей. При
цьому дані засоби можуть бути використані як для підтримки психічного здоров'я людини,
так і для впливу на свідомість і психіку як своїх військ і населення, так і військ і населення
потенційного супротивника.
СПИСОК ЛІТЕРАТУРИ
1. Agarwal P.K. Indexing moving points / P.K. Agarwal, L. Arge, J. Erickson // J. Comput. Syst. Sci. –
2003. – Vol. 66. – P. 207 – 243.
2. Agarwal P.K. Kinetic medians and kd-trees / P.K. Agarwal, J. Gao, L.J. Guibas // Proc. 10th European
Sympos. Algorithms. – London, 2002. – P. 15 – 26.
3. Guibas L.J. Kinetic data structures – a state of the art report / L.J. Guibas; P.K. Agarwal, L.E. Kavraki,
M. Mason (ed.) // Proc. Workshop Algorithmic Found. Robot. – Wellesley, 1998. – Р. 191 – 209.
4. Procopiuc C.M. Star-tree: An efficient selfadjusting index for moving points / C.M. Procopiuc,
P.K. Agarwal, S. Har-Peled // Proc. 4th Workshop Algorithm Eng. Experiments. – San Francisco, 2002. –
Р. 178 – 193.
5. Indexing the positions of continuously moving objects / S. Saltenis, C.S. Jensen, S.T. Leutenegger [et
al.] // Proc. ACM SIGMOD Internat. Conf. Management Data. – Vancouver, 2008. – P. 331 – 342.
Стаття надійшла до редакції 05.04.2011
|
| id | nasplib_isofts_kiev_ua-123456789-83514 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1028-9763 |
| language | Ukrainian |
| last_indexed | 2025-12-07T13:20:58Z |
| publishDate | 2011 |
| publisher | Інститут проблем математичних машин і систем НАН України |
| record_format | dspace |
| spelling | Терещенко, В.М. Скляровський, С.Є. 2015-06-20T08:35:16Z 2015-06-20T08:35:16Z 2011 Регіональний пошук для множини рухомих точок / В.М. Терещенко, С.Є Скляровський // Мат. машини і системи. — 2011. — № 2. — С. 73-80. — Бібліогр.: 5 назв. — укр. 1028-9763 https://nasplib.isofts.kiev.ua/handle/123456789/83514 004.519.712 +004.92 В роботі запропоновано структури даних у вигляді Вх-дерев для побудови ефективних алгоритмів регіонального пошуку на множині рухомих точок в евклідовому просторі Ed. В работе предложены структуры данных в виде Вх-деревьев для построения эффективных алгоритмов регионального поиска на множестве движущихся точек в эвклидовом пространстве Ed. A modification of data structures in the form of Bx-trees for constructing effective algorithms of regional search on the set of moving points in Euclidean space Ed is proposed. uk Інститут проблем математичних машин і систем НАН України Математичні машини і системи Нові інформаційні і телекомунікаційні технології Регіональний пошук для множини рухомих точок Региональный поиск для множества движущихся точек Regional search for the set of moving points Article published earlier |
| spellingShingle | Регіональний пошук для множини рухомих точок Терещенко, В.М. Скляровський, С.Є. Нові інформаційні і телекомунікаційні технології |
| title | Регіональний пошук для множини рухомих точок |
| title_alt | Региональный поиск для множества движущихся точек Regional search for the set of moving points |
| title_full | Регіональний пошук для множини рухомих точок |
| title_fullStr | Регіональний пошук для множини рухомих точок |
| title_full_unstemmed | Регіональний пошук для множини рухомих точок |
| title_short | Регіональний пошук для множини рухомих точок |
| title_sort | регіональний пошук для множини рухомих точок |
| topic | Нові інформаційні і телекомунікаційні технології |
| topic_facet | Нові інформаційні і телекомунікаційні технології |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/83514 |
| work_keys_str_mv | AT tereŝenkovm regíonalʹniipošukdlâmnožiniruhomihtočok AT sklârovsʹkiisê regíonalʹniipošukdlâmnožiniruhomihtočok AT tereŝenkovm regionalʹnyipoiskdlâmnožestvadvižuŝihsâtoček AT sklârovsʹkiisê regionalʹnyipoiskdlâmnožestvadvižuŝihsâtoček AT tereŝenkovm regionalsearchforthesetofmovingpoints AT sklârovsʹkiisê regionalsearchforthesetofmovingpoints |