Рекурсия и параллельные алгоритмы в задачах геометрического моделирования
Розглянуто ефективний підхід до побудови точних комп’ютерних моделей явищ і процесів. На основі стратегії «поділяй та владарюй» розроблено узагальнений паралельно-рекурсивний алгоритм одночасного розв’язання всієї сукупності взаємозв’язаних задач, які використовують спільно єдину структуру даних (зв...
Saved in:
| Published in: | Кибернетика и системный анализ |
|---|---|
| Date: | 2010 |
| Main Authors: | , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2010
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/45140 |
| 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: | Рекурсия и параллельные алгоритмы в задачах геометрического моделирования / В.Н. Терещенко, А.В. Анисимов // Кибернетика и системный анализ. — 2010. — № 2. — С. 10-22. — Бібліогр.: 27 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859688009706766336 |
|---|---|
| author | Терещенко, В.Н. Анисимов, А.В. |
| author_facet | Терещенко, В.Н. Анисимов, А.В. |
| citation_txt | Рекурсия и параллельные алгоритмы в задачах геометрического моделирования / В.Н. Терещенко, А.В. Анисимов // Кибернетика и системный анализ. — 2010. — № 2. — С. 10-22. — Бібліогр.: 27 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| description | Розглянуто ефективний підхід до побудови точних комп’ютерних моделей явищ і процесів. На основі стратегії «поділяй та владарюй» розроблено узагальнений паралельно-рекурсивний алгоритм одночасного розв’язання всієї сукупності взаємозв’язаних задач, які використовують спільно єдину структуру даних (зважену зчеплену чергу) на етапі злиття. При цьому етап розбиття спільний і виконується один раз для всіх задач. Це забезпечує ефективні і зручні засоби для побудови і дослідження складних обчислювальних моделей.
The paper discusses an efficient approach to accurate computer modeling of phenomena and processes. The “divide-and-conquer” technique is used to develop a generalized parallel-recursive algorithm for simultaneous solution of the totality of interrelated problems that use a common and unified data structure (weighted concatenable queue) at the stage of a merger. The stage of decomposition is common and is executed once for all tasks. This provides efficient and convenient means to construct and study complex computational models.
|
| first_indexed | 2025-11-30T23:33:53Z |
| format | Article |
| fulltext |
ÓÄÊ 004.925.8, 004.272.2
Â.Í. ÒÅÐÅÙÅÍÊÎ, À.Â. ÀÍÈÑÈÌÎÂ
ÐÅÊÓÐÑÈß È ÏÀÐÀËËÅËÜÍÛÅ ÀËÃÎÐÈÒÌÛ Â ÇÀÄÀ×ÀÕ
ÃÅÎÌÅÒÐÈ×ÅÑÊÎÃÎ ÌÎÄÅËÈÐÎÂÀÍÈß
Êëþ÷åâûå ñëîâà: âçàèìîñâÿçàííûå çàäà÷è, îáîáùåííûé ïàðàëëåëüíî-ðåêóðñèâ-
íûé àëãîðèòì, ãåîìåòðè÷åñêîå ìîäåëèðîâàíèå, âçâåøåííàÿ ñöåïëÿåìàÿ î÷åðåäü.
ÂÂÅÄÅÍÈÅ
Ñîâðåìåííûå âû÷èñëèòåëüíûå âîçìîæíîñòè ïîçâîëÿþò ñòàâèòü è ðåøàòü íîâûå
ñëîæíûå çàäà÷è, äëÿ êîòîðûõ íåîáõîäèìî ñîçäàâàòü êîìïëåêñíûå ìàòåìàòè÷åñ-
êèå ìîäåëè. Îñîáåííî ýòî îòíîñèòñÿ ê çàäà÷àì âèçóàëüíîãî ìîäåëèðîâàíèÿ ÿâ-
ëåíèé è ïðîöåññîâ, îïðåäåëåííûõ â íåêîòîðîé îáëàñòè ãåîìåòðè÷åñêîãî ïðîñò-
ðàíñòâà. Ðå÷ü èäåò î çàäà÷àõ, èññëåäóåìûå ïàðàìåòðû êîòîðûõ çàâèñÿò îò âíóò-
ðåííåé ñòðóêòóðû è ãåîìåòðè÷åñêîé ôîðìû ðàññìàòðèâàåìîé îáëàñòè è ìîãóò
èçìåíÿòüñÿ ñî âðåìåíåì. Ê íèì îòíîñÿòñÿ çàäà÷è ìîäåëèðîâàíèÿ òåïëîôèçè÷åñ-
êèõ ïðîöåññîâ ïðè ñâàðêå ðàçëè÷íûõ êîíñòðóêöèé èç ìåòàëëà, çàäà÷è ñëîæíîãî
äâèæåíèÿ æèäêîñòè, èññëåäîâàíèÿ â ÿäåðíîé ôèçèêå è àñòðîôèçèêå, à òàêæå çà-
äà÷è èññëåäîâàíèÿ áèîëîãè÷åñêèõ è õèìè÷åñêèõ ïðîöåññîâ, ïðîèñõîäÿùèõ â æè-
âîì îðãàíèçìå, è äðóãèå çàäà÷è.
Òàê, ïðè ñâàðêå ïëàñòèí ðàçëè÷íûõ ìàòåðèàëîâ ïðîèñõîäÿò ñëîæíûå äèíàìè-
÷åñêèå, òåïëîôèçè÷åñêèå è òåðìîìåõàíè÷åñêèå ïðîöåññû, ñâÿçàííûå ñ èçìåíåíèåì
ôàçîâîãî ñîñòîÿíèÿ âåùåñòâà, òåðìîíàïðÿæåííîãî è äåôîðìàöèîííîãî ñîñòîÿíèÿ,
à òàêæå ñî ñòðóêòóðíûìè èçìåíåíèÿìè ìàòåðèàëà. Çäåñü çîíà ñâàðêè ðàçäåëåíà íà
îáëàñòü ðàñïëàâà (ñâàðî÷íàÿ âàííà), ñâàðî÷íûé øîâ è ïðèãðàíè÷íûå ñ íèìè îáëàñ-
òè. Äëÿ ìîäåëèðîâàíèÿ òàêèõ ïðîöåññîâ íåîáõîäèìî îáðàáàòûâàòü îãðîìíûå îáúå-
ìû äàííûõ, ïàðàìåòðîâ è ðàçëè÷íûõ ñòðóêòóðíûõ ýëåìåíòîâ. ×òîáû ïîñòðîèòü
òî÷íóþ âèçóàëüíóþ ìîäåëü ðàññìàòðèâàåìûõ ïðîöåññîâ, íåîáõîäèìî ðàçðàáîòàòü
òàêîé ïîäõîä, êîòîðûé áû ïîçâîëÿë îäíîâðåìåííî ðåøàòü êîìïëåêñ ãåîìåòðè÷åñ-
êèõ è ïðèêëàäíûõ çàäà÷. Îäíèì èç òàêèõ ïîäõîäîâ ìîæåò áûòü ñîçäàíèå ïàðàë-
ëåëüíûõ àëãîðèòìîâ. Çäåñü ñóùåñòâóåò äâà âàðèàíòà.
 ïåðâîì âàðèàíòå èñïîëüçóþòñÿ ñîâîêóïíîñòè ýôôåêòèâíûõ, íî íå ñâÿçàííûõ
ìåæäó ñîáîé ïàðàëëåëüíûõ àëãîðèòìîâ äëÿ îäíîâðåìåííîãî ðåøåíèÿ íåñêîëüêèõ çà-
äà÷.  ýòîì ñëó÷àå èìååòñÿ öåëûé íàáîð ðàçíûõ èíñòðóìåíòîâ, êàæäûé èç êîòîðûõ
ìîæåò ýôôåêòèâíî ðåøàòü îòäåëüíûå çàäà÷è. Íà ñåãîäíÿøíèé äåíü ðàçðàáîòàíî
ìíîãî ýôôåêòèâíûõ ïàðàëëåëüíûõ àëãîðèòìîâ ðåøåíèÿ îòäåëüíûõ çàäà÷ âû÷èñëè-
òåëüíîé ãåîìåòðèè. Òàê, â ðàáîòå [1] ñ èñïîëüçîâàíèåì ñõåìû «ðàçäåëÿé è âëàñòâóé»
îïèñàíû ýôôåêòèâíûå àëãîðèòìû ðåøåíèÿ çàäà÷ ïîñòðîåíèÿ âûïóêëîé îáîëî÷êè äëÿ
äâóõ- è òðåõìåðíûõ ïðîñòðàíñòâ ñ îöåíêîé ñëîæíîñòè O N(log ) è O N(log )3 ñîîòâå-
òñòâåííî, à òàêæå ïîñòðîåíèÿ äèàãðàììû Âîðîíîãî (O N(log )2 ). Êðîìå òîãî, ïðåä-
ñòàâëåí äîñòàòî÷íî ãëóáîêèé àíàëèç äðóãèõ ýôôåêòèâíûõ àëãîðèòìîâ ðåøåíèÿ çàäà÷
ïåðåñå÷åíèÿ îòðåçêîâ, òðèàíãóëÿöèè ïîëèãîíîâ, îïòèìèçàöèè (O N(log )).  ðàáîòàõ
[2–7] ïîëó÷åíû óëó÷øåííûå ðåçóëüòàòû ðåøåíèÿ âûøåóêàçàííûõ çàäà÷ äëÿ ðàç-
ëè÷íûõ ìîäåëåé âû÷èñëåíèé (CREW, EREW) è äëÿ âûñøèõ ðàçìåðíîñòåé (d � 4).
Ðÿä ñòàòåé ïîñâÿùåí îáùèì ïàðàëëåëüíûì ìåòîäàì, êîòîðûå ïðèìåíèìû ê ðåøå-
íèþ îòäåëüíûõ çàäà÷ âû÷èñëèòåëüíîé ãåîìåòðèè [8–11].
Îäíàêî ïðè ïîñòðîåíèè ãåîìåòðè÷åñêèõ è âèçóàëüíûõ ìîäåëåé äëÿ èññëåäîâà-
íèÿ ñëîæíûõ ÿâëåíèé è ïðîöåññîâ èñïîëüçîâàíèå îòäåëüíûõ ýôôåêòèâíûõ àëãî-
ðèòìîâ â îáùåì ñëó÷àå íå ïðèíîñèò æåëàåìîé ýôôåêòèâíîñòè. Îòìåòèì, ÷òî ïî÷òè
10 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 2
© Â.Í. Òåðåùåíêî, À.Â. Àíèñèìîâ, 2010
êàæäûé àëãîðèòì ÿâëÿåòñÿ çàêðûòûì îòíîñèòåëüíî âûïîëíåíèÿ è íóæäàåòñÿ â ñîá-
ñòâåííîé ïðåäâàðèòåëüíîé îáðàáîòêå è ñîçäàíèè ñòðóêòóðû äàííûõ, à òàêæå ïðîöå-
äóðàõ ðåàëèçàöèè. Ýòî çàòðóäíÿåò âîçìîæíîñòü âçàèìîäåéñòâèÿ ìåæäó ïðîöåäóðà-
ìè àëãîðèòìîâ è íå ïîçâîëÿåò ïîëó÷àòü ðåøåíèå òàêîãî êëàññà çàäà÷ ñ ìèíè-
ìàëüíûì âðåìåíåì.
Ïîýòîìó âòîðîé âàðèàíò ñâÿçàí ñ ðàçðàáîòêîé óíèâåðñàëüíîãî èíñòðóìåíòà,
êîòîðûé èìåë áû îáùèå ñðåäñòâà äëÿ ýôôåêòèâíîãî ðåøåíèÿ âñåãî êîìïëåêñà âçà-
èìîñâÿçàííûõ ãåîìåòðè÷åñêèõ è ïðèêëàäíûõ çàäà÷. Äðóãèìè ñëîâàìè, íåîáõîäèìî
âûáðàòü ñòðàòåãèþ, êîòîðàÿ èñïîëüçîâàëà áû îáùèå ñðåäñòâà ðåàëèçàöèè: ñòðóêòó-
ðû äàííûõ, îòäåëüíûå ýòàïû àëãîðèòìîâ, ïðîöåäóð è íåêîòîðûå èõ øàãè, à òàêæå
ñïîñîáû ïðåäñòàâëåíèÿ ðåçóëüòàòîâ. Ó÷èòûâàÿ îòìå÷åííûå îñîáåííîñòè è òî, ÷òî
áîëüøèíñòâî çàäà÷ âû÷èñëèòåëüíîé ãåîìåòðèè èìååò âíóòðåííèé ïàðàëëåëèçì è
ïðåäóñìàòðèâàåò ðåêóðñèâíóþ ïðèðîäó ðåàëèçàöèè, íàèáîëåå ïîäõîäÿùåé ñòðàòå-
ãèåé, íà íàø âçãëÿä, ìîæåò áûòü òà, â îñíîâå êîòîðîé ëåæèò ïàðàëëåëüíî-ðåêóðñèâ-
íûé àëãîðèòì, èñïîëüçóþùèé ñõåìó «ðàçäåëÿé è âëàñòâóé». Çäåñü ýòàïû ïðåäâàðè-
òåëüíîé îáðàáîòêè è ðàçáèåíèÿ ìíîæåñòâà áóäóò îáùèìè äëÿ âñåãî êîìïëåêñà çà-
äà÷, à íà ýòàïå ñëèÿíèÿ ïðåäëàãàåòñÿ èñïîëüçîâàòü îáùóþ äëÿ âñåõ çàäà÷ ñòðóêòóðó
äàííûõ — âçâåøåííóþ ñöåïëÿåìóþ î÷åðåäü. Êðîìå òîãî, ðåçóëüòàòû îòäåëüíûõ
ýòàïîâ íåêîòîðûõ ïðîöåäóð áóäóò èñïîëüçîâàòüñÿ äðóãèìè ïðîöåäóðàìè, ÷òî îáåñ-
ïå÷èò âûñîêóþ ýôôåêòèâíîñòü ðåøåíèÿ.
 íàñòîÿùåé ñòàòüå äëÿ ñîâîêóïíîñòè çàäà÷ âû÷èñëèòåëüíîé ãåîìåòðèè,
êîòîðûå èìåþò íèæíþþ îöåíêó ñëîæíîñòè � ( log )N N , ïðåäëîæåí îáîáùåííûé
ïàðàëëåëüíî-ðåêóðñèâíûé àëãîðèòì èõ ðåøåíèÿ, ïðèíàäëåæàùèé êëàññó ðàçðåøè-
ìîñòè ïîðÿäêà O N(log )2 .  ÷àñòíîñòè, â ðàáîòàõ [12, 13] îòìå÷åíî, ÷òî áîëüøèí-
ñòâî çàäà÷ âû÷èñëèòåëüíîé ãåîìåòðèè â ñëó÷àå ïàðàëëåëüíîé ðåàëèçàöèè ïðèíàä-
ëåæèò ýòîìó êëàññó.
Ïîñòàíîâêà çàäà÷è. Ïóñòü çàäàíî ìíîæåñòâî S èç N òî÷åê â ïðîñòðàíñòâå Å d .
Íåîáõîäèìî ðàçðàáîòàòü îáîáùåííûé ýôôåêòèâíûé ðåêóðñèâíî-ïàðàëëåëüíûé
àëãîðèòì ðåøåíèÿ çàäà÷ âû÷èñëèòåëüíîé ãåîìåòðèè, îïðåäåëåííûõ íà îäíîì è
òîì æå ìíîæåñòâå S , íèæíÿÿ îöåíêà ñëîæíîñòè êîòîðûõ ïîðÿäêà � ( log )N N (äëÿ
îäíîïðîöåññîðíîé ìàøèíû).
1. ÏÀÐÀËËÅËÜÍÎ-ÐÅÊÓÐÑÈÂÍÛÉ ÀËÃÎÐÈÒÌ ÍÀ ÎÑÍÎÂÅ
ÑÒÐÀÒÅÃÈÈ «ÐÀÇÄÅËßÉ È ÂËÀÑÒÂÓÉ»
Èäåÿ ïðåäëîæåííîãî àëãîðèòìà áàçèðóåòñÿ íà ñòðàòåãèè «ðàçäåëÿé è âëàñòâóé»,
êîòîðàÿ ñîñòîèò èç äâóõ ýòàïîâ: ðåêóðñèâíîãî ðàçáèåíèÿ çàäàííîãî ìíîæåñòâà
òî÷åê íà ïîäìíîæåñòâà ðàâíîé ìîùíîñòè è ñëèÿíèÿ, â ïðîöåññå êîòîðîãî íà
êàæäîì øàãå ðåêóðñèè ðåøàåòñÿ çàäà÷à ñîîòâåòñòâóþùåãî ìíîæåñòâà òî÷åê ïó-
òåì ñëèÿíèÿ ðåçóëüòàòîâ äëÿ åå ïîäìíîæåñòâ.
Îñíîâíîé ïðîáëåìîé ïðèìåíåíèÿ ñõåìû «ðàçäåëÿé è âëàñòâóé» ïðè ðåøåíèè
çàäà÷ âû÷èñëèòåëüíîé ãåîìåòðèè åñòü íåëèíåéíîñòü ýòàïà ñëèÿíèÿ è îòñóòñòâèå
ëèíåéíîé ðàçäåëèìîñòè ìíîæåñòâà òî÷åê.  ðàññìàòðèâàåìîì ïîäõîäå äëÿ çàäà÷,
âõîäíûìè äàííûìè êîòîðûõ ÿâëÿåòñÿ ìíîæåñòâî òî÷åê, áëàãîäàðÿ óäà÷íîìó ïðåä-
ñòàâëåíèþ âõîäíûõ äàííûõ íà ýòàïå ïðåäâàðèòåëüíîé îáðàáîòêè è èñïîëüçîâàíèþ
ïàðàëëåëüíîé îáðàáîòêè íà ýòàïàõ ðàçáèåíèÿ è ñëèÿíèÿ óäàëîñü ïîñòðîèòü ýôôåê-
òèâíûé ðåêóðñèâíî-ïàðàëëåëüíûé àëãîðèòì, â ðåçóëüòàòå ÷åãî ñíèìàþòñÿ óêàçàí-
íûå îãðàíè÷åíèÿ ê ïðèìåíåíèþ. Ðàññìîòðèì ïîñòðîåíèå ýòîãî àëãîðèòìà íà ïðè-
ìåðå äâóìåðíûõ çàäà÷.
Ìàòåìàòè÷åñêàÿ ìîäåëü àëãîðèòìà. Ìàòåìàòè÷åñêàÿ ìîäåëü ïðåäëàãàåìîãî
ïàðàëëåëüíîãî àëãîðèòìà âêëþ÷àåò òàêèå îñíîâíûå ýòàïû: ïðåäâàðèòåëüíàÿ îáðà-
áîòêà, ðàçáèåíèå ìíîæåñòâà òî÷åê, ðåêóðñèâíîå ñëèÿíèå ðåçóëüòàòîâ äëÿ ïîäìíî-
æåñòâ.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 2 11
Ýòàï 1. Ïðåäâàðèòåëüíàÿ îáðàáîòêà. Ïóñòü çàäàíû ìíîæåñòâî
S P P PN� { , , , }1 2 � èç N òî÷åê íà ïëîñêîñòè è Î N( ) ïðîöåññîðîâ. Ôîðìèðóåòñÿ óïî-
ðÿäî÷åííûé ìàññèâ òî÷åê â âèäå ñïèñêàU P ³ j Nij� �{ , , , }1 , ãäå i j, — èíäåêñû, óêà-
çûâàþùèå íà ïîðÿäîê òî÷êè â ìàññèâå ïî x è y êîîðäèíàòàì ñîîòâåòñòâåííî. Ïî-
ñòðîåíèå îòñîðòèðîâàííîãî ìàññèâà ñ ïîìîùüþ Î N( ) ïðîöåññîðîâ ìîæíî îñóùå-
ñòâèòü îäíèì èç àëãîðèòìîâ, äåòàëüíî îïèñàííûõ â ðàáîòàõ [14–16], êîòîðûå äàþò
îöåíêè ñëîæíîñòè ïîðÿäêà NC2 . Ñôîðìèðîâàííûé òàêèì ñïîñîáîì ìàññèâ ïîäàåò-
ñÿ íà âõîä àëãîðèòìà, ãðàô (äåðåâî) êîòîðîãî ïðåäñòàâëåí íà ðèñ. 1. Çäåñü NN , T,
CH, vor — ïðîöåäóðû ñëèÿíèÿ çàäà÷: áëèæàéøèå ñîñåäè, òðèàíãóëÿöèÿ, âûïóêëàÿ
îáîëî÷êà, äèàãðàììà Âîðîíîãî ñîîòâåòñòâåííî.  ýòîì ãðàôå êàæäûé óçåë îáîçíà-
÷åí öåëûì ÷èñëîì k , îòíîñèòåëüíî êîòîðîãî ðàçáèâàåòñÿ ñïèñîê òî÷åê â óçëàõ íà
äâà ðàâíîìîùíûõ îòíîñèòåëüíî ìåäèàíû ñïèñêà ïîñëå ñðàâíåíèÿ ïåðâûõ èíäåêñîâ
òî÷åê ìàññèâà Ðij . Çíà÷åíèå k îïðåäåëÿåòñÿ çà îäèí ïðîõîä ïî äåðåâó, åñëè èçâåñò-
íî êîëè÷åñòâî òî÷åê çàäàííîãî ìíîæåñòâà, ïî ôîðìóëå
k m M� �[( ) / ]2 , (1)
ãäå m è Ì — ñîîòâåòñòâåííî íîìåð ïåðâîãî è íîìåð ïîñëåäíåãî ýëåìåíòîâ ñïèñêà.
Ýòàï 2. Ðàçáèåíèå ìíîæåñòâà òî÷åê (ðåêóðñèâíûé ñïóñê). Ïðîèñõîäèò ðàç-
áèåíèå íà êàæäîì øàãå ðåêóðñèè çàäàííîãî ìíîæåñòâà òî÷åê â âèäå ñïèñêà U íà
ïîäìíîæåñòâà U1,U2 ðàâíîé ìîùíîñòè, ïîèñê ìåäèàíû l è ïåðåäà÷àU1,U2 íà ñëå-
äóþùèé øàã ðåêóðñèè. Ïðîöåññ ðàçáèåíèÿ çàêàí÷èâàåòñÿ, êîãäà â ïîäìíîæåñòâàõ
îñòàåòñÿ òàêîå êîëè÷åñòâî òî÷åê, äëÿ êîòîðîãî âñå ïðîöåäóðû ñëåäóþùåãî ýòàïà
(ñëèÿíèÿ) âûïîëíÿþòñÿ òðèâèàëüíî. Ïîèñê ìåäèàíû íà óïîðÿäî÷åííîì ïî êîîðäè-
íàòå õ èíäåêñèðîâàííîì ìàññèâå òî÷åê U âûïîëíÿåòñÿ çà êîíñòàíòíîå âðåìÿ
Î l P Pkj k j( ): ( ) /1 21� � � , ãäå k — íîìåð óçëà.
Âðåìÿ, íåîáõîäèìîå íà ðåêóðñèâíûé ñïóñê ïàðàëëåëüíîãî àëãîðèòìà, îïðåäå-
ëÿåòñÿ ñëåäóþùåé ëåììîé.
12 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 2
6
3 9
2 5 8 11
1 4 7 10
ÏÐÎÖÅÑÑÎÐÛ
ß×ÅÉÊÈ ÏÀÌßÒÈ
NN, T, CH, vor : S
NN, T, CH, vor : S1 NN, T, CH, vor : S2
NN, T, CH, vor : S11 NN, T, CH, vor : S12 NN, T, CH, vor : S21
i
NN, T, CH, vor : S111 NN, T, CH, vor : S121 NN, T, CH, vor : S211 NN, T, CH, vor : S221
j
NN, T, CH, vor : S22
Ðèñ. 1. Ãðàô àëãîðèòìà
Ëåììà 1. Ýòàï ðåêóðñèâíîãî ðàçáèåíèÿ ìíîæåñòâà S èç N òî÷åê íà ðàâíîìîù-
íûå ïîäìíîæåñòâà S1 è S 2 ïëîñêîñòè, ïîèñê ìåäèàíû l è ïåðåäà÷ó ïîäìíîæåñòâ S1
è S 2 ñ ïîìîùüþ Î N( ) ïðîöåññîðîâ ìîæíî âûïîëíèòü çà âðåìÿ Î N(log ).
Äîêàçàòåëüñòâî. Ïóñòü çàäàíî ìíîæåñòâî òî÷åê â âèäå èíäåêñèðîâàííîãî äâó-
ìåðíîãî, óïîðÿäî÷åííîãî ìàññèâà U P ³ j Nij� �{ , , , }1 . Äëÿ ïîñòðîåíèÿ òàêîé ñòðóê-
òóðû äàííûõ ìîæíî âîñïîëüçîâàòüñÿ, íàïðèìåð, ïàðàëëåëüíûì àëãîðèòìîì ñîð-
òèðîâêè ñî âðåìåíåì Î N(log ), ïðåäëîæåííûì â [16]. Òàêîå ïðåäñòàâëåíèå ìíî-
æåñòâà òî÷åê ïîçâîëÿåò ïðè èçâåñòíîì êîëè÷åñòâå òî÷åê N â ñïèñêå U ïîñòðîèòü
ïðîöåññ ðàçáèåíèÿ (ñì. ðèñ. 1). Íà êàæäîì øàãå ðàçáèåíèÿ ñîîòâåòñòâóþùèå ïðî-
öåññîðû ñèíõðîííî ñðàâíèâàþò ïåðâûå èíäåêñû èç ñïèñêà òî÷åê è ðàññûëàþò òî÷-
êè â ñîîòâåòñòâóþùèå óçëû àëãîðèòìà, ñîõðàíÿÿ ïðè ýòîì ïîðÿäîê ðàñïîëîæåíèÿ
òî÷åê. Ââèäó ÷åòêîé óïîðÿäî÷åííîñòè ïî îáîèì èíäåêñàì òî÷åê Pij ìàññèâà U
è âçàèìîñâÿçè ìåæäó ïðîöåññîðàìè è ýëåìåíòàìè ïàìÿòè âðåìÿ âûïîëíåíèÿ ïðî-
öåññà ñëèÿíèÿ â êàæäîì óçëå äåðåâà íå áóäåò ïðåâûøàòü êîíñòàíòó Î( )1 .Òàêèì îá-
ðàçîì, îáùåå âðåìÿ ðàçáèåíèÿ íå ïðåâûøàåò Î N(log ) äëÿ íàèõóäøåãî ââîäà äàí-
íûõ, ÷òî è òðåáîâàëîñü äîêàçàòü.
Ïðîöåññû, êîòîðûå ðåàëèçóþò àëãîðèòì íà ýòàïå ðàçáèåíèÿ, ìîæíî îïèñàòü
òàêèì îáðàçîì. Ïóñòü n — êîëè÷åñòâî ýëåìåíòîâ ñïèñêà â óçëàõ àëãîðèòìà, êîòîðîå
îïðåäåëÿåòñÿ äåëåíèåì êîëè÷åñòâà ýëåìåíòîâ ðîäèòåëüñêîãî óçëà íà äâå ðàâíûå
÷àñòè; r — óðîâåíü äåðåâà àëãîðèòìà, êîòîðûé ñîîòâåòñòâóåò øàãó ðåêóðñèè; k —
íîìåð óçëà, îïðåäåëÿåìîãî ñîîòíîøåíèåì (1); ³ j, — èíäåêñû ýëåìåíòîâ ìàññèâà
U P i j Nij� �{ , , , }1 .
Ïðè n � 1 âñåì ïðîöåññàì íåîáõîäèìî âûïîëíèòü ñëåäóþùèå îïåðàöèè.
1. Ïðèñâîèòü íîìåð k êàæäîìó óçëó äåðåâà àëãîðèòìà ñîãëàñíî (1).
2. Íà r-ì øàãå àëãîðèòìà â óçëå k îïðåäåëèòü ìåäèàíó l ìíîæåñòâà S U( ) ïî
ôîðìóëå l P Pkj k j� � �( ) /1 2.
3. Íà r-ì øàãå àëãîðèòìà â óçëå k íåîáõîäèìî ñðàâíèòü çíà÷åíèå ³-ãî èíäåêñà
Pij ýëåìåíòîâ ìàññèâà U ñ ÷èñëîì k :
à) åñëè i k� , òî ïîñëàòü êàæäûé ýëåìåíò P U
ij
� , èíäåêñ êîòîðîãî óäîâëåòâî-
ðÿåò ýòîìó óñëîâèþ, â óçåë «ËÅÂÛÉ ÑÛÍ» ïî ³-ìó êàíàëó è çàïèñàòü â j-þ ÿ÷åéêó
ïàìÿòè óçëà;
á) åñëè i k� , òî ïîñëàòü êàæäûé ýëåìåíò P U
ij
� , èíäåêñ êîòîðîãî óäîâëåò-
âîðÿåò ýòîìó óñëîâèþ, â óçåë «ÏÐÀÂÛÉ ÑÛÍ» ïî ³-ìó êàíàëó è çàïèñàòü â j-þ
ÿ÷åéêó ïàìÿòè óçëà.
4. Ïðè n � 1 ïðîèñõîäèò çàâåðøåíèå ðàáîòû ýòîãî ýòàïà àëãîðèòìà.
Òàêèì îáðàçîì, â ðåçóëüòàòå ðàáîòû àëãîðèòìà íà ýòîì ýòàïå áóäóò ñôîðìèðî-
âàíû óïîðÿäî÷åííûå ïî ó ïîäìíîæåñòâà òî÷åê U1, U2 ðàâíîé ìîùíîñòè îòíîñè-
òåëüíî ìåäèàíû l (ïðè ýòîì U1 ðàñïîëîæåíî ñëåâà, à U2 — ñïðàâà îòíîñèòåëüíî l).
Ýòàï 3. Ðåêóðñèâíîå ñëèÿíèå ðåçóëüòàòîâ äëÿ ïîäìíîæåñòâ (ðåêóðñèâíûé
ïîäúåì). Ïîëó÷åííûå ðåçóëüòàòû ðåøåíèÿ ñîîòâåòñòâóþùåé çàäà÷è (âûïóêëîé
îáîëî÷êè, äèàãðàììû Âîðîíîãî, äåêîìïîçèöèè è ò.ä.) ñ ëèñòîâûõ óçëîâ äåðåâà
àëãîðèòìà ïîäàþòñÿ â ðîäèòåëüñêèå óçëû, ãäå èñïîëüçóþòñÿ ñîîòâåòñòâóþùèå
ïðîöåäóðû ñëèÿíèÿ äëÿ ïîñòðîåíèÿ îáùåãî ðåøåíèÿ çàäà÷è. Ïðîöåññ çàêàí÷èâà-
åòñÿ ñëèÿíèåì ðåçóëüòàòîâ â êîðíåâîì óçëå.  ÷àñòíîñòè, â ðàáîòàõ [17–19] óæå
ïðåäëîæåíû ýôôåêòèâíûå ïðîöåäóðû ñëèÿíèÿ äëÿ òàêèõ çàäà÷, êàê ïîñòðîåíèå
âûïóêëîé îáîëî÷êè, íàõîæäåíèå áëèæàéøåé ïàðû, òðèàíãóëÿöèÿ è äðóãèå. Íèæå
äåòàëüíî áóäóò îïèñàíû ïðîöåäóðà ñëèÿíèÿ äèàãðàììû Âîðîíîãî (ïîñêîëüêó
ñàìà äèàãðàììà è àëãîðèòì åå ïîñòðîåíèÿ èñïîëüçóþòñÿ äëÿ ðåøåíèÿ äðóãèõ âàæ-
íûõ çàäà÷ âû÷èñëèòåëüíîé ãåîìåòðèè) è ïðîöåäóðà ñëèÿíèÿ çàäà÷è î âñåõ áëè-
æàéøèõ ñîñåäÿõ. À ïðîöåäóðû ñëèÿíèÿ äëÿ çàäà÷ ïîñòðîåíèÿ âûïóêëîé îáîëî÷êè
è òðèàíãóëÿöèè áóäóò îïèñàíû ëèøü íà óðîâíå èäåé. Îñîáåííîñòü ïðåäëîæåííûõ
ïðîöåäóð ñîñòîèò â ïðèìåíåíèè ñöåïëÿåìîé î÷åðåäè äëÿ ïðåäñòàâëåíèÿ òî÷åê â
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 2 13
óçëàõ àëãîðèòìà, ÷òî ïîçâîëÿåò âûïîëíÿòü âñå îïåðàöèè çà ëîãàðèôìè÷åñêîå âðå-
ìÿ. Âîïðîñ èñïîëüçîâàíèÿ îïòèìàëüíîãî ñîñòàâà ïðîöåññîðîâ (êîìïüþòåðîâ)
â äàííîé ñòàòüå íå ðàññìàòðèâàåòñÿ è íóæäàåòñÿ â äîïîëíèòåëüíîì èññëåäîâàíèè.
 òî æå âðåìÿ èç ðàáîòû [20] èçâåñòíî, ÷òî åñëè ñ÷èòàòü w îáùèì ÷èñëîì îïåðà-
öèé àëãîðèòìà, à Î F N( ( )) — îöåíêîé ñëîæíîñòè àëãîðèòìà äëÿ íåîãðàíè÷åííîãî
êîëè÷åñòâà ïðîöåññîðîâ, òî âðåìÿ âûïîëíåíèÿ àëãîðèòìà äëÿ p ïðîöåññîðîâ ìîæ-
íî âûðàçèòü ñîîòíîøåíèåì
Î f N p Î F N w p( ( )) (( – ) ( ( )) ) /� �1 . (2)
2. ÏÎÑÒÐÎÅÍÈÅ ÏÐÎÖÅÄÓÐ ÑËÈßÍÈß
Îñîáåííîñòü ðàññìàòðèâàåìîãî àëãîðèòìà çàêëþ÷àåòñÿ â òîì, ÷òî ìåæäó ïðîöå-
äóðàìè ñëèÿíèÿ ïðåäñòàâëåííîãî êîìïëåêñà çàäà÷ ñóùåñòâóåò ñâÿçü íà óðîâíå
êàê îòäåëüíûõ øàãîâ âûïîëíåíèÿ, òàê è îïåðàöèé. È ñâÿçóþùèì çâåíîì çäåñü
âûñòóïàåò ïðîöåäóðà ñëèÿíèÿ âûïóêëûõ îáîëî÷åê, ïîñêîëüêó îíà ïðè ïîñòðîå-
íèè âñåõ ïðîöåäóð ñëèÿíèÿ èñïîëüçóåòñÿ êàê îäèí èç êëþ÷åâûõ øàãîâ àëãîðèò-
ìà. Ïîýòîìó èõ ïîñòðîåíèå äëÿ ðàññìàòðèâàåìîãî ðåêóðñèâíî-ïàðàëëåëüíîãî àë-
ãîðèòìà íà÷íåì ñ ïðîöåäóðû ñëèÿíèÿ âûïóêëûõ îáîëî÷åê. Öåíòðàëüíîå ìåñòî,
êàê îáðàçóþùàÿ ïðîöåäóðà, çàíèìàåò ïðîöåäóðà ñëèÿíèÿ è ïîñòðîåíèÿ äèàãðàì-
ìû Âîðîíîãî, ïîñêîëüêó îíà ïîçâîëÿåò ñòðîèòü ïðîöåäóðû ñëèÿíèÿ äðóãèõ ñëîæ-
íûõ çàäà÷ ðàññìàòðèâàåìîé ñîâîêóïíîñòè. Èçëîæèì ýòî äåòàëüíî, à êðàòêî ðàñ-
ñìîòðèì ïðîöåäóðû ñëèÿíèÿ òðèàíãóëÿöèè è ïîèñêà âñåõ áëèæàéøèõ ñîñåäåé.
2.1. Ïðîöåäóðà ñëèÿíèÿ çàäà÷è ïîñòðîåíèÿ âûïóêëîé îáîëî÷êè. Èçâåñò-
íûå ïàðàëëåëüíûå àëãîðèòìû ïîñòðîåíèÿ âûïóêëîé îáîëî÷êè ìíîæåñòâà òî÷åê
â åâêëèäîâîì ïðîñòðàíñòâå E d , èñïîëüçóþùèå èäåþ «ðàçäåëÿé è âëàñòâóé», òàê
èëè èíà÷å ñâÿçàíû ñ íàõîæäåíèåì îïîðíûõ ðåáåð ãðàíèö äâóõ îáîëî÷åê. Çäåñü
(äëÿ äâóìåðíîãî ñëó÷àÿ) ìîæíî îòìåòèòü ðàáîòû Ð. Ìèëëåðà è Ê.Ô. Ñòîóòà [21]
(ñ îöåíêîé ñëèÿíèÿ O N(log )), Î. Áåðêìàíà [6] (O N(log log )), Ì.Ò. Ãóäðèõà è
Ì. Ãîóñà [22] (ñ îöåíêîé O N(log )2 ñ ïðåäâàðèòåëüíîé ñîðòèðîâêîé è ðàíäîìèçè-
ðîâàííûé àëãîðèòì ïîðÿäêà O N(log )), à òàêæå àëãîðèòì Ä. ×åíà [5]. Äëÿ ñëó÷àÿ
âûñøèõ èçìåðåíèé óìåñòíî âûäåëèòü ðàáîòó [4], ãäå äëÿ d � 3 ïîëó÷åíà âûñîêàÿ
ñêîðîñòü âûïîëíåíèÿ àëãîðèòìîâ — ïîðÿäêà O N(log )2 . Íî ðåøàþùèì â âîïðîñå
ïîñòðîåíèÿ ýôôåêòèâíûõ ïàðàëëåëüíûõ àëãîðèòìîâ, áåçóñëîâíî, ÿâëÿåòñÿ çàìå÷à-
òåëüíàÿ èäåÿ Ì. Îâåðìàðñà è Äæ. Âàí Ëþâåíà [23], êîòîðàÿ ïîçâîëÿåò èñïîëüçî-
âàòü â êà÷åñòâå ñòðóêòóðû äàííûõ ñöåïëÿåìóþ î÷åðåäü.
Äëÿ ïîñòðîåíèÿ ïðîöåäóðû ñëèÿíèÿ âûïóêëûõ îáîëî÷åê ðàññìàòðèâàåìîãî ïà-
ðàëëåëüíîãî àëãîðèòìà ïðèìåíÿëèü ëèøü íåêîòîðûå ýëåìåíòû èç ïîñëåäîâàòåëüíîãî
àëãîðèòìà, ïðåäëîæåííîãî â ðàáîòå [23].  ÷àñòíîñòè, â àëãîðèòìå áûëà ïðåäëîæåíà
ïðîöåäóðà ñëèÿíèÿ âåðõíåé ( íèæíåé ) âûïóêëîé îáîëî÷êè ìíîæåñòâà òî÷åê ïðè ðå-
øåíèè äèíàìè÷åñêîé çàäà÷è ñ îöåíêîé O N(log ). Òàêàÿ ýôôåêòèâíîñòü äîñòèãàåòñÿ
çà ñ÷åò èñïîëüçîâàíèÿ ñòðóêòóðû äàííûõ â âèäå ñöåïëÿåìîé î÷åðåäè, ÷òî ïîçâîëÿåò
âûïîëíÿòü âñå íåîáõîäèìûå îïåðàöèè íà êàæäîì øàãå çà ëîãàðèôìè÷åñêîå âðåìÿ.
Íà êàæäîì øàãå ðåêóðñèâíîãî ïîäúåìà, íà÷èíàÿ ñî âòîðîãî, íà âõîä íåêîòîðî-
ãî ðîäèòåëüñêîãî óçëà � äåðåâà àëãîðèòìà (ñì. ðèñ. 1) ïîäàþòñÿ âûïóêëûå îáîëî÷-
êè îò ëåâîãî UL (UL � ËÑÛÍ[ ]� ) è ïðàâîãî UR (UR � ÏÑÛÍ[ ]� ) ñûíîâåé ñîîòâåò-
ñòâåííî. Äëÿ ïîñòðîåíèÿ îáùåé âûïóêëîé îáîëî÷êè ñûíîâåé óçëà � íåîáõîäèìî
îïðåäåëèòü âåðõíèå (íèæíèå) îïîðíûå âåðøèíû äëÿ ëåâîé è ïðàâîé âûïóêëûõ îáî-
ëî÷åê. Äàëåå ñëåäóåò ðàñöåïèòü âçàèìíî âûïóêëûå öåïè ìåæäó ýòèìè îïîðíûìè
òî÷êàìè, à îñòàâøèåñÿ öåïè ñîåäèíèòü ñîîòâåòñòâóþùèìè îïîðíûìè îòðåçêàìè.
Ïðîöåäóðà ÑÎÅÄÈÍÈÒÜ ( , )U UL R , íà÷èíàÿ ñ êîðíåâûõ âåðøèí ñáàëàíñèðîâàííûõ
äåðåâüåâ, êîòîðûå ïîääåðæèâàþò UL è UR , ïîçâîëÿåò ïîñòðîèòü âåðõíþþ è íèæ-
íþþ ãðàíèöû âûïóêëîé îáîëî÷êè çà âðåìÿ O N(log ). Ïðè âûïîëíåíèè ïîèñêà
îïîðíûõ âåðøèí è ïîñòðîåíèè îïîðíûõ îòðåçêîâ â äàííîì ñëó÷àå èñïîëüçóåòñÿ òà-
êàÿ æå êëàññèôèêàöèÿ âåðøèí, êàê è â ðàáîòå [23]. Ïîñëå îïðåäåëåíèÿ îïîðíûõ òî-
14 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 2
÷åê è ñöåïëåíèÿ ñ ïîìîùüþ èõ âû-
ïóêëûõ îáîëî÷åê ñûíîâåé óçëà �
óäàëÿþòñÿ ïðàâàÿ è ëåâàÿ ÷àñòè
äåðåâüåâ, êîòîðûå ïîääåðæèâàþò
ñîîòâåòñòâåííî UL è UR ìåæäó
îïîðíûìè òî÷êàìè. Áàëàíñèðîâà-
íèå äåðåâüåâ, êîòîðûå áóäóò ïîä-
äåðæèâàòü âåðõíþþ è íèæíþþ
âûïóêëûå îáîëî÷êè óçëà �, îñóùå-
ñòâëÿåòñÿ ïóòåì ñëèÿíèÿ îñòàâ-
øèõñÿ ÷àñòåé äåðåâüåâ. Âñå ïðèâå-
äåííûå îïåðàöèè âûïîëíÿþòñÿ çà
âðåìÿ O N(log ). Ïîëó÷åííûå òà-
êèì ñïîñîáîì âûïóêëûå îáîëî÷êè
ïåðåäàþòñÿ íà ñëåäóþùèé óðîâåíü ðåêóðñèè äåðåâà àëãîðèòìà (ñì. ðèñ. 1).
Íà ðèñ. 2 ïîêàçàí øàã ñëèÿíèÿ àëãîðèòìà. Â êàæäîì óçëå äåðåâà àëãîðèòìà âû-
çûâàåòñÿ ïðîöåäóðà ÑËÈßÍÈß_ÂÛÏÓÊËÀß ÎÁÎËÎ×ÊÀ (CH U CH UL R( ), ( )), êî-
òîðàÿ íàõîäèò îïîðíûå âåðøèíû (îòðåçêè), ñòðîèò è ïîääåðæèâàåò íîâóþ
âûïóêëóþ îáîëî÷êó.
Íà ðèñ. 3 ïîêàçàíà ñõåìà ïîèñêà îïîðíûõ âåðøèí ëåâîé è ïðàâîé âûïóêëûõ
îáîëî÷åê, ïðåäñòàâëåííûõ íà ðèñ. 2, äî ñëèÿíèÿ (à) è ïîñëå ñëèÿíèÿ (á).
Ëåììà 2. Ýòàï ðåêóðñèâíîãî ñëèÿíèÿ ðåçóëüòàòîâ íàõîæäåíèÿ âûïóêëîé îáî-
ëî÷êè ìíîæåñòâà S èç N òî÷åê íà ïëîñêîñòè ñ ïîìîùüþ Î N( ) ïðîöåññîðîâ ìîæíî
âûïîëíèòü çà âðåìÿ Î N(log )2 .
Áîëåå äåòàëüíî ïðîöåäóðà ñëèÿíèÿ ïîñòðîåíèÿ âûïóêëîé îáîëî÷êè äëÿ ðàñ-
ñìàòðèâàåìîãî ïàðàëëåëüíî-ðåêóðñèâíîãî àëãîðèòìà îïèñàíà â ðàáîòå [17].
2.2. Ïðîöåäóðà ñëèÿíèÿ çàäà÷è òðèàíãóëÿöèè. Çàäà÷à òðèàíãóëÿöèè íà îãðà-
íè÷åííîì ìíîæåñòâå òî÷åê äîñòàòî÷íî èçó÷åíà, è äëÿ åå ðåøåíèÿ ñóùåñòâóåò ðÿä
ýôôåêòèâíûõ ïîñëåäîâàòåëüíûõ àëãîðèòìîâ. Çäåñü ñëåäóåò îòìåòèòü ïóáëèêàöèè
À.Â. Ñêâîðöîâà, â ÷àñòíîñòè ðàáîòó [24], â êîòîðîé ïðåäëîæåíî íåñêîëüêî áûñò-
ðûõ àëãîðèòìîâ òðèàíãóëÿöèè. Ñðåäè ïàðàëëåëüíûõ àëãîðèòìîâ òðèàíãóëÿöèè õî-
ðîøèå ðåçóëüòàòû ïîëó÷åíû Ì.Ò. Ãóäðèõîì [25].  íàñòîÿùåé ñòàòüå ïðåäëàãàåòñÿ
ïðîöåäóðà òðèàíãóëÿöèè äëÿ ðàññìàòðèâàåìîãî ïàðàëëåëüíîãî àëãîðèòìà â ñëó÷àå
àñèìïòîòè÷åñêè áîëüøèõ ìíîæåñòâ òî÷åê (èëè ìíîæåñòâ òî÷åê, ïðåäñòàâëÿþùèõ
ñòðóêòóðèðîâàííûå îáúåêòû). Ïðîöåäóðà ñëèÿíèÿ çàäà÷è òðèàíãóëÿöèè äåòàëüíî
îïèñàíà â ðàáîòå [19], ïîýòîìó çäåñü êîñíåìñÿ ëèøü åå èäåè.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 2 15
S1 S2
l1 l2l
P9
P2
P1
P3
UL � CH(S1) UR � CH(S2)P10
P11
P12
P7
P8P6
P5
P4
Ðèñ. 2. Ïðèìåð ýòàïà ñëèÿíèÿ âûïóêëûõ îáîëî÷åê
P2
Âåðõíÿÿ ëåâàÿ
îïîðíàÿ âåðøèíà
P1 P6
Íèæíÿÿ ëåâàÿ
îïîðíàÿ âåðøèíà
Âåðõíÿÿ ïðàâàÿ
îïîðíàÿ âåðøèíà
Íèæíÿÿ ïðàâàÿ
îïîðíàÿ âåðøèíàP5
P6P1
P7
P12P8
P10
P8 P12
P9 P11
P9
P1
P5 P2
P11
P10 P12
Ðèñ. 3. Ñöåïëÿåìûå î÷åðåäè âûïóêëûõ îáîëî÷åê äî ñëèÿíèÿ (à) è ïîñëå ñëèÿíèÿ (á)
à á
Íà êàæäîì øàãå ðåêóð-
ñèâíîãî ïîäúåìà, íà÷èíàÿ
ñî âòîðîãî, íà âõîä ðîäèòå-
ëüñêîãî óçëà � äåðåâà (ñì.
ðèñ. 1) ïîäàþòñÿ òðèàíãó-
ëÿöèè îò ëåâîãî T S L( )
è ïðàâîãî T S R( ) ñûíîâåé
ñîîòâåòñòâåííî, êîòîðûå
îãðàíè÷åíû ãðàíèöàìè âû-
ïóêëûõ îáîëî÷åê CH S L( )
è CH S R( ). Äëÿ ïîñòðîåíèÿ
òðèàíãóëÿöèè íà îñíîâå òðè-
àíãóëÿöèé ñûíîâåé óçëà �
íåîáõîäèìî îïðåäåëèòü âåð-
õíèå è íèæíèå îïîðíûå âåð-
øèíû CH S L( ) è CH S R( )
ñîîòâåòñòâóþùèõ òðèàíãó-
ëÿöèé è ñîåäèíèòü èõ âåðõ-
íèì è íèæíèì îïîðíûìè
îòðåçêàìè. Êàæäûé ïðîöåñ-
ñîð, äâèãàÿñü ïî îäíîé èç
âçàèìíî âûïóêëûõ öåïåé
ìåæäó âåðõíèì è íèæíèì
îïîðíûìè îòðåçêàìè, ïðî-
âîäèò îòðåçîê ê ñâîåé âåð-
øèíå äðóãîé öåïè. Ïðîöåññ
ïðîäîëæàåòñÿ äî òåõ ïîð,
ïîêà íå áóäåò äîñòèãíóò íèæ-
íèé îïîðíûé îòðåçîê. Ïîëó-
÷åííûå òàêèì ñïîñîáîì òðèàí-
ãóëÿöèè ïåðåäàþòñÿ íà ñëåäó-
þùèé óðîâåíü ðåêóðñèè.
Äëÿ âûïîëíåíèÿ âûøå-
îïèñàííûõ îïåðàöèé íàèáî-
ëåå ïîäõîäÿùåé (êàê è äëÿ
ïðåäûäóùåé ïðîöåäóðû) áó-
äåò ñöåïëÿåìàÿ î÷åðåäü, êî-
òîðàÿ ðåàëèçóåò ýòàï ñëèÿ-
íèÿ òðèàíãóëÿöèé çà ëîãà-
ðèôìè÷åñêîå âðåìÿ. Íà ðèñ. 4 ïðîäåìîíñòðèðîâàí ïðèìåð ïîøàãîâîãî ýòàïà
ñëèÿíèÿ òðèàíãóëÿöèé.
Ëåììà 3. Ýòàï ðåêóðñèâíîãî ñëèÿíèÿ â çàäà÷å òðèàíãóëÿöèè ìíîæåñòâà S èç N
òî÷åê íà ïëîñêîñòè ñ ïîìîùüþ Î N( ) ïðîöåññîðîâ ìîæíî âûïîëíèòü çà âðåìÿ
� (log )2 N .
2.3. Ïðîöåäóðà ñëèÿíèÿ çàäà÷è ïîñòðîåíèÿ äèàãðàììû Âîðîíîãî. Ñõåìà
«ðàçäåëÿé è âëàñòâóé» èìååò óñïåøíîå ïðèìåíåíèå è ïðè ïîñòðîåíèè äèàãðàììû
Âîðîíîãî äëÿ ìíîæåñòâà S èç N òî÷åê íà ïëîñêîñòè.  ÷àñòíîñòè, Ì. Øåéìî-
ñîì [26] ïðåäëîæåí ýôôåêòèâíûé ïîñëåäîâàòåëüíûé àëãîðèòì ðåøåíèÿ ýòîé çàäà-
÷è íà îäíîïðîöåññîðíîé ìàøèíå ñî âðåìåíåì �( log )N N , à â ðàáîòàõ [1, 4, 27]
îïèñàíû ýôôåêòèâíûå ïàðàëëåëüíûå àëãîðèòìû ñî âðåìåíåì � (log )2 N . Òàêàÿ ýô-
ôåêòèâíîñòü äîñòèãàåòñÿ â ðåçóëüòàòå äåòàëüíîãî àíàëèçà ãðàíèö äèàãðàìì Âîðî-
íîãî â çîíå ðàçäåëÿþùåé ïðÿìîé. Â äàííîì ðàçäåëå ýòàï ñëèÿíèÿ àëãîðèòìà ïî-
ñòðîåíèÿ äèàãðàììû Âîðîíîãî îòëè÷àåòñÿ îò ýòàïà ñëèÿíèÿ çàäà÷è âûïóêëîé îáî-
ëî÷êè ëèøü òåì, ÷òî â ïåðâîé çàäà÷å íà çàâåðøàþùåì øàãå ñòðîèòñÿ ðàçäåëÿþùàÿ
öåïü, êîòîðàÿ ñîåäèíÿåò äèàãðàììû Âîðîíîãî ñûíîâåé, à âî âòîðîé ïðîâîäÿòñÿ
16 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 2
P2
P1
P3
S1
S11 S12 S21 S22 S2
T (S11)
P4
P6
P9
P10
P11
P12P7
T (S22)
l1 l2l
l1 l2l
P9P2
P1
P3
UL � CH(S1) UR � CH(S2)
P10
P11
P12
P7
P8P6
P5
P4
S1 S2
l1 l2l
P9P2
P1
P3
P10
P11
P12
P7
P8
P6
P5
P4
P5
S11 S12 S21 S22
S11 S12 S21 S22
T (S)
P8
T (S12)
T (S21)
T (S1)
T (S2)
Ðèñ. 4. Ïðèìåð ïîøàãîâîãî ñëèÿíèÿ òðèàíãóëÿöèé
Øàã 1
Øàã 2
Øàã 3
îïîðíûå îòðåçêè ê âûïóêëûì îáîëî÷êàì ñûíîâåé. Ïðè ýòîì ðåçóëüòàòû ïîñòðîå-
íèÿ âûïóêëûõ îáîëî÷åê è îïîðíûõ îòðåçêîâ, ïîëó÷åííûå â çàäà÷å î âûïóêëîé
îáîëî÷êå, èñïîëüçóþòñÿ äëÿ ñëåäóþùèõ øàãîâ çàäà÷è ïîñòðîåíèÿ äèàãðàììû
Âîðîíîãî.
Ïîñòàíîâêà çàäà÷è. Íà ïëîñêîñòè çàäàíî ìíîæåñòâî S èç N òî÷åê. Íåîáõîäè-
ìî ðàçðàáîòàòü ýôôåêòèâíóþ ïðîöåäóðó ñëèÿíèÿ ïàðàëëåëüíî-ðåêóðñèâíîãî àëãî-
ðèòìà ïîñòðîåíèÿ äèàãðàììû Âîðîíîãî äëÿ ýòîãî ìíîæåñòâà òî÷åê.
Ñëèÿíèå ðåçóëüòàòîâ (ðåêóðñèâíûé ïîäúåì). Íà êàæäîì øàãå ðåêóðñèâíîãî
ïîäúåìà, íà÷èíàÿ ñî âòîðîãî, íà âõîä ðîäèòåëüñêîãî óçëà � äåðåâà ïîäàþòñÿ äèà-
ãðàììû Âîðîíîãî (ÄÂ) äëÿ ïîäìíîæåñòâà òî÷åê îò ëåâîãî ñûíà vor ( )S L è ïðàâîãî
ñûíà vor ( )S R . Íåîáõîäèìî ïîñòðîèòü ÄÂ äëÿ óçëà �. Âðåìÿ, êîòîðîå ðàñõîäóåòñÿ
íà ýòàï ðåêóðñèâíîãî ñëèÿíèÿ ðåøåíèÿ çàäà÷è â ñëó÷àå ïàðàëëåëüíîãî àëãîðèòìà,
îïðåäåëÿåòñÿ ñëåäóþùåé ëåììîé.
Ëåììà 4. Ýòàï ðåêóðñèâíîãî ñëèÿíèÿ äèàãðàìì Âîðîíîãî ìíîæåñòâà S èç N
òî÷åê íà ïëîñêîñòè ñ ïîìîùüþ Î N( ) ïðîöåññîðîâ ìîæíî âûïîëíèòü çà âðåìÿ
Î N(log )2 .
Procedura (ÑËÈßÍÈÅ_ÄÈÀÃÐÀÌÌÀ ÂÎÐÎÍÎÃÎ) (vor ( )S L , vor ( )S R )
Äëÿ ïîñòðîåíèÿ ñëèÿíèÿ äèàãðàìì Âîðîíîãî â óçëå � íåîáõîäèìî ñëåäóþùåå.
1. Îïðåäåëèòü âåðõíèå è íèæíèå îïîðíûå âåðøèíû ëåâîé è ïðàâîé ãðàíèö
âûïóêëûõ îáîëî÷åê CH S L( ) è CH S R( ) ñûíîâåé, à ñëåäîâàòåëüíî, âåðõíåå è íèæíåå
îïîðíûå ðåáðà ñîîòâåòñòâåííî.
2. Ïðîâåñòè âõîäÿùåå è âûõîäÿùåå ðåáðà ðàçäåëÿþùåé öåïè äëÿ âåðõíåãî è
íèæíåãî îïîðíûõ îòðåçêîâ äî ïåðåñå÷åíèÿ ñ îäíèì èç ðåáåð äèàãðàìì vor ( )S L èëè
vor ( )S R (ðèñ. 5).
3. Ïðîâåñòè ïðîöåññ
ïîñòðîåíèÿ ðàçäåëÿþùåé
öåïè ñ èñïîëüçîâàíèåì
Î N( ) ïðîöåññîðîâ äëÿ
ïðèãðàíè÷íûõ ìíîæåñòâ
òî÷åê îòíîñèòåëüíî ðàçäå-
ëÿþùåé âåðòèêàëè l, êî-
òîðûå ðàñïîëîæåíû ñëåâà
è ñïðàâà îò íåå è ïðèíàä-
ëåæàò âçàèìíî âûïóêëûì
öåïÿì âûïóêëûõ îáîëî-
÷åê ñûíîâåé, à òàêæå òî-
÷åê, îïðåäåëÿåìûõ ðåáðà-
ìè äèàãðàìì vor ( )S L ,
vor ( )S R , êîòîðûå ïåðåñå-
êàþò ðåáðà ýòèõ öåïåé.
4. Ïîëó÷åííûå ïîñëå
ñëèÿíèÿ òàêèì ñïîñîáîì
äèàãðàììû Âîðîíîãî ïåðåäàòü íà ñëåäóþùèé óðîâåíü ðåêóðñèè (ñì. ðèñ. 1).
Ïðîöåññ ñëèÿíèÿ çàâåðøàåòñÿ, êîãäà áóäåò ïîñòðîåíà ðàçäåëÿþùàÿ öåïü äëÿ
êîðíÿ äåðåâà, à çíà÷èò è äèàãðàììà Âîðîíîãî ìíîæåñòâà òî÷åê S .
Ðàññìîòðèì áîëåå äåòàëüíî øàã 3.
Ëåììà 5. Ïîñòðîåíèå ðàçäåëÿþùåé öåïè �( , )S S1 2 , êîòîðàÿ «ñøèâàåò» äèà-
ãðàììû Âîðîíîãî vor ( )S L , vor ( )S R , íà êàæäîì øàãå ýòàïà ñëèÿíèÿ ìîæíî âûïîë-
íèòü çà âðåìÿ Î N(log ) ñ èñïîëüçîâàíèåì Î N( ) ïðîöåññîðîâ.
Äîêàçàòåëüñòâî. Ìåæäó âåðõíèìè è íèæíèìè îïîðíûìè ðåáðàìè äâóõ âû-
ïóêëûõ îáîëî÷åê äèàãðàìì Âîðîíîãî ñûíîâåé vor ( )S L , vor ( )S R íåêîòîðîãî óçëà �
ãðàôà àëãîðèòìà èìååì äâå âçàèìîâûïóêëûå öåïè, êîòîðûå è îïðåäåëÿþò îáëàñòü
ïîñòðîåíèÿ D ðàçäåëÿþùåé öåïè (ðèñ. 6). Êàæäàÿ öåïü îïðåäåëÿåò óïîðÿäî÷åííûé
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 2 17
UL � CH(S1) UR � CH(S2)
S1 S2
l1 l22
l
P9P2
P1
P3
P10
P11
P12P7
P8
P6
P5
P4
S11 S12 S21 S22
vor(S2)vor(S1)
S111 S112 S121
l11 l12 l21
S211 S212 S221 S222
l2
Ðèñ. 5. Ïðèìåð ñëèÿíèÿ äèàãðàìì Âîðîíîãî
íàáîð ðåáåð äèàãðàììû Âîðîíîãî, íàïðàâëåííûõ â ñåðåäèíó îáëàñòè D è ïåðåñåêà-
þùèõ ðåáðà âçàèìíî âûïóêëûõ öåïåé CHL , CHR . Êàæäîå ðåáðî öåïåé CHL , CHR
ìîæåò ïåðåñåêàòüñÿ ñ ðåáðàìè äèàãðàìì Âîðîíîãî è òåì ñàìûì îïðåäåëÿòü
ìíîæåñòâî òî÷åê, ðàçäåëåííîå ýòèìè ðåáðàìè. Îáîçíà÷èì ìíîæåñòâî âåðøèí, êîòîðîå
ñîñòîèò èç âåðøèí âûïóêëîé öåïè CHL ( )CHR è òî÷åê, îïðåäåëåííûõ ðåáðàìè äèàã-
ðàìì Âîðîíîãî, êîòîðûå ïåðåñåêàþò öåïü, ÷åðåç B SL ( )1 ( ( ))B SR 2 è íàçîâåì åãî ëå-
âîïðåäåëüíûì (ïðàâîïðåäåëüíûì) óïîðÿäî÷åííûì ìíîæåñòâîì òî÷åê (ñïèñêîì). Ñîå-
äèíèâ ïîñëåäîâàòåëüíî òî÷êè â ñïèñêàõ B SL ( )1 è B SR ( )2 , ïîëó÷èì ñïèñêè ðåáåð
E SL ( )1 , E SR ( )2 , êîòîðûå îáðàçóþò öåïè ÑL è ÑR ñîîòâåòñòâåííî (ðèñ. 6). Çäåñü
B S P P P P P P P PL ( ) { , , , , , , , }1 1 2 3 4 5 6 7 8� , B S P P P P P P PR ( ) { , , , , , , }2 9 10 11 12 13 14 15�
— ñïèñêè ïðèãðàíè÷íûõ òî÷åê; CL è CR — ëåâàÿ è ïðàâàÿ ìîíîòîííûå öåïè ìåæäó
îïîðíûìè îòðåçêàìè, äëÿ êîòîðûõ ñòðîèòñÿ ðàçäåëÿþùàÿ öåïü. Âåðõíÿÿ öåïü
� A a a a a a a a a� { , , , , , , , }1 2 3 4 5 6 7 8 è íèæíÿÿ öåïü � B b b b b b� { , , , , }1 2 3 4 5 ñîîòâåò-
ñòâóþò ïàðàì ìîíîòîííûõ öåïåé ( , )C CL R1 1 è ( , )C CL R2 2 .
Ëåììà 6. Öåïè ÑL è ÑR ÿâëÿþòñÿ ìîíîòîííûìè îòíîñèòåëüíî ïðÿìîé l.
Äîêàçàòåëüñòâî. Äîêàæåì îò ïðîòèâíîãî. Èçâåñòíî, ÷òî ðàçäåëÿþùàÿ öåïü
�( , )S S1 2 îáÿçàòåëüíî äîëæíà áûòü ìîíîòîííîé îòíîñèòåëüíî ïðÿìîé l. Ïóñòü
õîòÿ áû îäíà èç öåïåé ÑL è ÑR áóäåò íå ìîíîòîííîé îòíîñèòåëüíî l. Òîãäà íàéäåò-
ñÿ ðåáðî ýòîé öåïè, êîòîðîå èìååò óãîë ïîâîðîòà îòíîñèòåëüíî îñè ÎÕ ñ íà÷àëîì â
êîíöå òåêóùåãî ðåáðà � �� , à ñëåäîâàòåëüíî, ñîîòâåòñòâóþùåå ðåáðî äèàãðàììû
Âîðîíîãî íå ïîïàäåò â îáëàñòü D è ðàçäåëÿþùàÿ öåïü � íå áóäåò ìîíîòîííîé, ÷òî
ïðîòèâîðå÷èò óñëîâèþ.
18 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 2
P3
P2
�B
�P15
b5
P8
P7
P6
P5
P4
P1
P14
P13
P12
P11
P10
P9
a8
b4
b3
b2
b1
a7
a6a5
a4
a3
a1
a2
l
D
vor(SR)
vor(SL)
Ðèñ. 6. Øàã ñëèÿíèÿ äâóõ ðàçäåëÿþùèõ öåïåé â îáëàñòè D
Ñëåäóåò îòìåòèòü, ÷òî ïðîöåäóðó ñëèÿíèÿ â êàæäîì óçëå äåðåâà àëãîðèòìà
ìîæíî âûïîëíÿòü íåçàâèñèìî è ïàðàëëåëüíî íà íåñêîëüêèõ ïðîöåññîðàõ. Äëÿ âû-
ïîëíåíèÿ âûøåïðèâåäåííûõ îïåðàöèé çà ëîãàðèôìè÷åñêîå âðåìÿ èñïîëüçóåòñÿ òà
æå ñòðóêòóðà äàííûõ, ÷òî è â çàäà÷å î âûïóêëîé îáîëî÷êå — ñöåïëÿåìàÿ î÷åðåäü
ñ çàäàííîé íà íåé ïðîöåäóðîé ÑÎÅÄÈÍÈÒÜ (UL , UR ). Îíà ïîçâîëÿåò ýôôåêòèâíî
ñòðîèòü ðàçäåëÿþùóþ öåïü.
Äëÿ îðãàíèçàöèè ïðîöåññà ïîñòðîåíèÿ ðàçäåëÿþùåé öåïè íà îñíîâå ñïèñêîâ
B SL ( )1 è B SR ( )2 ñîçäàäèì ñîîòâåòñòâóþùèå ñòðóêòóðû äàííûõ (ðèñ. 7), çàãðóçèâ
èõ íåîáõîäèìîé èíôîðìàöèåé. Ñöåïëÿåìûå î÷åðåäè îáåèõ ìîíîòîííûõ öåïåé
ïðåäñòàâëÿþò áèíàðíîå äåðåâî ñ êîðíåì, â óçëàõ êîòîðîãî èìååì êîîðäèíàòû âåð-
øèí, à äóãè ïðåäñòàâëÿþò ñîîòâåòñòâóþùèå ðåáðà ek ( , )k N� 1 èç ñïèñêîâ öåïåé
E SL ( )1 è E SR ( )2 . Êðîìå òîãî, óçëû çàãðóæåíû óêàçàòåëÿìè íà ñîîòâåòñòâóþùèå
ðåáðà äèàãðàììû Âîðîíîãî. Îáîçíà÷èì d ³ j Nij , , � , èìåíà ðåáåð vor ( )S1 , vor ( )S 2 ,
êîòîðûå ëåæàò â îáëàñòè D.
Òàêèå ñòðóêòóðû äàííûõ ïîçâîëÿþò ïîñòðîèòü ðàçäåëÿþùóþ öåïü �( , )S S1 2
ñ ïîìîùüþ Î N( ) ïðîöåññîðîâ çà âðåìÿ Î N(log ). Ñõåìó àëãîðèòìà ïîñòðîåíèÿ ðàç-
äåëÿþùåé öåïè ìîæíî òàêæå ïðåäñòàâèòü â âèäå áèíàðíîãî äåðåâà. Â ëèñòüÿõ äåðåâà
êàæäûì èç Î N( ) ïðîöåññîðîâ ñòðîèòñÿ ðàçäåëÿþùàÿ öåïü äëÿ ñîîòâåòñòâóþùèõ ïàð
ðåáåð ( , )e ek l ( ( )e E Sk L� 1 , e E Sl R� ( )2 ). Ïîëó÷åííûå ðåçóëüòàòû ïîäàþòñÿ íà ñëå-
äóþùèé óðîâåíü äåðåâà, ãäå îñóùåñòâëÿåòñÿ øàã ñëèÿíèÿ, â ðåçóëüòàòå ÷åãî ñòðîèòñÿ
ðàçäåëÿþùàÿ öåïü — îáúåäèíåíèå ðàçäåëÿþùèõ öåïåé ñûíîâåé. Ïðîöåññ ñëèÿíèÿ
ðàçäåëÿþùèõ öåïåé ñûíîâåé òðåáóåò Î ( )1 âðåìåíè äëÿ êàæäîãî óçëà äåðåâà. Êàê âè-
äèì, âñå îïåðàöèè ïðè ïîñòðîåíèè ðàçäåëÿþùåé öåïè òðåáóþò íå áîëåå ÷åì
Î N(log ) âðåìåíè ïðè èñïîëüçîâàíèè Î N( ) ïðîöåññîðîâ. Ñáàëàíñèðîâàííûå äå-
ðåâüÿ, êîòîðûå áóäóò ïîääåðæèâàòü âåðõíþþ è íèæíþþ âûïóêëûå îáîëî÷êè óçëà �,
îáðàçóþòñÿ ïóòåì ñëèÿíèÿ îñòàâøèõñÿ ÷àñòåé äåðåâüåâ. Ïîëó÷åííûå òàêèì îáðàçîì
äåðåâüÿ ïîääåðæèâàþò âûïóêëóþ îáîëî÷êó è ðåáðà äèàãðàììû Âîðîíîãî, ïåðåñåêà-
þùèå åå, à òàêæå îïðåäåëÿþò ðåáðà ìîíîòîííûõ öåïåé îáëàñòè D, ÷òî ïîçâîëÿåò âû-
ïîëíÿòü ïðîöåäóðû ïîñòðîåíèÿ ðàçäåëÿþùåé öåïè çà âðåìÿ Î N(log ).
2.4. Ïðîöåäóðà ñëèÿíèÿ çàäà÷è î âñåõ áëèæàéøèõ ñîñåäÿõ.  ðàáîòàõ
[1, 26] â ðåçóëüòàòå äåòàëüíîãî àíàëèçà êà÷åñòâåííûõ âîçìîæíîñòåé äèàãðàììû
Âîðîíîãî ñäåëàí äîñòàòî÷íî âàæíûé âûâîä, êîòîðûé ìîæíî ñôîðìóëèðîâàòü
â âèäå ñëåäóþùåãî îáîáùåííîãî óòâåðæäåíèÿ.
Òåîðåìà 1. Ñ ïîìîùüþ äèàãðàììû Âîðîíîãî ìíîæåñòâà S èç N òî÷åê â åâêëè-
äîâîé ïëîñêîñòè òàêèå çàäà÷è áëèçîñòè êàê áëèæàéøàÿ ïàðà, âñå áëèæàéøèå ñîñå-
äè, åâêëèäîâî ìèíèìàëüíîå îñòîâîå äåðåâî, òðèàíãóëÿöèÿ, à òàêæå çàäà÷à ïîñòðîå-
íèÿ âûïóêëîé îáîëî÷êè ìîæíî ðåøèòü çà îïòèìàëüíîå âðåìÿ � ( log )N N .
Äåòàëüíîå äîêàçàòåëüñòâî ýòîãî ðåçóëüòàòà äëÿ îäíîïðîöåññîðíîé âû÷èñëè-
òåëüíîé ìàøèíû ïðèâåäåíî â ðàáîòå [26]. Â îñíîâå ýòîãî äîêàçàòåëüñòâà ëåæèò
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 2 19
Ðèñ. 7. Ñöåïëÿåìûå î÷åðåäè äëÿ ëåâîé CL (à) è ïðàâîé CR (á) öåïåé îáëàñòè ñëèÿíèÿ D äèàãðàìì
Âîðîíîãî vor ( )S1 è vor ( )S 2 íà îñíîâå ðèñ. 6
d5
d42d41d21
Ð4
Ð6Ð2
Ð1 Ð3 Ð7Ð5
Ð8
d2
d1
d22 d3
d4
d82d81d71
Ð12
Ð14Ð10
Ð9 Ð11 Ð15Ð13
d7
d6
d72 d73
d8
d7
áà
ïðèíöèï ñâîäèìîñòè. Ýòîò âûâîä ïîçâîëÿåò ïðèìåíèòü äèàãðàììó Âîðîíîãî êàê
èíñòðóìåíò äëÿ ðåøåíèÿ øèðîêîãî êëàññà çàäà÷ âû÷èñëèòåëüíîé ãåîìåòðèè.  íà-
ñòîÿùåé ñòàòüå ýòîò èíñòðóìåíò èñïîëüçóåòñÿ ïðè ðàçðàáîòêå ïðîöåäóðû ñëèÿíèÿ
äëÿ çàäà÷è «âñå áëèæàéøèå ñîñåäè». Òàê êàê ïåðâûé è âòîðîé ýòàïû ðàññìàòðèâàå-
ìîãî ïàðàëëåëüíî-ðåêóðñèâíîãî àëãîðèòìà îáùèå äëÿ âñåãî êîìïëåêñà çàäà÷, òî
ðàññìîòðèì ëèøü ïîñòðîåíèå ïðîöåäóðû ñëèÿíèÿ ýòîé çàäà÷è, êîòîðîå ñîñòîèò
â ñëåäóþùåì.
Íà êàæäîì øàãå ðåêóðñèâíîãî ïîäúåìà, íà÷èíàÿ ñî âòîðîãî, íà âõîä ðîäèòåëü-
ñêîãî óçëà � ãðàôà àëãîðèòìà (ñì. ðèñ. 1) ïîäàþòñÿ äèàãðàììû Âîðîíîãî îò ëåâîãî
è ïðàâîãî ñûíîâåé vor ( )S1 è vor ( )S 2 , à òàêæå áëèæàéøèé ñîñåä êàæäîé òî÷êè ïîä-
ìíîæåñòâ S L è S R . Ñòðîèòñÿ äèàãðàììà Âîðîíîãî äëÿ óçëà � è ïàðàëëåëüíî îïðå-
äåëÿþòñÿ íîâûå ñîñåäè íà ãðàíèöàõ ïîäìíîæåñòâ S L è S R îòíîñèòåëüíî l.
Ïðè ïîñòðîåíèè ðàçäåëÿþùåé öåïè äèàãðàììû Âîðîíîãî ïàðàëëåëüíî îñóùå-
ñòâëÿåòñÿ ïîèñê áëèæàéøèõ ñîñåäåé ñðåäè òî÷åê ïîäìíîæåñòâ S L è S R , êîòîðûå
îáðàçóþò òåêóùóþ ïàðó ðåáåð öåïè �( , )S SL R . Ïðè ýòîì ñëåäóþùàÿ ïàðà, îïðåäå-
ëÿþùàÿ íîâîå ðåáðî ðàçäåëÿþùåé öåïè, ïðîâåðÿåòñÿ íà íàëè÷èå íîâîãî áëèæàéøå-
ãî ñîñåäà. Íà ãðàôå àëãîðèòìà (ñì. ðèñ. 1) ìíîæåñòâî ïàð áëèæàéøèõ ñîñåäåé äëÿ S
îáîçíà÷åíî NN S( ) è äëÿ ïîäìíîæåñòâ S L è S R — ñîîòâåòñòâåííî NN S L( ),
NN S R( ). Íà ðèñ. 8 äàí ïðèìåð ïðîöåññà íàõîæäåíèÿ áëèæàéøèõ ñîñåäåé íà ýòàïå
ñëèÿíèÿ. Êàê âèäèì, äëÿ Ð S R8 � íàéäåí íîâûé áëèæàéøèé ñîñåä P S L6 � .
Ïîñêîëüêó âðåìÿ ïîñòðîåíèÿ ìîíîòîííîé ðàçäåëÿþùåé öåïè íà øàãå ñëèÿíèÿ
äâóõ äèàãðàìì Âîðîíîãî ñ ïîìîùüþ Î N( ) ïðîöåññîðîâ ðàâíî Î N(log ) , òî è âðåìÿ
ñëèÿíèÿ ðåçóëüòàòîâ íàõîæäåíèÿ áëèæàéøèõ ñîñåäåé èìååò òîò æå ïîðÿäîê.
Äåéñòâèòåëüíî, êàæäîå ðåáðî ðàçäåëÿþùåé öåïè îïðåäåëÿåò ïîèñê áëèæàéøå-
ãî ñîñåäà äëÿ ïàðû òî÷åê, êîòîðóþ ýòî ðåáðî ðàçäåëÿåò. Äîñòàòî÷íî ëèøü ñðàâíèòü
âåëè÷èíû äâóõ ðàññòîÿíèé. Òàêèì îáðàçîì, ìîæíî ñäåëàòü âûâîä.
Ëåììà 7. Ýòàï ðåêóðñèâíîãî ñëèÿíèÿ ðåçóëüòàòîâ íàõîæäåíèÿ áëèæàéøèõ ñî-
ñåäåé äëÿ êàæäîé òî÷êè ìíîæåñòâà S èç N òî÷åê íà ïëîñêîñòè ñ ïîìîùüþ Î N( )
ïðîöåññîðîâ ìîæíî âûïîëíèòü çà âðåìÿ Î N(log )2 .
3. ÐÅÀËÈÇÀÖÈß ÀËÃÎÐÈÒÌÀ
Äëÿ ïðàêòè÷åñêîé ðåàëèçàöèè ðàçðàáîòàííîãî àëãîðèòìà ïðèìåíÿëñÿ îäèí èç ýô-
ôåêòèâíûõ ïîäõîäîâ, îñíîâàííûé íà èñïîëüçîâàíèè òåõíîëîãèè ïðîãðàììèðîâà-
20 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 2
å4
å2
å3
�87
�65
å1
åâõ
�6
P7
P8
qÂOR
P10
P12
P6
P5
P4
P3
qÂOL
P1
l
P11
SL SR
vor(SL) vor(SR)
NN(SR)NN(SL)
Ðèñ. 8. Ïðèìåð íàõîæäåíèÿ áëèæàéøèõ ñîñåäåé äëÿ ïàð òî÷åê ( , )Ð qÂÎR3 , ( , )Ð Ð3 8 , ( , )Ð Ð6 8 , ( , )Ð Ð6 7 ,
( , )Ð Ð5 7
íèÿ â ñòàíäàðòå MPI. Ýòîò ïîäõîä ïîçâîëÿåò äîñòàòî÷íî ëåãêî ðåàëèçîâàòü
èìåííî ðåêóðñèâíî-ïàðàëëåëüíûå àëãîðèòìû ðåøåíèÿ ñëîæíûõ çàäà÷ êàê íà
ìíîãîïðîöåññîðíûõ ìàøèíàõ (êëàñòåðàõ), òàê è â êîìïüþòåðíîé ñåòè. Â íàñòîÿ-
ùåé ñòàòüå ïðîâåäåíî íåñêîëüêî èññëåäîâàíèé îòíîñèòåëüíî ñêîðîñòè ðåøåíèÿ
ðàçðàáîòàííîãî àëãîðèòìà äëÿ öåëîãî êîìïëåêñà çàäà÷ âè÷èñëèòåëüíîé ãåîìåò-
ðèè, èñïîëüçóÿ ðàçëè÷íûå ñïîñîáû ðåàëèçàöèè ïðîãðàììû.
Ãëàâíàÿ ôóíêöèÿ ýòîé ïðîãðàììû main (int argc, char *argv[]) óñëîâíî ðàçäåëå-
íà íà òðè ÷àñòè. Ïåðâàÿ ÷àñòü ôóíêöèè — îñóùåñòâëåíèå èíèöèàëèçàöèè ñðåäû
MPI íåïîñðåäñòâåííî ïîñëå îáúÿâëåíèÿ ñàìîé ôóíêöèè . Ýòà ÷àñòü ôóíêöèè âû-
ïîëíÿåòñÿ âñåìè ïðîöåññîðàìè.
Âòîðàÿ ÷àñòü ôóíêöèè — ýòî òà ÷àñòü ïðîãðàììû, êîòîðàÿ âûïîëíÿåòñÿ ëèøü
íà íóëåâîì ïðîöåññîðå è íåïîñðåäñòâåííî íå ó÷àñòâóåò â ïðîöåññå ñëèÿíèÿ äâóõ
ïîäçàäà÷. Ïðîãðàììà ðàáîòàåò ñëåäóþùèì îáðàçîì: ñíà÷àëà èäåò ïðîâåðêà ôóíê-
öèÿìè is_free_proc è get_free_reg íà íàëè÷èå ñâîáîäíûõ ïðîöåññîðîâ è ñâîáîäíûõ
ðåãèîíîâ. Åñëè òàêîâûå îòñóòñòâóþò, òî îæèäàåòñÿ ïîñòóïëåíèå ðåçóëüòàòîâ îò
äðóãèõ ïðîöåññîðîâ. Ïðè ýòîì èäåò ðàñïàêîâêà äàííûõ, îñâîáîæäàåòñÿ ïàìÿòü îò
óæå îáðàáîòàííûõ è íåíóæíûõ ðåãèîíîâ, ïîâûøàåòñÿ óðîâåíü ðåêóðñèè ðåãèîíà,
êîòîðûé îáðàáàòûâàåò äðóãîé ïðîöåññîð (ïîëå level òèïà zone), à â ìàññèâå procs
ôèêñèðóåòñÿ, ÷òî ³-é ïðîöåññîð îñâîáîäèëñÿ.
Íà ñëåäóþùåì øàãå ïðîèñõîäèò ïåðåõîä ê ñòàäèè ïåðåäà÷è äàííûõ ñâîáîäíî-
ìó ïðîöåññîðó ñâîáîäíûõ ðåãèîíîâ ñ íàèìåíüøèì âîçìîæíûì çíà÷åíèåì ïîëÿ
level è ñíîâà âûïîëíÿåòñÿ ïðîâåðêà âîçìîæíîñòè ïîñëåäóþùèõ âû÷èñëåíèé è ïðè-
åì ñîîáùåíèé îò äðóãèõ ïðîöåññîðîâ äî òåõ ïîð, ïîêà íå îñòàåòñÿ îäèí ðåãèîí.
Òðåòüÿ ÷àñòü ôóíêöèè — îïèñàíèå äåéñòâèÿ äðóãèõ ïðîöåññîðîâ ñ íåíóëåâûì
íîìåðîì. Çäåñü öèêëè÷åñêè ïðîèñõîäèò ïðèåì äàííûõ îò íóëåâîãî ïðîöåññîðà,
ðàñïàêîâêà äàííûõ, ðàñïðåäåëåíèå äàííûõ (ðåêóðñèâíûé ñïóñê), âî âðåìÿ êîòîðîãî
çàïîëíÿåòñÿ äèíàìè÷åñêèé ñïèñîê ñ çàãëàâèåì head1. Âûçûâàþòñÿ ôóíêöèè ñëèÿ-
íèÿ ñîîòâåòñòâóþùèõ çàäà÷, ãäå ñëèâàþòñÿ ðåçóëüòàòû, ïîëó÷åííûå îò íóëåâîãî
ïðîöåññîðà. Ïðè ýòîì ïàðàëëåëüíî îäíà ïðîöåäóðà ñëèÿíèÿ ìîæåò èñïîëüçîâàòü
ðåçóëüòàòû äðóãîé. Ïîñëå çàâåðøåíèÿ ðàáîòû ïðîöåäóð ñëèÿíèÿ àëãîðèòìà ïðîèñ-
õîäèò çàïàêîâêà äàííûõ, êîòîðûå ïîñûëàþòñÿ íóëåâîìó ïðîöåññîðó, è ñíîâà îæè-
äàþòñÿ äàííûå îò òàêîãî ïðîöåññîðà äëÿ îáðàáîòêè.
Ïðîãðàììà èìååò ìîäóëüíûé õàðàêòåð è ïîçâîëÿåò â áóäóùåì èñïîëüçîâàòü åå
äëÿ ðåøåíèÿ òðóäîåìêèõ çàäà÷ âû÷èñëèòåëüíîé ãåîìåòðèè è êîìïüþòåðíîãî ìîäå-
ëèðîâàíèÿ, êîòîðûå ðàçðåøèìû ñ ïîìîùüþ ñõåìû «ðàçäåëÿé è âëàñòâóé». Ñ ó÷å-
òîì ñëîæíîñòè íîâûõ ðåøàåìûõ çàäà÷ è ðàñøèðåíèÿ îáëàñòè ïðèìåíåíèÿ çàäà÷
âû÷èñëèòåëüíîé ãåîìåòðèè àêòóàëüíîñòü òàêèõ ðåøåíèé âîçðàñòàåò. Îñîáåííî ýòî
êàñàåòñÿ âû÷èñëèòåëüíîé òî÷íîñòè è ýôôåêòèâíîñòè ðåøåíèÿ ðàññìîòðåííûõ çàäà÷.
ÇÀÊËÞ×ÅÍÈÅ
 íàñòîÿùåé ñòàòüå áëàãîäàðÿ óäà÷íî âûáðàííûì ñòðóêòóðàì äàííûõ — ñòðóê-
òóðèðîâàííîãî ìàññèâà òî÷åê íà âõîäå äåðåâà àëãîðèòìà è ïîääåðæêè ýëåìåíòîâ
ïðîöåäóð ñëèÿíèÿ â âèäå ñöåïëÿåìîé î÷åðåäè â êàæäîì óçëå äåðåâà àëãîðèòìà
óäàëîñü ðàçðàáîòàòü îáîáùåííûé ýôôåêòèâíûé ðåêóðñèâíî-ïàðàëëåëüíûé àëãî-
ðèòì àñèíõðîííîãî ðåøåíèÿ êîìïëåêñà âçàèìîñâÿçàííûõ çàäà÷. Ýòîò àëãîðèòì
ðåøàåò îäíîâðåìåííî íà O N( )-ïðîöåññîðíîé ñèñòåìå íåêîòîðóþ ñîâîêóïíîñòü
âçàèìîñâÿçàííûõ çàäà÷ âû÷èñëèòåëüíîé ãåîìåòðèè ñ ýôôåêòèâíîñòüþ íå õóæå,
÷åì çà Î N(log )2 âðåìåíè, ò.å. ïðèíàäëåæèò êëàññó NÑ2 . Õàðàêòåðíûì äëÿ
ïðàêòè÷åñêîé ðåàëèçàöèè äàííîãî ïîäõîäà ÿâëÿåòñÿ òî, ÷òî ðàçðàáîòàííûé àëãî-
ðèòì ïîçâîëÿåò îäíîâðåìåííî ðåøàòü ñ ïîìîùüþ òåõíîëîãèé MPI êàê ðàçíûå
øàãè îäíîé ïðîöåäóðû çàäà÷è íà ìíîãèõ ïðîöåññîðàõ, òàê è ðàçíûå ïðîöåäóðû
â îäíîì óçëå àëãîðèòìà.
Äðóãàÿ îñîáåííîñòü ýòîé ìîäåëè àëãîðèòìà çàêëþ÷àåòñÿ â òîì, ÷òî ýòàïû 1 è 2
ÿâëÿþòñÿ îáùèìè äëÿ ðåøåíèÿ ðàññìàòðèâàåìîãî ìíîæåñòâà êëàññîâ çàäà÷ è îòëè-
÷àþòñÿ ëèøü ïðîöåäóðàìè íà ýòàïå ñëèÿíèÿ. Ýòî è ïîçâîëÿåò ðàçðàáîòàòü îáîáùåí-
íûé àëãîðèòì ðåøåíèÿ çà åäèíîé ñõåìîé öåëîãî ðÿäà çàäà÷ âû÷èñëèòåëüíîé ãåî-
ìåòðèè è çàäà÷, êîòîðûå ñâîäÿòñÿ ê íèì.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 2 21
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. P a r a l l e l computational geometry / À. Aggarwal, B. Chazelle, L. Guibas, C. O’Dunlaing, C.Ê. Yap //
Algorithmica. — 1988. — 3. — P. 293–327.
2. A t a l l a h M . J . , C o l e R . , G o o d r i c h M . T . Cascading divide-and-conquer: A technique for de-
signing parallel algorithms // SIAM J. Comput. — 1989. — 18. — P. 499–532.
3. C o l e R . , G o o d r i c h M . T . Optimal parallel algorithms for polygon and point-set problems //
Algorithmica. — 1992. — 7. — P. 3–23.
4. A m a t o N . M . , G o o d r i c h M . T . , R a m o s E . A . Parallel algorithms for higher-dimensional con-
vex hulls // Proc. 35th Annu. IEEE Sympos. Found. Comput. Sci., 1994. — P. 683–694.
5. C h e n D . Efficient geometric algorithms on the EREW PRAM // IEEE Trans. Parallel Distrib. Syst. —
1995. — 6. — P. 41–47.
6. B e r k m a n O . , S c h i e b e r B . , V i s h k i n U . A fast parallel algorithm for finding the convex hull of
a sorted point set // Internat. J. Comput. Geom. Appl. — 1996. — 6. — P. 231–242.
7. G o o d m a n J . E . , O ’ R o u r k e J . Handbook of discrete and computational geometry. — N.Y.: Chap-
man and Hall/CRC Press, 2004. — 1497 p.
8. A k l S . G . , L y o n s K . A . Parallel computational geometry. — Englewood Cliffs: Prentice-Hall, 1993.
— 224 p.
9. J a j a J . An introduction to parallel algorithms. — Amsterdam: Addison-Wesley, 1992. — 566 p.
10. V a n L e e u w e n J . Handbook of theoretical computer science. — Amsterdam: Elsevier/The MIT Press,
1990. — 1294 p.
11. R e i f J . H . Synthesis of parallel algorithms. — San Mateo: Morgan Kaufmann, 1993. — 1011 p.
12. B e n - O r M . Lower bounds for algebraic computational trees // Proc. 15th ACM Symposium on Theory
Computing, 1983. — P. 80–86.
13. K o z e n D . , Y a p C . K . Algebraic ñåll decomposition in NC // Proc. 26th IEEE FOCS Symposium,
1985. — P. 515–521.
14. A j t a i M . , K o m l o s J . , S z e m e r e d i E . An Î n n( log( )) sorting network // Combinatorica. — 1983.
— 3, N 1. — P. 1–19.
15. L e i g h t o n T . Tight bounds on complexity parallel sorting // Proc. 16th ACM Symposium on Theory
Computing, 1984. — P. 71–80.
16. C o l e R . Parallel merge sort // Proc. 27th IEEE FOCS Symposium, 1986. — P. 511–516.
17. Òå ð å ù å í ê î  . Ì . Îäèí ï³äõ³ä â ðîçðîáö³ åôåêòèâíîãî ðåêóðñèâíî-ïàðàëåëüíîãî àëãîðèòìó
ïîáóäîâè îïóêëî¿ îáîëîíêè ìíîæèíè òî÷îê íà ïëîùèí³ // Òàâðè÷åñ. âåñòíèê èíôîðìàòèêè è ìàòå-
ìàòèêè. — 2007. — ¹ 2. — Ñ. 24–32.
18. Ò å ð å ù å í ê î  . Í . Ïîñòðîåíèå ðåêóðñèâíî-ïàðàëëåëüíûõ àëãîðèòìîâ ðåøåíèÿ çàäà÷ âû÷èñëè-
òåëüíîé ãåîìåòðèè íà îñíîâå ñòðàòåãèè «ðàñïðåäåëÿé è âëàñòâóé» // Òð. ìåæäóíàð. íàó÷. êîíô.
ÏàÂÒ’2008, 2008. — C. 476–482.
19. Òå ð å ù å í ê î  . Ì . Óçàãàëüíåíèé ï³äõ³ä ðîçâ’ÿçàííÿ äåÿêèõ çàäà÷ îá÷èñëþâàëüíî¿ ãåîìåò𳿠íà îñ-
íîâ³ ðåêóðñèâíî-ïàðàëåëüíî¿ òåõíîëî㳿. ×. 2 // Íàóêîâ³ íîòàòêè. — 2008. — ¹ 22. — Ñ. 344–349.
20.  î å â î ä è í  .  . ,  î å â î ä è í  ë .  . Ïàðàëëåëüíûå âû÷èñëåíèÿ. — ÑÏá.: ÁÕÂ-Ïåòåðáóðã,
2002. — 608 ñ.
21. M i l l e r R . , S t o u t Q . F . Efficient parallel convex hull algorithms // IEEE Trans. Comput. — 1988. —
37. — P. 1605–1618.
22. G h o u s e M . , G o o d r i c h M . T . In-place techniques for parallel convex hull algorithms // Proc. 3rd
Annu. ACM Sympos. Parallel Algorithms Architect, 1991. — P. 192–203.
23. O v e r m a r s M . H . , V a n L e e u w e n J . Maintenance configurations in plane // J. Comput. and Syst.
Sci. — 1981. — 23. — P. 166–204.
24. Ñ ê â î ð ö î â À . Â . Òðèàíãóëÿöèÿ Äåëîíå è åå ïðèìåíåíèå. — Òîìñê: Èçä-âî Òîìñê. óí-òà, 2002. —
128 ñ.
25. G o o d r i c h M . T . Planar separators and parallel polygon triangulation // J. Comput. and Syst. Sci. —
1995. — 51, N 3. — P. 374–389.
26. Ï ð å ï à ð à ò à Ô . , Ø å é ì î ñ Ì . Âû÷èñëèòåëüíàÿ ãåîìåòðèÿ: Ââåäåíèå. — Ì.: Ìèð, 1989. —
478 ñ.
27. T e r e s h c h e n k o V . One tool for building visual models // Proc. International Conf. on Comput. Intelli-
gence, Modelling and Simulation. IEEE CS, 2009. — P. 59–62.
Ïîñòóïèëà 06.10.2009
22 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 2
|
| id | nasplib_isofts_kiev_ua-123456789-45140 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0023-1274 |
| language | Russian |
| last_indexed | 2025-11-30T23:33:53Z |
| publishDate | 2010 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Терещенко, В.Н. Анисимов, А.В. 2013-06-08T06:09:31Z 2013-06-08T06:09:31Z 2010 Рекурсия и параллельные алгоритмы в задачах геометрического моделирования / В.Н. Терещенко, А.В. Анисимов // Кибернетика и системный анализ. — 2010. — № 2. — С. 10-22. — Бібліогр.: 27 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/45140 004.925.8, 004.272.2 Розглянуто ефективний підхід до побудови точних комп’ютерних моделей явищ і процесів. На основі стратегії «поділяй та владарюй» розроблено узагальнений паралельно-рекурсивний алгоритм одночасного розв’язання всієї сукупності взаємозв’язаних задач, які використовують спільно єдину структуру даних (зважену зчеплену чергу) на етапі злиття. При цьому етап розбиття спільний і виконується один раз для всіх задач. Це забезпечує ефективні і зручні засоби для побудови і дослідження складних обчислювальних моделей. The paper discusses an efficient approach to accurate computer modeling of phenomena and processes. The “divide-and-conquer” technique is used to develop a generalized parallel-recursive algorithm for simultaneous solution of the totality of interrelated problems that use a common and unified data structure (weighted concatenable queue) at the stage of a merger. The stage of decomposition is common and is executed once for all tasks. This provides efficient and convenient means to construct and study complex computational models. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Кибернетика Рекурсия и параллельные алгоритмы в задачах геометрического моделирования Рекурсія і паралельні алгоритми в задачах геометричного моделювання Recursion and parallel algorithms in geometric modeling problems Article published earlier |
| spellingShingle | Рекурсия и параллельные алгоритмы в задачах геометрического моделирования Терещенко, В.Н. Анисимов, А.В. Кибернетика |
| title | Рекурсия и параллельные алгоритмы в задачах геометрического моделирования |
| title_alt | Рекурсія і паралельні алгоритми в задачах геометричного моделювання Recursion and parallel algorithms in geometric modeling problems |
| title_full | Рекурсия и параллельные алгоритмы в задачах геометрического моделирования |
| title_fullStr | Рекурсия и параллельные алгоритмы в задачах геометрического моделирования |
| title_full_unstemmed | Рекурсия и параллельные алгоритмы в задачах геометрического моделирования |
| title_short | Рекурсия и параллельные алгоритмы в задачах геометрического моделирования |
| title_sort | рекурсия и параллельные алгоритмы в задачах геометрического моделирования |
| topic | Кибернетика |
| topic_facet | Кибернетика |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/45140 |
| work_keys_str_mv | AT tereŝenkovn rekursiâiparallelʹnyealgoritmyvzadačahgeometričeskogomodelirovaniâ AT anisimovav rekursiâiparallelʹnyealgoritmyvzadačahgeometričeskogomodelirovaniâ AT tereŝenkovn rekursíâíparalelʹníalgoritmivzadačahgeometričnogomodelûvannâ AT anisimovav rekursíâíparalelʹníalgoritmivzadačahgeometričnogomodelûvannâ AT tereŝenkovn recursionandparallelalgorithmsingeometricmodelingproblems AT anisimovav recursionandparallelalgorithmsingeometricmodelingproblems |