+ All Categories
Home > Documents > Obsah - FILES. · PDF filed n no ho cyklu pednek blzk c h aplik acm ale s matematic k ou npln...

Obsah - FILES. · PDF filed n no ho cyklu pednek blzk c h aplik acm ale s matematic k ou npln...

Date post: 20-Mar-2018
Category:
Upload: phamminh
View: 214 times
Download: 2 times
Share this document with a friend
77
Transcript

i

Jan Slov�k

Geometrick� algoritmy I�

podle p�edn��ek zpracoval Josef Pojsl��jen ���� � leden ���

Obsah

� Konvexn� mnoho�heln�ky ��� Pr�niky konvexn�ch mnoho�heln�k� � � � � � � � � � � � � � � � � � � � � � � � � � �� Konvexn� obal bod� v rovin� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��� Konvexn� obal mno�iny bod� ve vy���ch dimenz�ch � � � � � � � � � � � � � � � � ��� Porovn�n� algoritm� pro nalezen� konvexn�ch obal� bod� � � � � � � � � � � � � � ���� Aplikace � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��

� Voron�ho diagramy �� � Konstrukce Voron�ho diagramu � � � � � � � � � � � � � � � � � � � � � � � � � � � � Voron�ho diagramy v �ece � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � Probl�my nejbli���ch soused� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � Minim�ln� pokr�vaj�c� strom � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � Dynamick� aktualizace Voron�ho diagramu � � � � � � � � � � � � � � � � � � � � � �� � Voron�ho diagramy vy���ch ��d� � � � � � � � � � � � � � � � � � � � � � � � � � � � �� � Voron�ho diagramy ve vy���ch dimenz�ch � � � � � � � � � � � � � � � � � � � � � � �� � D�ry a pokryt� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� Triangulace a vyhled�v�n� v rovinnch rozdlen�ch ���� Triangulace � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � Vyhled�v�n� v rovinn�ch rozd�len�ch � � � � � � � � � � � � � � � � � � � � � � � � ��

� � Metoda p�s� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��� Metoda cest � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � Metoda postupn�ho zjem�ov�n� � � � � � � � � � � � � � � � � � � � � � � � ��

� Pr�niky �� Prot�n�n� �se�ek � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �� Pr�nik polorovin � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��� Pr�nik konvexn�ch mnoho�heln�k� � � � � � � � � � � � � � � � � � � � � � � � � � �� J�dro jednoduch�ho mnoho�heln�ka � � � � � � � � � � � � � � � � � � � � � � � � � ��� Pr�nik poloprostor� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

Vyhled�v�n� dle rozsahu ���� Multidimenzion�ln� bin�rn� strom � � � � � � � � � � � � � � � � � � � � � � � � � � �� Metoda p��m�ho p��stupu � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ���� Rozsahov� strom � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��

ii OBSAH

� �lohy o obd�ln�c�ch ���� M�ra sjednocen� �se�ek � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��� M�ra sjednocen� obd�ln�k� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ���� Obvod sjednocen� obd�ln�k� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � Uz�v�ry sjednocen� obd�ln�k� � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

Pozn�mka �vodemC�t�m povinost ��ci �vodem n�co o smyslu a c�li p�edn��ek� na jejich� z�klad� tyto u�ebn�

texty vznikly� a tak� o okolnostech jejich vznikuV r�mci zav�d�n� nov�ho cyklu p�edn��ek bl�zk�ch aplikac�m� ale s matematickou n�pln��

pro studenty vy���ch ro�n�k� odborn� informatiky a odborn� matematiky� jsem p�ijal �kol p�i�pravit p�edn��ky z oboru� kter�mu se anglicky ��k� �computational geometry� N�kte�� kolegov�to �skoro �kodolib�� komentovali� �e z dostupn�ch geometr� jsem naj�ast�ji zap�nal po��ta��proto pr� j� Hned jsem zjistil� �e se jedn� o obor v bou�liv�m rozvoji� se stovkami ned�vn�ch�asopiseck�ch publikac�� ale s velice m�lo monogra�ck�mi texty Shrom��dil jsem tedy alespo�to� co bylo dostupn�� vybral jsem n�kolik t�mat a sna�il se uv�st z�jemce do t�to oblasti Roz�hodl jsem se� �e t�maticky p�edn��ku rozd�l�m na dv� poloviny V prvn�m semestru se zab�v�mline�rn� de�novan�mi objekty� ve druh�m pak obecn�mi algebraicky zadan�mi �tvary V oboup��padech mi jde o p�edveden� n�kolika z�kladn�ch princip� v�stavby algoritm� a p�edveden�jejich mo�n�ch aplikac�Tento text pokr�v� p�edn��ky z prvn� ��sti Mus�m ��ci� �e v roce jeho vzniku jsem m�l

radost z dobr� odezvy u poslucha�� a zejm�na si moc cen�m pr�ce pana Josefa Pojsla� kter��prakticky bez m�ho dal��ho p�isp�n�� cel� u�ebn� texty na z�klad� p�edn��ek sepsal� opat�ilobr�zky a typogra�cky dovedl do stavu� kter� nyn� m�te p�ed sebouZa obsahovou str�nku ov�em mus�m ru�it s�m P�edn��ka se jist� ��ste�n� p�ekr�v� s p�ed�

n��kou z gra�ky� zejm�na � kapitolu je t�eba br�t jako jakousi rozcvi�ku V dal��ch �ty�echkapitol�ch se sna��m systematicky probrat �adu z�kladn�ch �loh a z�rove� z�kladn�ch princi�p� tvorby algoritm� Jak�koli koment��e� dotazy� v�hrady apod pos�lejte pros�m na adresuslovakmath�muni�cz

Brno ����� Jan Slov�k

O rok pozd�ji nem�m moc co dodat� snad jen� �e v obou polovin�ch p�edn��ky st�le v��ce vyu��v�m slu�eb programov�ho syst�mu MAPLE V Douf�m� �e to nen� jen m�j dojem��e se jedn� o syst�m u�ite�n�� a v���m� �e sezn�men� s n�m je samo o sob� p��nosem Z��po�tov� projekty� p�ev��n� vypracovan� pr�v� na z�klad� tohoto syst�mu� lze naj�t v m�madres��i �VYUKA�Maple�galg na stroji hunter� p�ipoj�m do n�j i leto�n�V textech jsem v podstat� jen opravil n�kter� z pravopisn�ch chyb� p�eklep�� apod D�kuji

v�em� kter� mne na spoustu takov�ch nedostatk� upozorniliBrno ����� Jan Slov�k

� Konvexn� mnoho�heln�ky

Objekty� kter� budeme popisovat �a nejen v t�to kapitole�� se v�dy nach�zej� v Euklidovsk�mprostoru p��slu�n� dimenze d� kter� zna��me Ed Bude�li v textu uveden prostor Rd� budemes n�m n�kdy implicitn� zach�zet jako s jeho euklidovsk�m roz���en�mBez snahy o exaktn� de�nice zavedeme nyn� pojmy� u kter�ch by mohl nejednozna�n� v�klad

v�st ke zmaten�

��� De�nice�

Konvexn� mno�ina� Mno�ina D v prostoru Ed je konvexn�� pokud pro ka�d� jej� dva elementyq�� q� je cel� �se�ka q�q� obsa�ena v mno�in� D

Konvexn� obal� Konvexn� obal mno�iny S je hranice nejmen�� �ve smyslu mno�inov� inkluze�konvexn� mno�iny obsahuj�c� celou mno�inu S�

Mnoho�heln�k� V E� je mnoho�heln�k de�nov�n jako kone�n� mno�ina �se�ek� jejich� koncov�body jsou sd�leny v�dy pr�v� dv�mi z nich� p�i�em� ��dn� vlastn� podmno�ina t�chto�se�ek nen� mnoho�heln�k �tedy nem� tu vlastnost� �e by koncov� body v�ech taktovybran�ch �se�ek byly sd�leny pr�v� dv�ma �se�kami z t�to podmno�iny� Takov� de�nicen�m zaru��� �e budeme pracovat s cyklick�mi �et�zci na sebe navazuj�c�ch �se�ek

Jednoduch� mnoho�heln�k� je takov�� ve kter�m se ��dn� dv� nesoused�c� hrany neprot�naj�Jednoduch� mnoho�heln�ky d�l� rovinu na dv� ��sti� z nich� jedna je ohrani�en� �vnit�ek�a druh� neohrani�en� �vn�j�ek mnoho�heln�ka�

Konvexn� mnoho�heln�k� je takov� jednoduch� mnoho�heln�k� jeho� vnit�ek je konvexn� mno��ina

Jdro mnoho�heln�ka� je mno�ina bod� k z vnit�ku jednoduch�ho mnoho�heln�ka takov�ch� �epro ka�d� bod p mnoho�heln�ka je cel� �se�ka kp uvnit� mnoho�heln�ka

Analogicky de�nujeme pojmy mnohost�n� jednoduch� mnohost�n� konvexn� mnohost�n a jdromnohost�nuV t�to kapitole se budeme zab�vat konvexn�mi �tvary Nejprve p�edstav�me konvexn� mno�

ho�heln�ky a jednu jejich reprezentaci� s n�� se nau��me prov�d�t z�kladn� operace P�ejdemek probl�mu nalezen� konvexn�ho obalu mno�iny bod�� a nakonec uvedeme n�kolik aplikac� to�hoto probl�mu

��� Pr�niky konvexn�ch mnoho�heln�k�

Mnoho�heln�k P s n body budeme n�kdy zna�it P nZ�kladn� operace a probl�my nad konvexn�mi mnoho�heln�ky jsou tyto �v z�vorce je v�dy

uveden �as� kter�ho dos�hneme�

� Pro konvexn� mnoho�heln�k P n rozhodn�te� zda dan� bod le�� uvnit� �i vn� P n �lze v �aseO�log n��

Pro danou p��mku ��se�ku� p najd�te p � P n �lze v �ase O�log n��

� Pro P n a Qm zjist�te� zda P n �Qm � �lze v �ase O�log�n!m���

Pro P n a Qm najd�te P n �Qm �lze v �ase O�n !m��

�Ne ka�d� syst�m mno�in obsahuje nejmen�� prvek� My v�ak m�me existenci takov� nejmen�� mno�inyzaru�enu� Oven� ponech�v�me �ten�i�

� KONVEXN� MNOHO�HELN�KY

eee

eeee

QQQQQsBBBBBN�������������Z

ZZ

ZZZ�

����������

P�

P�

����

������� �

� � � � �� �� ��

Obr �" Vyv��en� hierarchick� reprezentace konvexn�ho sedmi�heln�ka

#asov� slo�itosti� kter�ch dos�hneme� budou siln� ovlivn�ny datovou strukturou� kter� n�mbude slou�it pro reprezentaci mnoho�heln�k�

��� De�nice� Posloupnost P�� � � � � Pk mnoho�heln�k� se naz�v� vyv�en hierarchick reprezentace �V HR� konvexn�ho mnoho�heln�ka P � pokud

� P� m� nejv��e vrcholy

� Pk P

� Pi�� se obdr�� z Pi vynech�n�m vhodn�ch vrchol�� p�itom z ka�d�ch t�� po sob� jdouc�chje alespo� jeden vynech�n a ze �ty� po sob� jdouc�ch alespo� jeden z�stane zachov�n

V HR lze uchov�vat jako vyv��en� � �� strom �viz obr�zek �� Po��t�me�li �rovn� stromu odnuly� lze i�tou �rove� stromu V HR ch�pat jako posloupnost vrchol�� kter� dohromady d�vaj�mnoho�heln�k Pi V ko�eni stromu na obr�zku � je mnoho�heln�k P� ������� $se�ka ��� sev lev�m podstromu rozv�j� na �et�zec �� ��� �se�ka ��� v prost�edn�m podstromu na ����� a�se�ka ��� v prav�m podstromu na �������Ka�d� uzel stromu V HR m��e m�t dva nebo t�i n�sledn�ky� krom� uzl� na posledn� �rovni�

kter� nemaj� ��dn� n�sledn�ky� a ko�ene� kter� m� dva� t�i nebo �ty�i n�sledn�kyV HR je line�rn� strukturou v��i po�tu vrchol� Ov��en� je ponech�no na �ten��iPro odvozov�n� �asov�ch slo�itost� jednotliv�ch algoritm� n�s bude zaj�mat� jak�ch �as�

lze dos�hnout p�i proch�zen� V HR

��� Lemma� V�echny obvykl� operace v ��� stromu lze prov�d�t v ase O�log n�� v��katakov�ho stromu je O�log n�� VHR mnoho�heln�ka P lze z�skat v ase O�n��

D kaz� Obvyklou operac� zde rozum�me nap� Insert a Delete� p�i nich� projdeme strom odko�ene k n�jak�mu listu Takov� cesta m� d�lku rovnou v��ce stromu � �� strom m� nej�v��e O�log� n�� nejm�n� O�log� n� �rovn�� celkem tedy O�log n� Udr�en� vyv��en�ho stromuvy�aduje nejv��e jeden dal�� pr�chod zp�t ke ko�eni� co� nenaru�� logaritmickou slo�itostKonstrukci stromu V HR m��eme prov�d�t tak� �e jdeme od posledn� �rovn� �cel� mno�

ho�heln�k� sm�rem nahoru Mus�me v�dy proj�t v�echny uzly dan� �rovn� a vytv��et uzly na

��� Pr�niky konvexn�ch mnoho�heln�k� �

ni��� �rovni V�sledn� �as bude odpov�dat celkov�mu po�tu uzl� ve stromu� a ten je line�rn��

Dosp�li jsme do stadia� kdy se m��eme pustit do �e�en� jednotliv�ch probl�m���� Vta� Nech� P�� � � � � Pn je V HR konvexn�ho mnoho�heln�ka P n� Probl�m� zda bod x � P n�lze rozhodnout v ase O�log n��D kaz� Anal�zou n�sleduj�c�ho algoritmu

Algoritmus ��� Rozhodnut�� zda bod le�� uvnit� nebo vn� mnoho�heln�ka

Vstup� bod x a V HR mnoho�heln�ka PV�stup� zji�t�n�� zda x � P

� p t��i�t� P�% i " �

while Pi � P do

� zjist�me� ve kter� v�se�i z p na vrcholy Pi le�� x i " i! � a v dal�� iteraci rozv�j�me nalezenou v�se�

� ur��me� zda je x uvnit� v�sledn� v�se�e

Algoritmus nejprve v cyklu nalezne v�se� danou polop��mkami spu�t�n�mi z bodu p na v�echnyvrcholy P � ve kter� le�� bod x Pak se ov���� zda je bod x vn� nebo uvnit� troj�heln�ka� kter�vznikne ohrani�en�m t�to v�se�e hranou odpov�daj�c� t�to v�se�iBod p t��i�t� P� najdeme v konstantn�m �ase Tento bod je vnit�n�m bodem v�ech Pi

Bodem p vedeme polop��mky do v�ech vrchol� P� V konstantn�m �ase zjist�me� ve kter� v�se�ile�� x V uzlu n�sleduj�c� �rovn�� kter� je rozvinut�m hrany dan� touto v�se��� budeme d�lehledat� ve kter� v�se�i P� le�� bod x A� se t�mto zp�sobem dostaneme k Pk� zn�me v�se�Pk P � ve kter� le�� bod x Pak zjist�me v konstantn�m �ase� zda bod v nalezen� v�se�i le��uvnit� �i vn� mnoho�heln�kaV�echny operace v jednom uzlu lze prov�st v �ase O��� #asov� slo�itost je tedy �m�rn�

hloubce stromu� co� je O�log n� �

�� Vta� Nech� P�� � � � � Pk je V HR�P n�� p je p��mka� Pr�nik p �P lze naj�t v ase O�log n��

D kaz� Budeme op�t proch�zet V HR od ko�ene a� k listu Jestli�e p�i pr�chodu naraz�me napr�nik Pi s p��mkou p� zjist�me hrany e��i�� e��i� z Pi� kter� p��mka p prot�n� D�le p�ejdemek e��i ! ��� e��i ! �� z Pi��� kter� p prot�n� To zabere konstantn� �as� proto�e e��i ! �� jeprvkem �rozvinut�� hrany e��i� p�i p�echodu od Pi k Pi�� Jakmile tedy v pr�b�hu prov�d�n�algoritmu zjist�me� �e p m� s n�jak�m mnoho�heln�kem Pi nepr�zdn� pr�nik� najdeme taktonakonec pr�nik P k P s p��mkou p� co� je k��en� v�sledekNe� se v�ak k takov�mu Pi dostaneme� mus�me proj�t mnoho�heln�ky Pj � kter� p��mka p

neprot�n� Pokud tato situace trv� a� k P k P � z�sk�v�me informaci� �e p � P �V p��pad�� �e p � Pj �� rozv�j�me vrcholy �maxim�ln�� ve sm�ru kolm�m na p Jsou

to vrcholy� jejich� pr�m�ty na p��mku kolmou na p jsou nejbl��e p��mce p Takov� mohou b�tnejv��e dva� viz lemma�� Jestli�e p neprot�n� Pj � ale prot�n� Pj��� mus� p��mka p prot�nat Pj��v jednom z �et�zc�� kter� vzniknou rozvinut�m t�ch hran Pj� kter� inciduj� s maxim�ln�mi bodyve sm�ru kolm�m na p Toto si m��eme dovolit tvrdit d�ky konvexnosti v�ech mnoho�heln�k�Pi Obr�zek ilustruje situaci Bod ��� algoritmu � se odkazuje na tuto �vahuN�sleduj�c� lemma postihuje vztah mezi maxim�ln�mi body v pevn�m sm�ru po sob� jdou�

c�ch mnoho�heln�k� ve V HR

� KONVEXN� MNOHO�HELN�KY

��

��

����

��AAA HH

HHHH

HHHH

p

PjPj��

maxd�Pj�

maxd�Pj��� QQ

QQ

QQ

QQQkd

Obr " Vztah maxim�ln�ch bod� a pr�niku p��mky s mnoho�heln�kem

��� Lemma� Nech� d�Pi� je mno�ina vrchol� maxim�ln�ch ve sm�ru d� Pak jd�Pi�j � apokud v � d�Pi���� pak existuje w � d�Pi� tak� �e bu� v w nebo mezi v a w le�� nejv��e dvavrcholy v seznamu Pi���D kaz� Kdyby mezi body v a w byly t�i nebo v�ce vrchol�� nemohl by se ��dn� z nich vyskytovatv Pi� jinak by byl maxim�ln� m�sto w Potom ale tyto t�i vrcholy spolu s v tvo�� souvislou �adu�ty� vrchol�� kter� byly p�i p�echodu od Pi�� k Pi vynech�ny� co� odporuje de�nici V HR

Zn�me tedy zp�sob� jak v konstantn�m �ase p�ej�t od maxim�ln�ch vrchol� v dan�m sm�ruk maxim�ln�m vrchol�m v tomto sm�ru pro n�sleduj�c� mnoho�heln�k ve V HR V n�sleduj�c�malgoritmu se body d�Pi� v bod� �� naleznou v��e popsan�m zp�sobemP�ejdeme nyn� k samotn�mu algoritmu

Algoritmus ��� Nalezen� pr�niku p��mky s mnoho�heln�kem

Vstup� p��mka p a V HR mnoho�heln�ka PV�stup� p � P� i " �

najdeme d�P��

� if p � P� � then

�� repeat��� i " i! ��� najdeme d�Pi� s pomoc� d�Pi������ zjist�me s pomoc� d�Pi�� zda p � Pi �

� until p � Pi � � or Pi P

if p � Pi � then &' i k

� return �� else

�� while Pi � P do

��� najdeme e��i�� e��i�

��� Pr�niky konvexn�ch mnoho�heln�k� �

atd atd PRPL

Obr �" Prav� a lev� monot(nn� �et�zec mnoho�heln�ka

�� i " i! �� return �p � e��k�� � �p � e��k��

Algoritmus projde v�dy strom V HR a na ka�d� �rovni stromu �jeden pr�chod cyklem�provede konstantn� operaci v obou cyklech algoritmu� tedy v�sledn� �as je O�log n� �

��� D�sledek� Probl�m nalezen� P � s� kde s je �se ka� lze �e�it v ase O�log n��

D kaz� Aplikujeme algoritmus � na p��mku� na kter� �se�ka s le��� a pak v konstantn�m �asezjist�me pr�nik v�sledku algoritmu s �se�kou s �

��� Pozn�mka� Algoritmy �� a � jsou typick�mi p��klady metody vyhledvn� ve stromuOba postupuj� od ko�ene a na z�klad� jist�ho kriteria se na ka�d� �rovni stromu rozhoduj��kter� uzly budou �zaj�mav�� na p���t� �rovni Takto se dostanou a� k list�m� kde se d� ji�zjistit kone�n� v�sledek

N�sleduj�c� dv� �lohy zkoumaj� pr�nik dvou konvexn�ch mnoho�heln�k� Uvid�me� �e propouh� zji�t�n�� zda tento pr�nik je pr�zdn� �i ne� lze nal�zt p�i pou�it� V HR rychlej�� algoritmus�ne� pro nalezen� cel�ho pr�niku��� Vta� Nech� P� a� Pk je V HR mnoho�heln�ka Pm a Q� a� Ql je V HR mnoho�heln�kaQn� V ase O�log�m! n�� lze rozhodnout� zda Q � P � i nikoli�D kaz� Ozna�me PL a PR tzv lev� a prav� monot(nn� mnoho�heln�kov� �et�zec ��et�zce vznik�nou roztr�en�m cel�ho mnoho�heln�kov�ho �et�zce na dva pod�et�zce v bodech s maxim�ln� aminim�ln� y�ovou sou�adnic� � viz obr�zek �� Je z�ejm�� �e PL �PR P a QL �QR Q D�leplat�"

P �Q � � PL �QR � QL � PR ����

Bereme tedy v �vahu dv� dvojice monot(nn�ch �et�zc� Pop��eme nyn�� jak hledat pr�nikjedn� takov� dvojice� nap� PL a QR� druh� p��pad je symetrick�Na �et�zc�ch PL a QR budeme postupovat metodou p�len� intervalu �zde d�lic� �body�

interval� budou jednotliv� hrany �et�zc�� Na po��tku bereme v �vahu cel� �et�zce� v ka�d�mkroku se pak rozhodneme� zda n�s zaj�m� oblast nad nebo pod aktu�ln� hranou v obou �et�zc�chZ takov�ch dvou oblast� pak vybereme hrany uprost�ed �p�l�c� hrany�� a d�le postupujeme

� � KONVEXN� MNOHO�HELN�KY

������

EEEEEEEEE

������

AAA

������ A

AAAAA

������

����

����� �

����e eeee

ee

eee

ee

e

ee

e e

e ee

� �� � � �

QR

PL

QR

PL

QR PL

QR

PL

QR PL

e�d�c�

a� b�

AA��

�������

Obr " Diskuse vz�jemn�ch poloh aktu�ln�ch hran monot(nn�ch �et�zc�

stejn� Jestli�e dojdeme k ned�liteln�mu intervalu a na cest� jsme nenarazili na p��pad� kter�n�m zaru�uje existenci pr�niku PL a QR � viz obr a�� potom pr�nik neexistuje Tento postupn�m zaru�uje logaritmick� �asDiskusi vz�jemn�ch poloh aktu�ln�ch hran pop��eme za pomoci obr�zku Nastane�li p��pad

a�� pak �et�zce PL a QR maj� nepr�zdn� pr�nik V p��pad� b� n�s u PL bude d�le zaj�mat oblastnad aktu�ln� hranou V p��pad�� kdy aktu�ln� hrany jsou �z�dy k sob�� � p��pady c�� d�� e� naobr�zku� diskutujeme p��mky� na kter�ch le�� aktu�ln� hrany Proto�e tyto p��mky ohrani�uj�poloroviny� ve kter�ch le�� v�dy cel� odpov�daj�c� mnoho�heln�k �d�ky jejich konvexnosti�� m��enastat pr�nik pouze tam� kde se tyto p��mky prot�naj� V p��pad� c� n�s tedy budou d�le zaj�mathorn� oblasti pro oba �et�zce� v p��pad� d� spodn� oblasti� a v p��pad� e� u� pr�nik nem��eexistovat� proto�e p��mky jsou rovnob��n�Celkem v logaritmick�m �ase zjist�me� zda existuje pr�nik PL a QR� a tot�� se d� zcela

analogicky zjistit pro PR a QL D�ky vztahu � tak zn�me v logaritmick�m �ase odpov�) naot�zku� zda existuje pr�nik mnoho�heln�k� P a Q �

���� Pozn�mka� Algoritmus popsan� v p�edchoz�m d�kaze pou��v� metody tzv binrn�lokalizace #esk� term�n p�len� intervalu je v podstat� ekvivalentem Tyto algoritmy se sna��lokalizovat dan� jev tak� �e rozp�l� interval� ve kter�m prob�h� hled�n� jevu� a podle n�jak�hokriteria mohou jeden ze dvou takto vznikl�ch interval� vylou�it Hled�n� pak rekurzivn� prob�h�na tomto men��m intervalu

��� Konvexn� obal bod� v rovin� �

��

��

��

����

��

��

��QQQQQ�

����

e e e ee

eee

����

����LLLLLLLL

��������LLLLLLLLe e e

eeee

e

a� b�

Obr �" Pr�niky d�lky O�m! n� a� troj� a p�ti�heln�ka b� dvou �ty��heln�k�

Mus� v�ak existovat n�jak� �zar��ka�� kter� na jist� �rovni rekurze algoritmus zastav� V na��em p��pad� je to ned�litelnost intervalu Hled�me�li touto metodou iracion�ln� ko�en polynomu�mus�me m�t jako zar��ku jistou �p�esnost�� nebo�li velikost intervalu� kter� u� nebudeme d�lep�lit� pouze jeho st�ed prohl�s�me za ko�en

���� Vta� Nech� Pm� Qn jsou konvexn� mnoho�heln�ky� Pak P �Q lze zjistit v ase O�m!n��

D kaz� Nejd��ve z�sk�me bod p uvnit� P �nap� t��i�t� libovoln�ch t�� vrchol� P � Z bod� P i Qvytvo��me posloupnosti bod� p�� � � � � pm a q�� � � � � qn takov�� �e v�dy sousedn� body jsou spojenyhranou Ozna��me pro i � � � � n v�se�e ohrani�en� polop��mkami ppi a ppi�� �pn�� p�� jakosi V line�rn�m �ase se d� zjistit� ve kter� v�se�i si se nach�z� bod q� V �ase O�k ! �� ur��mepr�nik �se�ky L�q�� q�� s P � p��padn� jej� polohu �uvnit� � vn�� Zde k je po�et polop��mekppi pro*at�ch �se�kou L�q�� q�� Z�ejm� je k � m Takto pokra�ujeme pro v�echny body qj Popr�chodu z�sk�me bu) pr�niky hran� nebo informaci� zda Q � P nebo P � Q nebo P �Q �Proto�e ka�d� hrani�n� polop��mka oblasti si prot�n� nejv��e dv� hrany� pot�ebujeme nejv��e�as O� m� pro nalezen� pr�se��k� Z�rove� v�ak mus�me proj�t v�echny body Qn� proto v�sledn��as je O�m ! n� �

Lep��ho �asu ne�O�m!n� nelze obecn� dos�hnout� proto�e v�sledek m� v nejhor��m p��pad�pr�v� tuto d�lku Pr�nikem troj� a p�ti�heln�ka na obr�zku �a� je toti� pr�v� osm bod� Dva�tverce na obr�zku �b� maj� rovn�� pr�nik d�lky osm

���� Pozn�mka� Postup uveden� v d�kazu v�ty ��� nach�z� pr�se��ky hran mnoho�heln�k�v takov�m po�ad�� kter� produkuje mnoho�heln�k ohrani�uj�c� pr�nik vnit�k� mnoho�heln�k� Pa Q Chceme�li tedy naj�t pr�nik vnit�k� P a Q� nemus�me body d�le t��dit Pro ov��en� si sta��uv�domit� �e uveden� postup proch�z� hrany Q postupn� podle sousednosti $seky hran z Q�kter� ohrani�uj� pr�nik� jdou za sebou ve stejn�m po�ad�� pouze se mezi n� p��padn� vkl�daj��seky hran z P K pochopen� zde op�t pom��e obr�zek �

��� Konvexn� obal bod� v rovin�

Nalezen� konvexn�ho obalu kone�n� mno�iny bod� v rovin� ch�peme jako zad�n� hrani�n�chbod� konvexn�ho obalu se�azen�ch v jist�m sm�ru �nap� ve sm�ru hodinov�ch ru�i�ek�Uvedeme postupn� n�kolik algoritm�� u kter�ch ur��me nejprve asymptoticky nejhor�� �asy

V ��sti � tyto algoritmy porovn�me z hlediska �asu o�ek�van�ho

� � KONVEXN� MNOHO�HELN�KY

���������������������� J

JJJJ

QQ

QQQ

BBBBB��������aaaaaaaa

JJJJJP

��

��

��

����

������

BBBBBBBBN

horn+, konvexn+, obal

Obr �" Horn� konvexn� obal

���� Pozn�mka� Konvexn� obal mno�iny S budeme zna�it BCH�S� �z angl BoundaryConvex Hull� Vnit�ek konvexn�ho obalu budeme zna�it CH�S� �Convex Hull�

���� Vta� Nech� S � R� je kone n� mno�ina bod� v rovin�� P n jednoduch� mnoho�heln�k�jeho� vrcholy jsou pr�v� v�echny body z S� Konvexn� obal BCH�S� lze spo �tat v line�rn�m ase O�jSj� ��Preparata����� str� ��������D kaz� V line�rn�m �ase najdeme vrcholy pl� pr � S s minim�ln� a maxim�ln� x�ovou sou�adnic�$se�ka L�pr� pl� le�� v konvexn�m obalu D�ky jednoduchosti P lze �lohu �e�it zvl��* pro tzvhorn� a doln� konvexn� obal �viz obr � a n�sleduj�c� odstavec�Konvexn� obal je vlastn� konvexn�mnoho�heln�k Body pr a pl budou zcela jist� jeho vrcholy

Tyto dva vrcholy roztrhnou konvexn� obal na dva �et�zce �se�ek� vedouc� z pr do pl� ka�d� v jin�polorovin� podle p��mky prpl -et�zec nad touto p��mkou nazveme horn� konvexn� obal � podn� doln� konvexn� obal bod� mno�iny S Probl�m nalezen� doln�ho konvexn�ho obalu je du�ln�k nalezen� horn�ho konvexn�ho obalu a n��e uveden� algoritmus se d� snadno upravit tak� abypo��tal doln� konvexn� obalOzna�en� �napravo� resp �nalevo� od pq� kter� se v algoritmu hojn� vyskytuj�� znamenaj�

lokalizaci v prav� resp lev� polorovin� dan� p��mkou pq Orientace je takov�� jako bychom se�d�vali� od bodu p sm�rem k bodu q Prakticky se tento test pro bod x provede v�po�tem de�terminantu matice ze sloupc� pq� px T�m z�sk�me orientovan� obsah p��slu�n�ho rovnob��n�ka�a podle znam�nka !&� je bod nalevo&napravo

Algoritmus ��� Nalezen� horn�ho konvexn�ho obalu jednoduch�ho mnoho�heln�ka

Vstup� jednoduch�mnoho�heln�k P n zadan� jako seznam bod� p�� � � � � pn uspo��dan� ve sm�ruhodinov�ch ru�i�ek

V�stup� hrani�n� body horn�ho konvexn�ho obalu v�ech vrchol� mnoho�heln�ka P n ve sm�ruhodinov�ch ru�i�ek

V algoritmu vystupuje z�sobn�k Q " q�� � � � � qt� kde t je v�dy vrchol tohoto z�sobn�kuZ�sobn�k m� dno q� p��stupn� ke �ten�

� najdi body pr a pl

��� Konvexn� obal bod� v rovin� �

q� prq� pl

a�

���

JJJJJ

eq�q�

qt ps

b�

���

JJJJJ q�

qt

q� ���

q�

qt

q�

eeepseps���

c�

e e

Obr �" Konstrukce horn�ho konvexn�ho obalu jednoduch�ho mnoho�heln�ka

inicializuj z�sobn�k" q� " pr % q� " pl

� s " �

while ps je vrchol nalevo od q�q� do &' p�esko��me body pod p��mkou prpl � viz obr �a�

� s " s! �

� p�idej ps na vrchol z�sobn�ku

� while s � n do

�� repeat &' vyhled�me body� kter� jsou mimomnoho�heln�k dan� body v z�sobn�kuQ� viz obr �b�

��� s " s! �

� until ps je napravo od q�qt or ps je nalevo od qt��qt or s n

�� while ps je nalevo od qt��qt and s � n do &' p�id�me bod ps� ale tak� aby nov�hrana neporu�ila konvexnost � viz obr �c�

��� odstra� qt z vrcholu z�sobn�ku

� p�idej ps na vrchol z�sobn�ku

q�� � � � � qt je horn� konvexn� obal

Diskus� poloh bodu ps v��i bod�m z�sobn�ku Q �obr�zek �� si ov���me n�sleduj�c� invarianty�kter� plat� v�dy na za��tku cyklu �"

� q� pr % q� pl % t � % qt ps

� s � n

� q�� � � � � qt� q� je konvexn� mnoho�heln�k

� horn� konvexn� obal S je posloupnost vybran� z q�� � � � � qt� ps��� � � � � pn

�� � KONVEXN� MNOHO�HELN�KY

Prvn� dva body jsou z�ejm� Zachov�n� konvexnosti ve t�et�m bod� se uk��e snadno z obr�zku ��kdy� si uv�dom�me� v jak�m po�ad� nast�v� p�id�v�n� a ub�r�n� bod� na vrcholu z�sobn�kuK ov��en� �tvrt�ho bodu vede pon�kud slo�it�j�� �vahaV situac�ch a� a b� na obr�zku � nenastane ��dn� komplikace Nastane�li situace c� � bod

ps nalevo od qt��qt� m��e b�t bod ps nalevo �jako je tomu na obr�zku� nebo napravo od q�qtV druh�m p��pad� je jasn�� �e bod qt a ani ��dn� jin� bod vylou�en� ze z�sobn�ku v cyklu ��nemohou b�t u� vrcholy konvexn�ho obalu Pro prvn� p��pad si mus�me uv�domit� �e z bodu psvede lomen� ��ra jako sou��st mnoho�heln�ka P n do bodu q� Ta mus� prot�nat p��mku qt��qt�proto�e bod ps je od n� vlevo a bod q� vpravo �jinak by qt nebyl p�id�n do z�sobn�ku za qt���Proto�e je mnoho�heln�k P n jednoduch� a jeho vrcholy jsou zad�ny podle sm�ru hodinov�chru�i�ek� bude tato lomen� ��ra prot�nat polop��mku qt��qt a� za bodem qt Bod qt se tak octneuvnit� konvexn�ho obalu� a nem��e u� b�t na jeho hranici To stejn� plat� i pro ostatn� bodyodstran�n� ze z�sobn�ku v cyklu ��K odvozen� �asu b�hu algoritmu vede �vaha zkoumaj�c� zach�zen� s jednotliv�mi vrcholy

mnoho�heln�ka Po nalezen� bod� pr a pl� kter� je line�rn� z�le�itost�� je ka�d� vrchol P n kon�frontov�n se z�sobn�kem Q pr�v� jednou� nepo��t�me�li cyklus �� Tento cyklus bude v�ak m�tmaxim�ln� n iterac� v pr�b�hu cel�ho algoritmu� proto�e je zde odstra�ov�n vrchol z�sobn�ku�a to se ka�d�mu bodu z P n m��e st�t nejv�ce jednou Proto�e p��slu�nost bodu do jedn� z polo�rovin ur�en�ch danou p��mkou lze testovat v konstantn�m �ase� algoritmus �� pracuje line�rn�

��� Vta� Nech� S � R� je kone n� mno�ina o n bodech� Pak BCH�S� lze spo �tat v aseO�n log n��

D kaz� Probl�m �e�� n�sleduj�c� algoritmus

Algoritmus ���

Vstup� kone�n� mno�ina S bod� v rovin�V�stup� vrcholy konvexn�ho obalu S� set��d�n� ve sm�ru hodinov�ch ru�i�ek

Lexikogra�cky uspo��d�me S� tj p � q jestli�e x�p� � x�q� nebo x�p� x�q� a y�p� � y�q�Nech* p�� � � � � pn je v�sledn� posloupnost Na ni aplikujeme algoritmus ��

I kdy� takto zadan� posloupnost bod� p�� � � � � pn nen� mnoho�heln�kem� lze ji pou��t jako vstupv��e uveden�ho algoritmu� proto�e ten vy�aduje pouze to� aby se ��dn� dv� nesousedn� hranypi��pi pro i �� � � � � n neprot�naly a aby z ka�d�ho bodu pi pro i � n existovala lomen� ��ratvo�en� posloupnost� hran vybranou z P n do bodu q� V na�em p��pad� q� pn� a tedy ob�podm�nky jsou spln�nyV�sledn� �as je O�n log n� !O�n� �

Vstup pro algoritmus �� se d� z�skat z obecn� mno�iny bod� je�t� jin�m zp�sobem Cel�algoritmus je nazv�n Graham�s Scan

Algoritmus �� Grahams Scan

Vstup� kone�n� mno�ina S bod� v rovin�V�stup� vrcholy konvexn�ho obalu S� set��d�n� ve sm�ru hodinov�ch ru�i�ek

Vybereme libovoln� vnit�n� bod konvexn�ho obalu �nemus� b�t prvkem S� a spoj�me ho sev�emi body S Set��d�me body podle velikosti �hl� jejich spojnic s vybran�m bodem a takovouposloupnost po�leme na vstup algoritmu ��

��� Konvexn� obal bod� v rovin� ��

Posloupnost bod� set��d�n�ch podle jejich �hl� u� jist� d�v� jednoduch�mnoho�heln�k a je tedypou�iteln� pro algoritmus �� Graham.s Scan pracuje d�ky t��d�n� bod� op�t v �ase O�n log n�

���� Pozn�mka� N�sleduj�c� t�i algoritmy pracuj� tak� �e po��taj� konvexn� obal n�jak�chpodmno�in vstupn� mno�iny� a pak s pomoc� t�chto ��ste�n�ch v�sledk� produkuj� celkov�konvexn� obal Prvn� algoritmus se li�� od zbyl�ch dvou pouze v tom� jak�m zp�sobem d�l�vstupn� mno�inuTato metoda se naz�v� rozd�l a panuj a je pro ni charakteristick� �i kdy� ne nutn�� re�

kurzivn� vol�n� procedur Typick� algoritmus rozd�l a panuj rozd�l� vstupn� soubor na n�kolik��st� �mohou b�t bu) srovnateln� velk� nebo jsou z�m�rn� n�kter� v�t�� a jin� men���� a pro n�zavol� rekurzivn� s�m sebe ���st rozd�l� Jakmile jsou zn�my v�sledky t�chto vol�n�� aplikujese na n� n�jak� efektivn� metoda� kter� produkuje celkov� v�sledek ���st panuj �Metoda rozd�l a panuj se �asto pou��v� v praxi p�i anal�ze probl�m� �m��e to b�t anal�za

hospoda�en� podniku nebo p�epis algoritmu do procedur�ln�ho programovac�ho jazyka� Cel��loha se d�l� na podprobl�my� a� vznikne jist� hierarchie ��ste�n�ch probl�m� Jejich spojov�n�do v�sledk� je pak jasn�j�� a p�ehledn�j��

Po rozd�len� vstupn� mno�iny a spo��t�n� konvexn�ch obal� takto rozd�len�ch ��st� budemem�t za �kol spo��tat konvexn� obal dvou konvexn�ch obal� �tedy konvexn�ch mnoho�heln�k���nebo bodu a mnoho�heln�ka N�sleduj�c� lemma �e�� oba probl�my� v p��pad� dvou mnoho��heln�k� v�ak pouze pro p��pad� kdy jsou jejich vnit�ky disjunktn� Tuto vlastnost v na�emalgoritmu zaru��me

���� Lemma� BCH�P �Q� disjunktn�ch konvexn�ch mnoho�heln�k� Pm a Qn lze naj�t v aseO�m! n��

D kaz� V �ase O�m� najdeme hranu v P nebo Q tak� �e P a Q padnou do r�zn�ch polorovinT�m umo�n�me nalezen� dvou nejbli���ch bod� z p� � P a q� � QV prvn�m kroku postupujeme po P proti sm�ru hodinov�ch ru�i�ek� dokud se zmen�uje

�hel s vybranou hranou v Q Ozna�me z�skan� bod p� Tak z�sk�me te�nu z q� na P V dal��mkroku zam�n�me P a Q� postupujeme po Q ve sm�ru hodinov�ch ru�i�ek� a z�sk�me te�nu z p�na Q Po kone�n�m po�tu krok� dostaneme jednu z te�en P a Q � viz obr�zek � Obr�cen�morientac� z�sk�me druhou te�nu P�i cel�m pr�b�hu algoritmu proch�z�me ka�d�m vrcholemnejv��e jednou �

���� Lemma� V HR�BCH�P �Q�� dvou disjunktn�ch konvexn�ch mnoho�heln�k� Pm a Qn�zn�me�li jejich V HR a te ny� lze spo �st v ase O�log�m! n���

D kaz� Mus�me vylou�it �et�zce mezi body dotyku M��eme si to p�edstavit tak� �e z�sk�mev ka�d�m ze strom� V HR pro oba mnoho�heln�ky dva ukazatele na listy� z nich� jeden znamen�za��tek a druh� konec �et�zce� kter� m� b�t odstran�n ve v�sledn�m mnoho�heln�ku �bodydotyku te�en� Odstran�me nyn� tyto listy v obou stromech� a ve vy���ch �rovn�ch stromu d�lety uzly� kter� vedou pouze na listy� je� maj� b�t odstran�ny Z�sk�me tak dva �hybridn�� stromy�viz obr �a�� kter� nemus� spl�ovat podm�nky V HR Z nich mus�me stvo�it jedin� V HR stromKonstrukci za�neme na nejni��� �rovni Jeden �et�zec list� vlo��me mezi �et�zec zbyl�ch

list� ve druh�m strom�� a to na m�sto� odkud byly p�edt�m listy odstran�ny T�m na t�to�rovni kon��meNa ka�d� vy��� �rovni je t�eba zajistit� aby platily podm�nky V HR Jde p�edev��m o zaji�t��

n� toho� aby ka�d� uzel m�l dva a� �ty�i potomky Vezmeme v �vahu se�azen� uzly t�to �rovn�

� � KONVEXN� MNOHO�HELN�KY

��

����

LLL

�������

�e

eee

ep� q�

p�

Obr �" Te�ny dvou konvexn�ch disjunktn�ch mnoho�heln�k�

obou hybridn�ch strom� Budou n�s nyn� zaj�mat pouze krajn� uzly obou t�chto posloupnost�N�kdy dva z t�chto uzl� splynou v jeden� jindy je t�eba uzel rozd�lit na dva �viz obr �b�c�Vnit�n� uzly t�chto posloupnost� v�ak mohou b�t zachov�ny Tato vlastnost� zjednodu�en� vy�sv�tliteln� t�m� �e jsme vzali v�dy souvisl� �et�zec list� a jejich p�edch�dc� v p�vodn�m V HR�n�m zaru�� konstantn� �as v�po�tu na ka�d� �rovni konstrukce nov�ho stromu Nov� zkonstruo�van� strom u� m� v�echny vlastnosti V HR� a po�et jeho vrchol� je maxim�ln�m!n Znamen�to tedy� �e konstrukce V HR zabere O�log�m! n�� �asu �

���� Vta� Nech� S � R� je mno�ina o n bodech� p � R� je bod� Je�li d�na V HR�BCH�S���pak

V HR�BCH�S � fpg��spo teme v ase O�log n��

D kaz� Podle v�ty � zjist�me v �ase O�log n�� zda p � BCH�S� Pokud ano� je v�sledkemBCH�S� Pokud ne� najdeme v �ase O�log n� body dotyku te�en spu�t�n�ch z bodu p naBCH�S�"Body dotyku te�en z p na P� lze z�skat v konstantn�m �ase Jdeme�li od Pi k Pi��� mus� le�et

nov� bod dotyku v rozvinut� n�kter� ze dvou hran� kter� soused� s p�vodn�m bodem dotyku�pokud j�m nez�stane on s�m Ka�d� krok je konstantn�� proto celkov� m�me �as O�log n�Tyto body dotyku jsou vrcholy mnoho�heln�ka BCH�S� Aktualizace V HR pak prob�hne

v �ase O�log n� podle lemmatu ���� dosad�me�li za mnoho�heln�k Qn bod p �

M��eme p�istoupit k prvn�mu algoritmu rozd�l a panuj Ten ze vstupn� mno�iny vyberejeden bod� spo��t� konvexn� obal zbyl�ch n � bod�� a pak tento jeden bod p�id� Rekurze sezde d� snadno nahradit iterativn�m postupem V�hodou tohoto p��stupu je jeho dynami�nost� po zpracov�n� libovoln� podmno�iny element� ze vstupu zn�me pro n� v�sledek

Algoritmus ���Vstup� kone�n� mno�ina S bod� v rovin�V�stup� vrcholy konvexn�ho obalu S� set��d�n� ve sm�ru hodinov�ch ru�i�ekAlgoritmus pro tvorbu konvexn�ho obalu lze z�skat jako d�sledek v�ty ��� tak� �e body mno�inyS bereme ze vstupu po jednom a konvexn� obal konstruujeme iterativn� p�id�v�n�m t�chto bod�V�sledn� �as je op�t O�n log n��

��� Konvexn� obal bod� v rovin� ��

e u u u e e e u u u e e

JJJJJ

JJJJJ

BBBBB�����B

BBBB�����

e e u u u u e e e u u u u eJJJJJ

BBBBB�����B

BBBB�����

�Q

QQ

QQ

QQ

QQ��

��

���

��������

���JJ�

��JJ

e u u u u e e e e eee

eeue

e�

��

��

��� �����ZZ

ZZZZ

JJJJJ

B

BBBB�����B

BBBB�����

���������

����Z

ZZZZZ

JJJJJ

� �

a�

b�

c�

Obr �" Postup p�i spojov�n� V HR disjunktn�ch mnoho�heln�k�% a� hybridn� strom� b� spojen�uzl�� c� rozd�len� uzlu

Druh� algoritmus rozd�luje vstupn� mno�inu na dv� stejn� velk� podmno�iny� pro kter�rekurzivn� zavol� s�m sebe V�sledky pak spoj� v konvexn� obal pomoc� lemmatu ��� Aby totolemma bylo pou�iteln�� mus�me zaru�it disjunktnost ��ste�n�ch v�sledk� To provedeme tak� �eob� podmno�iny budou v�dy cel� le�et v r�zn�ch polorovin�ch podle n�jak� p��mky rovnob��n�s osou y Za t�mto ��elem body na za��tku algoritmu t��d�me podle x�ov� sou�adnice

Algoritmus ��� Algoritmus pro z�sk�n� konvexn�ho obalu metodou Rozd�l a panuj

Vstup� kone�n� mno�ina S bod� v rovin�V�stup� vrcholy konvexn�ho obalu S� set��d�n� ve sm�ru hodinov�ch ru�i�ek

� Uspo��d�me body podle x�ov�ch sou�adnic �pro jednoduchost p�edpokl�dejme� �e jsounavz�jem r�zn��

Rozd�l�me body na dv� stejn� velk� poloviny podle x�ov� sou�adnice� pro n�� rekurzivn�zavol�me tento algoritmus Zb�v��li nyn� jedin� bod� nepou�ijeme dal�� rekurzivn� vol�n��ale po�leme tento bod na v�stup jako konvexn� obal sama sebe ��zar��ka� rekurze�

� Pou�ijeme line�rn� algoritmus pro nalezen� konvexn�ho obalu dvou disjunktn�ch konvex�n�ch mnoho�heln�k� �viz lemma ���� aplikovan� na konvexn� obaly obou polovin p�vodn�mno�iny� kter� jsme dostali jako v�sledky rekurzivn�ch vol�n� v p�edchoz�m kroku

Po��te�n� uspo��d�n� spot�ebuje O�n log n� �asu#as rekurzivn� ��sti"

T �n� T �bn� c� ! T �dn� e� !O�n�

� � KONVEXN� MNOHO�HELN�KY

T �n� � T �bn�c� ! T �dn�e� !O�n� �

atd Celkem to je O�n log n�

���� Pozn�mka� Na�li jsme doposud �ty�i algoritmy� kter� pracuj� v �ase O�n log n� M��emesi tedy mezi nimi vybrat metodu odpov�daj�c� nejl�pe konkr�tn� implementaci Lep��ho �asu ne�O�n log n� v�ak u� nelze dos�hnout� proto�e dostaneme�li na vstupu mno�inu bod� n�hodn�rozm�st�n�ch na kru�nici� nalezen� jejich konvexn�ho obalu znamen� pr�v� jejich set��d�n� podle�hl� na t�to kru�nici Proto nenajdeme algoritmus pracuj�c� v lep��m asymptotick�m �aseTato �vaha by mohla znamenat� �e jsme na�li optim�ln� algoritmy pro nalezen� konvexn�ho

obalu Uvedeme v�ak je�t� dal�� dva algoritmy� jejich� obecn� �asov� slo�itost bude v jednomp��pad� i hor�� ne� O�n log n�� ale o�ek�van� slo�itost pro jist� distribuce bod� v rovin� budelep�� Tento rozbor provedeme v ��sti �

N�sleduj�c� algoritmus kombinuje metodu Graham.s Scan a p��stup rozd�l a panuj Budemenyn� rozd�lovat vstupn� mno�inu na podmno�iny bez ohledu na rozd�len� bod� podle sou�adnicKonvexn� obal t�chto podmno�in se bude po��tat rekurzivn� Pro v�sledn� mnoho�heln�kys potenci�ln� nepr�zdn�m pr�nikem spo��t�me jejich konvexn� obal metodou Graham.s ScanVyu�ijeme k tomu n�sleduj�c� lemma���� Lemma� M�me�li k dispozici dv� set��d�n� posloupnosti bod�� set��d�me je v�echnyv line�rn�m ase�D kaz� Udr�ujeme dva ukazatele dovnit� posloupnost�� do ka�d� jeden Na po��tku ukazuj� obana nejmen�� prvky obou posloupnost� Postupujeme tak� �e vybereme v�dy men�� ze dvou prvk��na kter� ukazujeme� a odpov�daj�c� ukazatel posuneme na dal�� prvek v jeho posloupnosti

A nyn� ji� samotn� algoritmusAlgoritmus ��� MergeHull

Vstup� kone�n� mno�ina S bod� v rovin�V�stup� vrcholy konvexn�ho obalu S� set��d�n� ve sm�ru hodinov�ch ru�i�ek

� Pro jist� mal� po�et bod� na vstupu spo��t�me konvexn� obal p��mo �nap� jedin� bodje s�m sv�m konvexn�m obalem�

Rozd�l�me body na dv� ��sti p�ibli�n� stejn� mohutnosti a zavol�me rekurzivn�MergeHull

� M�me nyn� dva konvexn� mnoho�heln�ky� kter� se mohou p�ekr�vat Vybereme libovoln�vnit�n� bod p jednoho z nich Ten bude jist� uvnit� jejich konvexn�ho obalu

Je�li p z�rove� uvnit� druh�ho mnoho�heln�ka� jsou vrcholy obou mnoho�heln�k� jakspolu soused� monot(nn�mi posloupnostmi vzhledem k �hl�m� kter� sv�raj� jejich spojnices bodem p

Nen��li p vnit�n� bod druh�ho mnoho�heln�ka� spust�me na� z bodu p te�ny Body do�tyku roztrhnou mnoho�heln�k na dva �et�zce Ten bli��� bodu p bude jist� cel� uvnit�v�sledn�ho konvexn�ho obalu a nebudeme jej proto br�t v �vahu Vn�j�� �et�zec je op�tposloupnost� monot(nn� vzhledem k �hl�m spojnic jednotliv�ch bod� s bodem p

Dost�v�me tak dv� posloupnosti bod� set��d�n� podle jejich �hl� V line�rn�m �ase z nichum�me sestrojit jedinou monot(nn� posloupnost� kterou pak po�leme na vstup algorit�mu ��

�� Konvexn� obal mno�iny bod� ve vy���ch dimenz�ch ��

MergeHull pracuje op�t v �ase O�n log n�� co� se odvod� ekvivalentn� odvozen� �asu algorit�mu �� Na rozd�l od n�ho v�ak MergeHull net��d� na za��tku body� a tak o�ek�van� �as budejist� lep�� Linearita jednoho vol�n� MergeHull �bez rekurzivn� ��sti� je nejhor�� p��pad� kdyob� podmno�iny budou m�t line�rn� velik� konvexn� obaly Diskuse o�ek�van�ch �as� budeprovedena v ��sti �Algoritmus Jarvis�s March postupuje po vrcholech konvexn�ho obalu Najde nejprve jeden

vrchol� kter� m� n�kterou sou�adnici extr�mn� a bude tedy jist� vrcholem konvexn�ho obaluTento vrchol ozna��me za aktu�ln� a hled�me jeho souseda v BCHD�le postupujeme tak� �e �nat���me� polop��mku vych�zej�c� z aktu�ln�ho vrcholu do ostat�

n�ch bod�� a� najdeme p��mku� v jej�� jedn� polorovin� le�� v�echny ostatn� body vstupn� mno��iny Znamen� to vlastn� naj�t bod� pro n�j� p��mka spu�t�n� z aktu�ln�ho vrcholu na n�hom� extr�mn� �hel Tento bod je rovn�� vrcholem BCH Prohl�s�me jej za aktu�ln� vrcholV hled�n� vrchol� takto pokra�ujeme� dokud se nevr�t�me do �pln� prvn�ho vrcholu

Algoritmus ��� JARVISS MARCH � algoritmus pro z�sk�n� konvexn�ho obalumno�iny bod� v rovin�

Vstup� kone�n� mno�ina S bod� v rovin�V�stup� vrcholy konvexn�ho obalu S� set��d�n� ve sm�ru hodinov�ch ru�i�ek

� vybereme bod s nejmen�� y�ovou sou�adnic� za aktu�ln� vrchol

repeat

� spoj�me aktu�ln� vrchol s ostatn�mi body a za dal�� vrchol BCH vybereme nejbli���z t�ch� kter� spojuje s v�choz�mnejmen�� �hel po��tan� mezi jejich spojnic� a posledn�p�idanou hranou �m�me�li zat�m pouze prvn� bod� vezmeme m�sto t�to hrany osu x�

aktu�ln� vrchol " nov� vybran� vrchol

� until aktu�ln� vrchol je op�t ten �pln� p�vodn�

Prvn� krok algoritmu je line�rn� V ka�d�m kroku cyklu je identi�kov�na pr�v� jedna hranakonvexn�ho obalu Tento krok zji�*uje extr�m mezi nejv��e n vrcholy� proto zabere O�n� �asuJarvis.s March pracuje tedy v �ase O�n� !O�nH� O�nH�� kde H je po�et hran v�sledn�hoBCH

Po�et hran v�sledn�ho konvexn�ho obalu m��e b�t a� O�n� � op�t p��klad se v�emi body nakru�nici Proto Jarvis.s March pracuje v kvadratick�m �ase O�n�� Tento algoritmus v�ak� narozd�l od ostatn�ch uveden�ch v t�to ��sti� bude v�t�inou pracovat v lep��m �ase� ne� kter� jsmeodhadli pro nejhor�� p��pad V�ce k tomu podkapitola �

��� Konvexn� obal mnoiny bod� ve vy�ch dimenz�ch

���� Pozn�mka� P�edpokl�d�me�li� �e ��dn� t�i body z mno�iny bod� v rovin� nele�� nap��mce� je konvexn�m obalem t�chto bod� konvexn� mnoho�heln�k Nele���li ��dn� �ty�i bodyv rovin� ze vstupn� mno�iny bod� v prostoru� je jejich konvexn�m obalem konvexn� simplici�ln�mnohost�n Obecn�� konvexn�m obalem mno�iny bod� v Rd je ddimenzionln� simpliciln�mnohost�n� jeho� st�ny jsou v prostoru Rd�� simplexy M��eme je tedy nazvat simpliciln�nadst�ny To ov�em plat� za p�edpokladu� �e ��dn�ch d ! � bod� vstupn� mno�iny nele��v �d ���dimenzion�ln� nadrovin�

�� � KONVEXN� MNOHO�HELN�KY

hrana V� V� F� F� P� P��" � � � �

JJJJJ

HHHLLLLLLLL

�����

���e

ev�

v�

f�

f��h�

h�h�

h�

hh�

h�

Obr ��" Jedna polo�ka dvojit�ho spojov�ho seznamu

Metoda Graham�s Scan z algoritmu �� nen� ve v�cerozm�rn�m prostoru ��inn�Pop��eme si nyn� zobecn�n� principu Jarvis�s March ve t�ech dimenz�ch �algoritmus ���

Budeme se sna�it pohybovat po povrchu v�sledn�ho simplici�ln�ho mnohost�nu a postupn�za�azovat jeho vrcholy� a� zjist�me� �e jsme se dostali na za��tek na�eho hled�n� Metoda sev�ak d� pou��t obecn� v d�dimenzion�ln�m prostoru

Algoritmus ���� Giftwrapping method

� Najdeme nejprve bod s nejmen�� z�ovou sou�adnic� a jednu hranu konvexn�ho obalu Tutohranu m��eme z�skat nap� tak� �e vstupn� mno�inu prom�tneme do roviny ur�en� osamixz a tam metodou Jarvis�s March najdeme tuto jednu hranu Zvol�me tuto hranu zaaktu�ln�

repeatKolem aktu�ln� hrany nat���me rovinu do v�ech bod� vstupn� mno�iny a vyberemeten bod� pro n�j� odpov�daj�c� rovina d�l� prostor na dva poloprostory� z nich� jedenobsahuje celou vstupn� mno�inu bod� Takov� bod se d� op�t naj�t ur�en�m minim�ln�ho�hlu� kter� sv�raj� v�echny takov� roviny s rovinou st�ny BCH� jej�� je aktu�ln� hrana��st� �op�t� m�me�li zat�m k dispozici pouze inicializa�n� hranu z prvn�ho kroku� vezmemerovinu xy�

� until Mnohost�n je uzav�en� tedy neexistuj� v n�m �neuzav�en�� hrany �jsou to hrany�kter� zat�m inciduj� pouze s jednou st�nou� Najdeme�li takovou hranu� vezmeme ji zaaktu�ln� a pokra�ujeme v cyklu

Celkov� �as algoritmu je op�t O�nH�� kde H je zde po�et st�n v�sledn�ho BCH V�echnyoperace v prvn�m kroku jsme schopni vykonat v line�rn�m �ase� cyklus prob�hne H�kr�t� abude hledat extr�mmezi nejv��e n vrcholy Tento �asov� odhad je platn� pro v�echny dimenze�jen H zde vystupuje jako po�et simplici�ln�ch nadst�n�� kter� tvo�� v�sledn� konvexn� obal

Odvod�me nyn� �asovou slo�itost pro t�i dimenze���� Vta� Algoritmus Gift�wrapping method pracuje ve t�ech dimenz�ch v ase O�n���D kaz� Pot�ebujeme dok�zat� �e nejvy��� mo�n� po�et st�n je line�rn� Mus�me po��tat s nejhor���m p��padem� tedy �e v�echny body z�stanou vrcholy konvexn�ho obalu �nap� kdy� v�echny

�� Porovn�n� algoritm� pro nalezen� konvexn�ch obal� bod� ��

le�� na povrchu koule� V�me� �e hran je v mnohost�nu pr�v� ��kr�t tolik� co st�n Bereme�li

toti� jednotliv� st�ny a d�v�me do posloupnosti jejich hrany �v�dy t�i�� dostaneme posloupnosthran� v n�� bude ka�d� hrana pr�v� dvakr�t Dosad�me�li do Eulerova vzorce

h! s! v

kde h je po�et hran� s je po�et st�n a v po�et vrchol�� dostaneme rovnost

s v Nen��li v�sledn� mnohost�n simplici�ln�� lze ka�dou st�nu� kter� nen� troj�heln�kem� na

troj�heln�ky rozd�lit Pro takto zv�t�en� po�et st�n plat� vztah z p�edchoz�ho odstavce� je tedypro n�s horn�m odhademCelkem dost�v�me slo�itost O�n�� �

Pam�*ov� struktury pou�iteln� pro algoritmus Gift�wrapping method stoj� za pozn�mku���� Pozn�mka� Pro mnohost�ny a plan�rn� grafy se d� pou��t struktura dvojit�ho spojov�hoseznamu �double connected edge list� DCEL� viz tak� /Preparata���0� str ������ Pro ka�douhranu m�me �est atribut� V�� V�� F�� F�� P�� P� V� a V� jsou ukazatele na vrcholy� kter� jsoukrajn�mi body hrany F� a F� ukazuj� na st�ny� kter� inciduj� s hranou� nejl�pe v dohodnut�mpo�ad� �nap� F� je ta st�na� kter� se jev� nalevo od hrany� d�v�m�li se ve sm�ru od V� k V� �P� je pak odkaz na tu hranu� kter� m� s danou hranou spole�nou st�nu F� a vrchol V� � respst�nu F� a vrchol V� pro ukazatel P� Budou to vlastn� hrany �soused�c�� v krajn�ch bodechdan� hrany s touto hranou ve sm�ru proti ot��en� hodinov�ch ru�i�ek �viz obr ���Z�rove� s v��e popsan�m seznamem hran udr�ujeme seznam vrchol� a st�n� pro n�� udr�

�ujeme jedin� atribut� a to n�kterou incidentn� hranu Uvnit� seznamu hran ji� m��eme velmiefektivn� vyhledat v�echny hrany na okraji jist� st�ny� v�echny hrany vych�zej�c� z jist�ho vr�cholu� v�echny vrcholy na okraji jist� st�ny atd V�echna tato vyhled�v�n� lze prov�d�t p��mo�a v�sledn� �as je �m�rn� velikosti v�sledkuV p��pad� algoritmu Gift�wrapping method je u�ite�n� m�t zvl��tn� seznam ne�pln�ch hran

Vyhled�n� takov� hrany pak bude prob�hat v konstantn�m �ase� stejn� jako ov��en�� zda takov�hrany je�t� existuj�� co� odpov�d� testu na konec algoritmu

��� Pozn�mka� Algoritmus Gift�wrapping se d� snadno zobecnit do vy���ch dimenz� Kon�vexn� obaly v Rd pro d � lze takto naj�t v �ase O�nbd��c���!O�nbd��c log n�� viz /Preparata���0

��� Porovn�n� algoritm� pro nalezen� konvexn�ch obal� bod�

V rovin� jsme nalezli n�kolik algoritm� pracuj�c�ch v �ase O�n log n� V praxi od nich nem��emeo�ek�vat lep�� �as� proto�e pou��vaj� v n�jak� podob� bu) t��d�n� nebo rekurziJak uvid�me� lze od algoritm� Jarvis.s March a Gift�wrapping method o�ek�vat ve skute��

nosti lep�� �asy� ne� ty� kter� jsme odvodili pro nejhor�� p��pady Dal��m algoritmem� kter� jez hlediska o�ek�van�ho �asu v�razn� lep�� ne� v nejhor��m p��pad�� je MergeHull �alg ���Tento algoritmus pracoval metodou rozd�l a panuj a volal rekurzivn� s�m sebe Jeho �asov�slo�itost T �n� se odvod� pomoc� vztahu

T �n� T �n� � ! C�n��� �

kde C�n� je �as pot�ebn� na �panov�n��

�� � KONVEXN� MNOHO�HELN�KY

���� Vta� Plat� n�sleduj�c� z�vislost hodnoty T �n� na C�n� ze vztahu �!T �n� C�n�O�n� O�n log n�

O�n� log n� O�n log log n�O�n� O�np� p � �

D kaz� uvedeno v /Preparata���0� str ��� bez d�kazu �

Tabulka � shrnuje nejhor�� i o�ek�van� �asy algoritm� pro nalezen� konvexn�ho obaluUvedeme� jak� po�et simplici�ln�ch nadst�n konvexn�ho obalu mno�iny bod� budeme o�e�

k�vat u n�kter�ch distribuc� bod� vstupn� mno�iny���� Vta� Je�li n bod� vybr�no n�hodn� uniformn� distribuc� v rovinn�m konvexn�m r��heln�ku� pak pro n�� se po et hran konvexn�ho obalu t�chto n bod� bl���

E�H� � r���� ! loge n� !O�������

kde � je Eulerova konstanta ��D kaz� Neuveden� /Preparata���0 odkazuje na text /R�nyi���0 �

���� Vta� Je�li n bod� vybr�no n�hodn� uniformn� distribuc� uvnit� d�dimenzion�ln� hy�perkoule� pak pro n � � se po et simplici�ln�ch nadst�n konvexn�ho obalu t�chto n bod�bl���

E�H� O�n�d�����d�������

���� Vta� Je�li n bod� vybr�no n�hodn� norm�ln� distribuc� v cel�m prostoru Rd pak pron�� se po et simplici�ln�ch nadst�n konvexn�ho obalu t�chto n bod� bl���

E�H� O��log n��d����������

D kaz� Ani d�kaz posledn�ch dvou tvrzen� neuv�d�me� /Preparata���0 odkazuje na /Raynaud���0�

�� Aplikace

Uvedeme nyn� dva probl�my� kter� jsou p��buzn� konvexn�m obal�m

Konvexn� vrstvy �Convex Layers� Zad�n� spo��v� v nalezen� do sebe vno�en�ch kon�vexn�ch obal�� mezi nimi� nele�� ��dn� dal�� body vstupn� mno�iny Jde vlastn� o opakovan�hled�n� konvexn�ho obalu pro body uvnit� p�edchoz�ho konvexn�ho obalu � viz obr ��S t�m souvis� i probl�m zji�t�n� hloubky bodu v dan� mno�in�� co� je po�ad� konvexn� vrstvy�

ve kter� bod le��� po��t�no od vn�j�ku Nap� na obr�zku �� m� bod A hloubku � a bod Bhloubku Je jist� mo�n� opakovan� aplikovat n�kter� algoritmus pro hled�n� konvexn�ho obalu� to

by v�ak vedlo ke slo�itosti nejhor��ho p��padu O�n� log n� Vhodn�j�� by byl Jarvis.s March�kter� bude pracovat v �ase 1�n�� /Preparata���0 uv�d� na stran� ��� odkaz na /Chazelle���0�kter�mu se poda�ilo doc�lit pro oba probl�my �asu 1�n log n�

�� � limn�� �Pn

i�� �i� loge n��� ������ ������ ���������� ������� � � �

��� Aplikace ��

nejhor�� distribuce bod�algoritmus p��pad v r��heln�ku v kruhu v rovin�po�et hran O�n� O�r log n� O�n��� O��log n�����Jarvis�s March O�n�� O�n log n� O�n��� O�n

plog n�

MergeHull O�n log n� O�n� O�n� O�n�ostatn� O�n log n�

nejhor�� distribuce bod�algoritmus p��pad v kouli v prostorupo�et st�n O�n� O�n���� O�log n�Gift�wrapping O�n�� O�n��� O�n log n�

Tabulka �" Shrnut� �asov�ch slo�itost� algoritm� pro nalezen� konvexn�ho obalu

e e

e

e� ee e

�����T

TTT

�����������

������

����EEEEEEEEEE

ee

A

B

C

Obr ��" Konvexn� vrstvy

� � VORON"HO DIAGRAMY

Shluky Jde o nalezen� shluk� �clusters� bod� s co nejmen��m pr�m�remP�i hled�n� shluk� naraz�me na probl�m pr�m�ru mno�iny bod�� co� je nejv�t�� vzd�lenost

mezi dvojic� bod� v mno�in� Tento pr�m�r odpov�d� pr�m�ru konvexn�ho obalu dan� mno�inyJe�li ji� zn�m BCH t�to mno�iny� lze pr�m�r naj�t v �ase line�rn�m �jednoduch� cvi�en��Konvexn� obal dan� mno�iny najdeme v �ase O�n log n�

� Voron�ho diagramy

Voron�ho diagramy maj� n�kolik modi�kac� Budeme se zab�vat nejprve nejjednodu��� z nich�a pak uvedeme jist� zobecn�n� tohoto p��padu V n�kter�ch podkapitol�ch se budeme zab�vatprobl�my� kter� lze s vyu�it�m Voron�ho diagram� efektivn� �e�it

��� Konstrukce Voron�ho diagramu

V t�to ��sti uvedeme de�nici nejjednodu���ho Voron�ho diagramu v rovin� Uk��eme n�kolikz�kladn�ch vlastnost�� a p�ejdeme ke konstrukci tohoto diagramu v optim�ln�m �ase

��� De�nice� Nech* S fx�� � � � � xng � R� Voron�ho oblast bodu xi � S je

V RS�xi� " fy � R� j �� � j � n " dist�xi� y� � dist�xj� y�g

Voron�ho diagram p��slu�n� mno�in� S je rozd�len� roviny na n Voron�ho oblast�� zna��meV D�S�

Na obr�zku � je ilustrov�n p��pad Voron�ho diagramu pro mno�inu p�ti bod� v rovin�

��� Lemma� V R�xi� je konvexn� mnoho�heln�kov� oblast�

D kaz� Ozna�meHi�j " fy � R� j dist�xi� y� � dist�xj� y�g

To je z�ejm� polorovina a z�rove� konvexn� �tvar Nav�c V RS�xi� se d� zapsat jakoTi� j Hi�j

Pak V RS�xi� mus� b�t konvexn� a je pr�nikem polorovin� tedy je to mnoho�heln�kov� oblast�

��� Lemma� V RS�xi� je neohrani en� oblast pr�v� tehdy� kdy� xi le�� na okraji konvexn�hoobalu mno�iny S �xi � BCH�S��

D kaz� " Nech* V RS�xi� je neohrani�en� Pak v n� jist� le�� n�jak� polop��mka vych�zej�c�z xi Tato mus� prot�nat BCH�S�� nap� v hran� L�xj� xk� Za ��elem sporu d�le p�edpokl��dejme� �e xi nele�� na hranici konvexn�ho obalu Tedy xi �� L�xj� xk�� a ve V R�xi� jsou body�kter� jsou bl��e xj nebo xk ne� xi� co� je spor

� " Nech* xi � BCH�S�� xj a xk jsou jeho sousedi Pak body na polop��mce kolm�k L�xj� xk� proch�zej�c� bodem xi jsou bl��e k xi ne� ke v�em ostatn�m bod�m� tedy oblastV R�xi� nen� ohrani�en� �

�V anglick�m literatue je uveden term�n Voronoi diagrams� Diagramy uv�d�me jako Voron�ho� proto�eVoronoiho je jazykolam� a krom toho je pravdpodobn�� �e jm�no je to rusk� �voronoj� nebo francouzsk��voronoa�� V obou p�padech je pivlast�ovac� tvar �voron�ho��

��� Konstrukce Voron�ho diagramu �

ee

e

ee

Obr � " Voron�ho diagram p�ti bod�

Sezn�m�me se nyn� s pojmem Delaunayova triangulace Souvis� �zce s Voron�ho diagramy�je vlastn� prvn� jejich vyu�itelnou aplikac� S pomoc� t�to triangulace lze tak� snadno uk�zatn�kter� vlastnosti Voron�ho diagram�

��� De�nice� Nech* S � R�� jSj n P�edpokl�dejme d�le� �e ��dn� �ty�i body z S nele�� nakru�nici Pak graf D s vrcholy z S a hranami spojuj�c�mi pr�v� ty body z S� jejich� Voron�hooblasti sd�l� hranu� je triangulac� CH�S� Naz�v�me ji Delaunayova triangulace

�� Vta� Delaunayova triangulace m� tu vlastnost� �e kru�nice opsan� libovoln�mu jej�mutroj�heln�ku neobsahuje ji� ��dn� dal�� body vstupn� mno�iny�

D kaz� Voron�ho oblasti jsou mnoho�heln�kov� oblasti� ohrani�en� osami �se�ek� kter� spojuj�jist� dvojice bod� z mno�iny S K tomuto v�sledku vede �vaha z d�kazu lemmatu Vezmemenyn� v �vahu libovoln� troj�heln�k ABC Delaunayovy triangulace� jak ukazuje tak� obr�zek ��Osy �se�ek AB� BC� AC� zna�en� postupn� c� a� b� tvo�� hranice jednotliv�ch Voron�ho oblast�odpov�daj�c�ch bod�m A� B a C Jejich pr�se��k K je tedy bodem� kter� pat�� z�rove� dov�ech t�� oblast� Jeho vzd�lenost je tedy od v�ech t�� bod� stejn�� a z�rove� vzd�lenost odlibovoln�ho jin�ho bodu mno�iny je v�t�� Tento bod je tedy st�edem kru�nice� na n�� le�� bodyA� B i C� a uvnit� n�� nele�� ji� ��dn� dal�� bod mno�iny S �

��� Lemma� Voron�ho diagram mno�iny S s n body m� nejv��e n vrchol� a �n � hran�

D kaz� Delaunayova triangulace DS je rovinn� graf� m� tedy nejv��e �n � hran �pro n � �Zd�vodn�n�"Uspo��d�me do posloupnosti v�echny hrany v�ech st�n v rovinn�m grafu Po�et hran budeme

zna�it h� po�et st�n s a vrchol� n Ka�d� hrana se v t�to posloupnosti vyskytuje pr�v� dvakr�t�za ka�dou st�nu� kterou ohrani�uje� jednou�� posloupnost m� proto d�lku h Za ka�dou st�nu

� VORON"HO DIAGRAMY

A

B

C

Obr ��" Jeden troj�heln�k Delaunayovy triangulace a jeho souvislost s Voron�ho diagramem

jsou v posloupnosti pro n � alespo� t�i hrany� proto d�lka posloupnosti je alespo� �s Tedy h � �s Vyu�ijeme Eulerova vztahu h! n ! s"

�h! � �n ! �s�h ! � �n �s � h

h � �n �V nedegenerovan�m p��pad� ���dn� �ty�i body nele�� na kru�nici� jsou hrany v bijekci

s hranami V D�S� a po�et hran je roven �n �� v degenerovan�m p��pad� m�n� V�echnyvrcholy V D�S� maj� stupe� alespo� t�i� proto po�et vrchol� je nejv��e �

��n �� n �

Nyn� se vrhneme na konstrukci Voron�ho diagramu Nejprve odhadneme nejlep�� �asovouslo�itost� kter� m��eme dos�hnout

��� Vta� Ka�d� algoritmus pro nalezen� Voron�ho diagramu mno�iny n bod� bude pro nej�hor�� p��pad pot�ebovat alespo# 2�n log n� asu�

D kaz� Uv���me�li nejhor�� p��pad mno�iny n bod� le��c�ch na kru�nici� budou Voron�ho oblastiohrani�en� v�dy dv�ma polop��mkami vych�zej�c�mi ze st�edu t�to kru�nice Tyto polop��mkyjsou osami �se�ek spojuj�c�ch sousedn� body Pro nalezen� Voron�ho diagramu je tedy pot�ebaodhalit dvojice sousedn�ch bod� na kru�nici� co� odpov�d� set��d�n� bod� podle �hl� �

N�sleduj�c� v�ta se skl�d� z n�kolika tvrzen�� na kter�ch je postaven cel� n�� algoritmus kon�strukce Voron�ho diagramu V�ta operuje se dv�ma stejn� velk�mi podmno�inami mno�iny S�jejich� Voron�ho diagramy jsou zn�my To vlastn� u� napov�d�� jak bude vypadat algoritmuske kter�mu sm��ujeme" metoda rozd�l a panuj s rekurzivn�m vol�n�m sebe sama

��� Konstrukce Voron�ho diagramu �

��� Vta� Nech� S fx�� � � � � xng � R�� nech� SL a SR je lev� a prav� polovina S vzhledemk lexik�ln�mu set��d�n�� P�edpokl�dejme� �e zn�me V D�SL� i V D�SR�� De$nujme

P " fy � R� j dist�y� SL� dist�y� SR�g

P je tedy mno�ina v�ech bod�� kter� maj� stejnou vzd�lenost od SL a SR� Ozna me d�le L�P � �st roviny nalevo od P � R�P � napravo od P �

Potom plat�!�� P % fy j y le�� na hran� V D�S� kolm� na spojnici L�xi� xj� pro n�jak� xi � SL� xj � SRg�� P je monot&nn� �p�i vhodn� orientaci ��dn� z hran P nesm��uje dol�

� V D�S� �V D�SL� � L�P �� � P � �V D�SR� �R�P ��� 'Nejspodn�j��( hrana P je polop��mka a z�rove# osa doln� te ny BCH�SL� a BCH�SR��

D kaz�

� Ozna�me pravou stranu v�razu jako Q M�me nyn� dok�zat dv� mno�inov� inkluze

� P � Q" Nech* bod y � P Tedy vzd�lenost bodu y od mno�in SL a SR je stejn�Vybereme nyn� ten bod z mno�inySL� kter� m� od y nejmen�� vzd�lenost� a ozna��mexL Stejn� vybereme bod xR v mno�in� SR V�me� �e vzd�lenost y od xL je stejn�jako jeho vzd�lenost od xR Krom� toho je libovoln� jin� bod SL i SR �a tedy i S�d�le od bodu y Proto y ve V D�S� odd�luje V R�xL� od V R�xR�� le�� tedy na hran�kolm� na spojnici bod� xL a xR

� Q � P " Nech* y � Q Pak

�x � S dist�y� S� dist�y� xi� dist�y� xj� � dist�y� x�

Z toho u� plyne� �e

dist�y� SL� dist�y� xi� dist�y� xj� dist�y� SR�

a bod y je tedy prvkem P

D�ky lexik�ln�mu rozd�len� mno�iny S na SL a SR m��eme �se�ky v P orientovat tak�aby body z SL byly v�dy vlevo p�i pohledu ve sm�ru orientace �se�ek

� Ozna�me pravou stranu v�razu jako D M�me nyn� dok�zat dv� mno�inov� inkluze

� V D�S� � D" y � V D�S�� tj y le�� na n�kter� z hran� proto existuj� i� j tak� �edist�y� xi� dist�y� xj� � dist�y� x� �x � S Pokud xi� xj � SL� pak z�ejm� y �V D�SL� � L�P � Je�li xi � SL� xj � SR� pak y � P Analogicky pokud xi� xj � SR�pak y � V D�SR� �R�P �

� V D�S� � D" y � D Je�li y � P � pak y � V D�S�y � V D�SL� � L�P �" y � L�P � dist�y� SL� � dist�y� SR� a proto�e y � V D�SL��existuj� xi� xj � SL tak� �e dist�y� SL� dist�y� xi� dist�y� xj� � dist�y� x� �x �S y � V D�S�Pro y � V D�SR� � L�P � je d�kaz analogick�

� VORON"HO DIAGRAMY

V�me� �e nejspodn�j�� hrana P je tak� hranou V D�S� Je z�ejm�� �e je to polop��mkaZbytek tvrzen� je intuitivn� jasn�� form�ln� plyne z lemmatu �

V n�sleduj�c�m algoritmu budeme p�edpokl�dat� �e u� zn�me V D�SL� i V D�SR�� a �emno�iny SL a SR jsou rozd�leny podle lexikogra�ck�ho uspo��d�n� jako ve v�t� � Podle bodu� p�edchoz� v�ty sta�� naj�t d�lic� lomenou ��ru P � a ohrani�it pomoc� n� p�vodn� Voron�hodiagramy Sjednocen�m dostaneme Voron�ho diagram cel� mno�iny S Jde vlastn� o posledn�krok algoritmu rozd�l a panuj � kter� spojuje dohromady meziv�sledkyOzna��me L nejspodn�j�� hranu lomen� ��ry P �bod v�ty ��P�edpokl�dejme� �e postupujeme p�i hled�n� P odspodu� a m�me u� ��sti L� e�� e�� � � � � en

lomen� ��ry P � p�i�em� posledn� �se�ka �i polop��mka zat�m nen� omezena Pak bu) neprot��n� ��dnou z hran V D�SL�� V D�SR� � v tom p��pad� jsme pr�v� z�skali posledn� polop��mku��nehorn�j��� hranu� L� ��ry P � nebo prot�n� nap� nejd��ve V D�SL�� a to v bod� z na hran�e V SL jsou body xi� x

�i takov�� �e e � V R�xi�� e � V R�x�i�� dist�xi� z� dist�x�i� z� en v�ak

mus� b�t osou �se�ky spojuj�c� jeden z bod� xi� x�i �nech* je to nap� xi� a n�jak� bod z SR�nap� xj Jeliko� bod z le�� na en� je stejn� vzd�len od bod� xi� x�i i xj Z�rove� v�ak ��dn�bod mno�iny S nen� bodu z bl��e� proto z je vrchol V D�s� Zde tak� je kon�� hrana en lomen���ry P � a za��n� dal�� hrana en��� kter� je osou �se�ky L�x�i� xj�

Algoritmus ��� Algoritmus tzv �se��v�n�� V D�SL� a V D�SR�

Vstup " V D�SL�� V D�SR�V�stup " V D�SL � SR�

� h " �

� TL � � � doln� te�na BCH�SL�� BCH�SR� spojuj�c� x � SL� y � SR� L � � � polop��mka� kter� je osou L�x� y�

l� " L

� while L prot�n� V D�SL� nebo V D�SR�

�� if L protne nejd��ve e � V D�SL� then��� z " bod pr�niku�� lh ukon�i v z��� x� " bod SL tak� �e e � V R�x�� e � V R�x���� x " x�%h " h! ���� L " polop��mka za��naj�c� v z� osa L�x� y���� lh " L

� else symetricky pro SR

#asov� slo�itost tohoto algoritmu p�i reprezentaci Voron�ho diagramu dvojit�m spojov�m se�znamem �doubleconnectededgelist � viz pozn�mka � a algoritmus ��� GiftWrapping� jeO�n�� kde n je po�et bod� sjednocen� mno�in SR a SL Po�et v�ech hran obou diagram�V D�SL� i V D�SR� toti� nep�ev��� dohromady �n � podle lemmatu �� a ani ��ra P nem��em�t v�ce ne� n hran� tedy �as z�st�v� line�rn�

Nyn� si m��eme dovolit tvrdit� �e��� Vta� Voron�ho diagram lze sestavit v optim�ln�m ase O�n log n��

��� Voron�ho diagramy v �ece �

�������j

�������j

�������j j��

�����

� � � � � � � � � �

Obr �" Kru�nice dosahu pro n�kter� hodnoty �

D kaz� Optim�lnost �asu ukazuje v�ta � Algoritmus pracuj�c� v tomto �ase lze zkonstruovatmetodou rozd�l a panuj Mus�me nejprve lexik�ln� uspo��dat body mno�iny S Potom budemed�lit S v�dy na dv� stejn� velk� poloviny podle uspo��d�n�� a rekurzivn� volat tento algoritmuspro ob� poloviny zvl��* Spojen� v�sledk� za��d� p�edchoz� algoritmus � �� Jako zar��ka rekur�ze m��e slou�it test na velikost vstupn� mno�iny Je�li toti� vstupem jedin� bod� jeho Voron�hodiagram je cel� rovinaPo��te�n� f�ze set��d�n� bod� bude trvat O�n log n� �asu Ozna��me�li �asovou slo�itost

zbytku algoritmu pro n bod� jako T �n�� dost�v�me" T �n� T �n� � !O�n� a T ��� �� tedyT �n� O�n log n� �

��� Voron�ho diagramy v �ece

Prvn�m mo�n�m zobecn�n�m Voron�ho diagram� je uveden� roviny do rovnom�rn�ho pohybuP��m�r k tekouc� �ece je zde velice v�sti�n� Oby�ejn� Voron�ho diagram je speci�ln�m p��pademtohoto pro rychlost plovouc� roviny rovnu nuleZ dan�ch bod� roviny se ���� konstantn� rychlost� v vzruch v�emi sm�ry M�me vytvo�it

rozd�len� roviny� kter� �pluje� konstantn� rychlost� w Ozna�me � wv� tzv relativn� rychlost

Z bodu ��� �� se v �ase t rychlost� v pod �hlem � dostaneme do bodu

�x� y� �tw ! tv cos �� tv sin ��

Jde tedy o kru�nici se st�edem �tw� �� a polom�rem tv

���� De�nice� Voron�ho diagram V D��S� de�nujeme jako rozd�len� cel� roviny na oblastiV R��xi�� xi � S� do nich� se z bodu xi dostaneme nejrychleji za v��e uveden�ch podm�nek

���� Pozn�mka� P�edchoz� de�nice je korektn�� proto�e pro p��slu�nost k Voron�ho oblastemv �ece nejsou rozhoduj�c� ob� hodnoty w i v� ale sta�� jejich pom�r � K ov��en� vede n�sleduj�c��vahaNech* hodnoty rychlost� jsou v a w a do bodu y se dostaneme z bodu xi v �ase ti Zm�n�me�li

ob� hodnoty rychlost� na jejich k�n�sobek� lze snadno ov��it� �e se z bodu xi dostaneme v �aseti�k do bodu y Minimummezi t�mito hodnotami z�stane tedy zachov�no� a s n�m i p��slu�nostbodu y k Voron�ho oblasti p��slu�n�ho diagramu

���� Pozn�mka� Pro � � � ve V R��xi� nen� ��dn� bod s men�� x�ovou sou�adnic� ne� m�xi

� � VORON"HO DIAGRAMY

eexi xj

w

d�

� �

tan � vw �

l v

Obr ��" Ku�ele pod body mno�iny S a �hel pr�m�tu zp�t do roviny

Voron�ho diagram V D��S� lze sestrojit pomoc� ku�el� pod body mno�iny S Vlo��me na�irovinu do t��rozm�rn�ho prostoru a nech* t�et� rozm�r odpov�d� �asu t� p�i�em� na�e p�vodn�rovina budi� polo�ena v �asov� rovin� t � Z ka�d�ho bodu vy�leme po jeho �asov� osekru�nice� do kter�ch se pr�v� d� z tohoto bodu dostat v dan�m �ase t Tyto kru�nice budou m�trovnom�rn� rostouc� polom�r a dostaneme tak v�dy pl��* ku�ele Tento postup je ilustrov�n naobr�zku �� Prom�tneme�li pr�niky t�chto ku�el� kolmo zp�t do roviny� dostaneme V D��S� V D�S�V��e uveden� postup lze zobecnit pro plovouc� rovinu Kru�nice pod body mno�iny S bu�

dou v �ase nejen rovnom�rn� zv�t�ovat sv�j polom�r a pohybovat se z�rove� po ose kolm� nap�vodn� rovinu �rychlost� v�� ale budou se z�rove� pohybovat ve sm�ru osy x rovnom�rn�mpohybem rychlost� w Ku�ely budou v kolm�m pr�m�tu p�esn� kop�rovat dosah vzruch� vypu��t�n�ch z bod� mno�iny S T�m doc�l�me toho� �e kolm�m pr�m�tem pr�nik� takov�ch ku�el�budou Voron�ho oblasti V R�Kru�nice pod body se vlastn� pohybuj� rychlost� danou vektorov�m sou�tem rychlost� v a w

Jej� v�slednice sv�r� s rovinou xy �hel � z obr�zku �� Prom�tneme�li tedy pr�niky p�vodn�chku�el�� nepohybuj�c�ch se ve sm�ru osy x� zp�t do roviny xy pod �hlem zn�zorn�n�mna obr�zku��� dost�v�me op�t spr�vn� v�sledekPo prom�tnut� se paraboly �pr�niky pl��*� ku�el�� prom�tnou na hyperboly V p��padech�

kdy � � �� p�ich�z� do �vahy pouze ty oblasti� kam se v�bec d� z jednotliv�ch bod� dostatTy jsou ohrani�eny polop��mkami veden�mi z t�chto bod� pod �hlem �% viz tak� obr�zek ��p��pad � � � Tyto polop��mky jsou pr�m�tem povr�ek na p��slu�n�m ku�elu vymezuj�c�ch vi�ditelnost p�i prom�t�n� Odtud plyne� �e hranice Voron�ho oblast� p�ech�z� z t�chto polop��mekna paraboly pr�v� v pr�m�tech m�st� kde se prot�naj� zm�n�n� povr�ky s pr�niky ku�el� Obr��zek �� nazna�uje v�sledn� Voron�ho diagramy V D��S�� rozd�len� na charakteristick� p��padypodle hodnoty �

���� Pozn�mka� Pro � � � je ka�d� bod mno�iny S nejlev�j��mbodem sv� oblasti D�ky tomum��eme zvolit alternativn� postup pro konstrukci V D��S� Jedn� se o metodu tzv pro�esvn��plovouc� horizont� sweep� Tento algoritmus nebudeme podrobn� rozeb�rat� zm�n�me se alestru�n� o principu metody� kter� bude pozd�ji u�ite�n� v �ad� dal��ch probl�m� Tato metoda

�� Probl�my nejbli���ch soused� �

e

ee

e

ee

e

ee

e

ee

� � �� �� � �� �

Obr ��" V�sledn� Voron�ho diagramy v �ece pro n�kter� hodnoty �

je zalo�ena na �lexikogra�ck�m� set��d�n� bod� v S a zaveden� tzv horizontln� a vertikln�struktury

� Horizont�ln� struktura� tedy rovnob��n� s osou x� obsahuje polohy tzv pro�esvac� p��mky� kter� je t�eba diskutovat Jde tedy o jak�si set��d�n� seznam bod� na ose x� o kter�chv�me� �e se v nich m��e m�nit pro n�s v�znamn� veli�ina Zpo��tku algoritmu bude tatostruktura obsahovat pr�v� x�ov� sou�adnice bod� z S� pozd�ji se k nim budou p�id�vatpr�se��ky hranic jednotliv�ch oblast� a body� ve kter�ch p�ech�z� hranice oblast� z p��mekna hyperboly

� Vertik�ln� struktura �pro�esvac� p��mka� je rovnob��n� s osou y Nech�me ji prob�hatpostupn� v�emi body z horizont�ln� struktury Na n� budou v�dy le�et v�znamn� hraniceoblast� �bu) body z p�vodn� mno�iny� nebo jin� pr�se��ky oblast��

P�i jednotliv�ch diskus�ch vertik�ln� struktury �pro�es�vac� p��mky� v �ase O�log n� z�sk�mealgoritmus o celkov�m �ase O�n log n�� proto�e v�ech bod� ze vstupn� mno�iny i pr�se��k�oblast� dohromady �a tedy prvk� horizont�ln� struktury� je O�n�V n�kter�ch dal��ch pro�es�vac�ch algoritmech m��e b�t pro�es�vac� p��mka naopak hori�

zont�ln� V t�chto p��padech bude zam�n�n faktick� v�znam horizont�ln� a vertik�ln� strukturyObecn� se lze setkat i s jin�m pro�es�vac�m objektem ne� je p��mka� nap� ve vy���ch dimenz�ch��asto tak� hovo��me o struktu�e udlost�� resp o statutu udlost��Podstatou pro�es�v�n� je redukce dimenze za cenu p�echodu k dynamick�m struktur�m

Pozd�ji se k t�to t��d� algoritm� vr�t�me podrobn�ji

V dal��ch dvou podkapitol�ch zm�n�me aplikace Voron�ho diagram� p�i �e�en� dvou �ast�ch�loh" nalezen� nejbli���ch soused� v mno�in� bod� a nalezen� minim�ln�ho pokr�vaj�c�ho stromumno�iny bod� v Euklidovsk� rovin�

��� Probl�my nejbli�ch soused�

Budeme se zab�vat t�emi probl�my nejbli���ch soused�"� Z kone�n� mno�iny bod� S � R�� jSj n vyber takov� dva body� kter� maj� nejmen��vzd�lenost �probl�m nalezen� nejbli���ho p�ru�

� � VORON"HO DIAGRAMY

Pro ka�d� bod x � S najdi jeho nejbli���ho souseda �probl�m nalezen� nejbli���ch soused��

� M�me�li d�nu pevn� mno�inu S a libovoln� bod v rovin� x� najdi v mno�in� S bodnejbli��� bodu x

Probl�m � znamen� vlastn� vyhled�n� oblasti ve Voron�ho diagramu mno�iny S� ve kter� le��bod x M�me�li tedy p�edspo��t�n Voron�ho diagram� sta�� pou��t n�kter� z algoritm� navyhled�v�n� v rovinn�ch rozd�len�ch� kter� uvedeme v kapitole � Na prvn� pohled se m��e zd�t podivn�� �e prvn� dva probl�my budeme �e�it ve stejn�m

�ase Nalezen� nejbli���ho p�ru budeme toti� �e�it tak� �e najdeme nejbli��� sousedy� a pakz nich vybereme tu nejbli��� dvojiciPokus�me se nazna�it d�kaz� �e v��e uveden� postup n�m skute�n� zaru�� optim�ln� �as i

pro nalezen� nejbli���ho p�ru Vyu�ijeme obecn� princip redukce probl�m�"Poda���li se transformovat v �ase O�f�n�� probl�m A na probl�m B� a m��li probl�m B

�asovou slo�itost O�g�n�� n�m p�edem zn�mou� a je�li funkce g asymptoticky v�t�� ne� f � v�me��e probl�m A m��eme �e�it v �ase O�g�n�� nebo hor��m Kdyby se n�m toti� poda�ilo vy�e�itprobl�m A v �ase lep��m� mohli bychom pomoc� transformace v �ase O�f�n�� dos�hnout celkem�asu lep��ho ne� O�g�n�� k vy�e�en� probl�mu B� co� je sporProbl�m � je transformovateln� na

zjisti� zda mezi n re�ln�mi ��sly jsou alespo� dv� stejn�

takto"Najdeme nejbli��� dvojici z �xi� ��� �xj� �� Pokud je jejich vzd�lenost v�t�� ne� nula� jsou

v�echna dan� ��sla r�zn� Probl�m� zda mezi n re�ln�mi ��sly jsou stejn�� je �e�iteln� v �ase2�n log n� D�kaz je uveden v /Preparata���0� strana �� Transformace zabere �as O�n� Kdybyse tedy poda�ilo naj�t nejbli��� p�r v �ase lep��m ne� 2�n log n�� po transformaci bychom znalilep�� �as ne� 2�n log n� i pro probl�m zji�t�n� rovnosti ��selProbl�m nalezen� nejbli���ch soused� se d� v �ase O�n� transformovat na nalezen� nejbli���ho

p�ru Ten toti� mus� b�t mezi n nejbli���mi sousedy� a prost�m vyhled�n�m minima ho lzevyhledat Nejbli��� sousedy tedy tak� nep�jde nal�zt v �ase lep��m ne� 2�n log n� N�sleduj�c��vahy sm��uj� ke zji�t�n�� �e to pr�v� v uveden�m �ase jdeN�sleduj�c� lemma charakterizuje chov�n� nejbli���ch soused� ve Voron�ho diagramu

���� Lemma� Nech� S � R�%x� y � S� Je�li V R�x� � V R�y� � nebo jV R�x� � V R�y�j ��pak existuje z � S tak� �e dist�x� z� � dist�x� y� a V R�x� a V R�z� sd�l� hranu�

D kaz� Pro p��pad V R�x��V R�y� � je to z�ejm� Nech* fpg L�x� y��V R�x� Bod p pat��do V R�z� pro jist� z takov�� �e V R�x� a V R�z� sd�l� hranu Z�rove� dist�x� p� dist�z� p��tedy

dist�x� z� � dist�x� p� � dist�x� y�

Rovnost m��e nastat pouze pro dist�p� x� dist�p� y� a p � L�x� z� �

Z lemmatu bezprost�edn� plyne

��� D�sledek� Pro ka�d� bod x z mno�iny S plat�� �e jeden z jeho nejbli���ch soused� mezibody z S s n�m sd�l� hranu ve V D�S��

Nejbli��� sousedy lze tedy hledat mezi sousedy ve Voron�ho diagramu

���� Vta� Nech� S � R�� jSj n� Je�li d�n V D�S�� pak probl�m nalezen� v�ech nejbli���chsoused� je �e�iteln� v ase O�n�� Proto i probl�m nalezen� nejbli��� dvojice lze �e�it v ase O�n��

�� Minim�ln� pokr�vaj�c� strom �

D kaz� Podle lemmatu � m� ka�d� prvek x � S nejbli��� sousedy y � S takov�� �e V R�x�a V R�y� sd�l� hranu P�i hled�n� budeme pro ka�d� bod hledat pouze mezi jeho sousedy veV D�S� Projdeme tedy ka�dou hranu nejv��e dvakr�t Po�et hran V D�S� je podle lemmatu �line�rn� V D�S� reprezentovan� dvojit�m spojov�m seznamemm��eme proj�t v line�rn�m �aseMezi line�rn�m po�tem v�sledk� najdeme minimum� tedy nejbli��� p�r� tak� v line�rn�m �ase

���� D�sledek� Probl�m nejbli���ch soused� i nejbli���ho p�ru lze �e�it v optim�ln�m aseO�n log n��

D kaz� Tvrzen� plyne z �vah o optimalit� probl�m� d��ve v t�to podkapitole� z v�ty � okonstrukci Voron�ho diagramu v �ase O�n log n�� a z p�edchoz� v�ty �

��� Minim�ln� pokr�vaj�c� strom

Obecn� probl�m nalezen� minim�ln�ho pokr�vaj�c�ho stromu �kostry� je pokryt p�edn��kou docPol�ka Grafov� algoritmy B��n� se uv�d� dva algoritmy �nap� v /MIT0��"

� Kruskal v algoritmus pracuje v �ase O�E logE�� kde E je po�et hran grafu

� Prim v algoritmus d�v� v�sledek v �aseO�E log V � p�i pou�it� haldy� respO�E!V log V �p�i pou�it� Fibonacciho haldy� kde E je op�t po�et hran a V po�et vrchol� grafu

Stoj� za zm�nku� �e pravd�podobn� prvn� algoritmus �e��c� tento probl�m nab�dl brn�nsk� ma�tematik prof Otakar Bor�vka� kdy� dostal ve ��t�ch letech za �kol navrhnout elektri�kaciMoravyMy se budeme zab�vat Euklidovskou modi�kac� probl�mu Uzly na�eho grafu budou vno�eny

do roviny s Euklidovskou metrikou� a graf budeme pova�ovat za �pln�

Probl�m Nalezn�te pro S � R�� jSj n strom T takov�� �e uzly jsou v�echny body z S�hrany jsou ohodnoceny vzd�lenost� mezi odpov�daj�c�mi body� a sou�et d�lek hran stromu T jeminim�ln� mezi v�emi takov�mi stromyAplikujeme�li Kruskalovy a Primovy v�sledky� dost�v�me �as O�n� log n�� resp O�n�� v p���

pad� Primova algoritmu s pou�it�m Fibonacciho haldyD�le uvid�me� �e speci�ln� p��pad Euklidovsk� varianty n�m za pomoci Delaunayovy trian�

gulace d� v�sledek lep��

���� Lemma� Minim�ln� pokr�vaj�c� strom T mno�iny n bod� existuje tak� �e v�echny jehohrany le�� v Delaunayov� triangulaci D dan� mno�iny�

D kaz� Nech* T je strom minim�ln� pokr�vaj�c� a ze v�ech takov�ch ten� kter� m� maxim�ln�po�et hran vD P�edpokl�dejme� �e v T je hrana �x� y�� kter� nele�� v D Potom V R�x�aV R�y�nemaj� spole�nou hranu Pak �podle lemmatu �� existuje z � S tak� �e V R�x� a V R�z� maj�spole�nou hranu a dist�x� z� � dist�x� y�� nav�c dist�y� z� � dist�x� y� Ob� hrany �y� z� a �x� z�nepat�� z�rove� do T � a bu)

T� �T f�x� y�g� � f�x� z�g�Jde o bro�urku� kterou pou��v� pi v�uce doc� Pol�k� Bohu�el nezn�m pesnj�� �daje� jako rok a m�sto

vyd�n�� proto se obra�te p�mo na pana docenta�

�� � VORON"HO DIAGRAMY

eee

e eeAA

A���

���JJJJJ

� �

��

��

Obr ��" Pr�chod kostrou p�i nav�t�ven� ka�d�ho uzlu alespo� jednou a ka�d� hrany pr�v�dvakr�t

nebo

T� �T f�x� y�g� � f�y� z�g

bude op�t pokr�vaj�c� strom T� m� men�� ocen�n� hran a T� m� sice men�� nebo rovn� ocen�n�hran jako T � ale m� zato v�ce hran z D V obou p��padech tedy nastane spor �

���� Vta� Minim�ln� Euklidovsk� pokr�vaj�c� strom kone n� mno�iny S � R� lze naj�t v aseO�n�� je�li d�na Delaunayova triangulace D�

D kaz� Podle p�edchoz�ho lemmatu sta�� diskutovat hrany D� co� je rovinn� graf� a ten m�line�rn� po�et hran �

Zn�mou aplikac� minim�ln� kostry je nalezen� jist�ho p�ibli�n�ho �e�en� pro probl�m ob�chodn�ho cestuj�c�ho v grafu

Probl�m obchodn�ho cestuj�c�ho spo��v� v nalezen� Hamiltonovsk� kru�nice �kru�nice pro�ch�zej�c� ka�d� vrchol pr�v� jednou�� kter� m� minim�ln� sou�et d�lek hranPohybujeme�li se pouze po minim�ln� kost�e a ka�dou hranu m��eme nav�t�vit pr�v� dva�

kr�t� lze proj�t v�emi vrcholy alespo� jednou a dostat se zp�tky do v�choz�ho vrcholu Naobr �� je nazna�en takov� pr�chod o��slov�n�m vrchol�� jak jsou postupn� nav�t�veny Dost��v�me tak cestu d�lky dvojn�sobn� oproti minim�ln� kost�e Ka�d� Hamiltonovsk� kru�nice� ita nejkrat��� kter� je k��en�m �e�en�m� m� o jednu hranu v�c ne� n�jak� kostra Tato kostra jev�ak del�� nebo rovna ne� minim�ln� kostra Celkem je dvojn�sobek minim�ln� kostry men�� ne�dvojn�sobek �e�en� probl�mu obchodn�ho cestuj�c�ho� a p�itom jsme v t�to d�lce mohli nav�t�vitv�echny uzlyV Euklidovsk�m prostoru m��eme p�i proch�zen� grafem p�esko�it ty uzly� kter� u� byly

nav�t�veny V�me toti�� �e takov� �zkratka� bude skute�n� krat�� Na obr �� tak dostanemekru�nici proch�zej�c� postupn� uzly �� � �� �� �� �� �� �

���� D�sledek� Pro Euklidovsk� probl�m obchodn�ho cestuj�c�ho lze naj�t v ase O�n log n��nebo v ase O�n�� je�li u� d�na Delaunayova triangulace p�ibl��en�� jeho� d�lka dosahujemaxim�ln� dvojn�sobku optima�

��� Dynamick� aktualizace Voron�ho diagramu ��

�� Dynamick� aktualizace Voron�ho diagramu

Mnoho skute�n�ch aplikac� m� dynamickou povahu� data se m�n� v �ase Abychom nemuselidatov� struktury v�dy cel� znovu po��tat i p�i mal� zm�n� dat� navrhujeme tzv dynamick�datov� struktury Jde vlastn� o n�vrh algoritm�� kter� umo��uj� efektivn� do struktury vlo�itprvek a vybrat z n� prvekUvedeme nyn� algoritmus pro p�id�n� prvku do Voron�ho diagramu a pop��eme algoritmus�

kter� by prvek z Voron�ho diagramu naopak vybralAlgoritmus p�id�n� prvku y do Voron�ho diagramu p�edpokl�d� znalost bodu x � S� v jeho�

Voron�ho oblasti V R�x� � V D�S� le�� bod y Probl�mem vyhled�n� takov� oblasti se budemezab�vat v kapitole � Najdeme sice algoritmus� kter� vyhled�v� v �ase O�log n�� nebudemev�ak schopni v takov�m �ase aktualizovat p��slu�nou vyhled�vac� strukturu V ka�d�m p��pad�se nab�z� line�rn� prohled�v�n� v�ech oblast�N�sleduj�c� popis algoritmu je mo�n� konfrontovat s obr�zkem ��Budeme postupovat po hranici Voron�ho oblasti nov� p�id�van�ho bodu y Nejprve najdeme

hranu� kter� le�� uvnit� V R�x� Tou bude osa �se�ky L�x� y� ohrani�en� oblast� V R�x� Pr�nikt�to osy s Voron�ho oblast� bodu x budou dva body fa� bg� kter� se jist� stanou vrcholy v nov�mVoron�ho diagramu Nech* nap� bod b le�� na hranici mezi V R�x� a V R�z� Pak bod b je stejn�vzd�len od bod� x� y� z� a uvnit� kru�nice t�mto t�em bod�m opsan� u� nele�� ��dn� dal�� bodz S � fyg� proto b bude vrcholem v�sledn�ho diagramuBodem z nyn� nahrad�me bod x Budeme tedy hledat pr�se��ky L�z� y� s Voron�ho oblast�

bodu z Jedn�m z nich bude jist� bod b� proto�e je st�edem kru�nice opsan� troj�heln�ku�xyzDruh� takov� bod v�ak ji� nemus� existovat� jako v ��sti b� obr�zku �� V tomto p��pad� jenutn� se vr�tit k v�choz�mu bodu x a postupovat opa�n�m sm�rem� tedy pomoc� vrcholu ak bodu r atd V p��pad�� �e kone�n� Voron�ho oblast bodu y bude ohrani�en� jako v ��sti a�obr�zku ��� nebude nutn� se vracet� proto�e se po hranici t�to oblasti dostaneme zp�tky dov�choz�ho bodu x

Algoritmus ��� P�id�n� prvku do Voron�ho diagramu

Vstup� Mno�ina S� jej� Voron�ho diagram V D�S�� bod y �� S� kter� m� b�t p�id�n do diagramu�a bod x � S takov�� �e y � V R�x�

V�stup� Vr�t� V D�S � fyg�� p " x

repeat

� fa� bg " pr�nik osy �se�ky L�p� y� s hranic� Voron�ho oblasti bodu p �a a b mohoub�t identick��

Najdi bod z takov�� kter� je sousedem bodu p ve V D�S� a na jeho� hranici le��n�kter� z bod� a� b� nav�c z jsme je�t� v tomto algoritmu nenav�t�vili �takov� bodnemus� existovat� nebo mohou b�t dva a mus�me jeden vybrat�

� p " z

� until Vr�t�me se zp�tky do v�choz�ho bodu x �tedy p x�� nebo nelze naj�t bod zv bodu

if Do bodu x jsme se v p�edchoz�m cyklu nevr�tili then

� Zopakuj p�edchoz� postup z bodu x opa�n�m sm�rem

� � VORON"HO DIAGRAMY

ee

e

ee

ux y

z

a

b

c

a�

b�

e

e

ee

u

z

x

r

y

a

b

Obr ��" Dynamick� aktualizace Voron�ho diagramu � p�id�n� bodu

��� Voron�ho diagramy vy���ch ��d� ��

Aktualizace prob�hne v �ase O�s�� kde s je po�et soused� bodu y I s vyhled�n�m v�choz�hobodu x tedy lze dos�hnout �asu O�s ! log n�

Algoritmus pro nalezen� V D�S n fyg�� tedy vypu�t�n� prvku z mno�iny S� spot�ebuje �asO�s log s�� kde s je po�et soused� bodu y ve Voron�ho diagramu Sta�� toti� vyhledat tyto sou�sedy a p�epo��tat Voron�ho diagram pouze pro n� Hranice jejich Voron�ho oblast� s ostatn�mibody z�stane nezm�n�na

��� Voron�ho diagramy vy�ch ��d�

Vra*me se k de�nici Voron�ho diagramu z podkapitoly � Pro ka�d� bod p roviny jsme hle�dali ten bod x z dan� kone�n� mno�iny bod� S� pro kter� je vzd�lenost dist�p� x� minim�ln�Vyb�r�me tedy tu jednoprvkovou podmno�inu S� ke kter� m� bod p nejbl��e Tento Voron�hodiagram ozna��me jako diagram prvn�ho �du

Voron�ho diagram druh�ho �du bude vych�zet z vyhled�n� dvouprvkov� podmmno�iny S�ke kter� m� bod p nejbl��e ze v�ech mo�n�ch dvouprvkov�ch podmno�in S Pro ka�dou dvou�prvkovou podmno�inu T � S pak ozna��me v�echny body� kter� byly takto p�i�azeny t�tomno�in�� jako Voron�ho oblast druh�ho �du mno�iny T N�sleduj�c� v�klad pracuje s obecn�m ��dem Voron�ho oblast� a diagram�

���� De�nice� Nech* S � R� je kone�n� mno�ina� T jej� podmno�ina Pak Voron�ho oblastpodmno�iny T mno�iny S de�nujeme takto"

V R�T � " fp � R� " �x � �S T � �y � T " dist�p� y� � dist�p� x�g

S takto de�novanou mno�inou bod� se nepracuje p��li� p�kn� Rad�ji si vyj�d��me ka�douVoron�ho oblast pomoc� jednodu���ch �tvar�

���� Vta�

V R�T � �xi�T

xj�S�T

Hi�j�

kde Hi�j fy% dist�xi� y� � dist�xj� y�g����� Pozn�mka� Mno�ina Hi�j z p�edch�zej�c� v�ty je polorovina� jej�� hrani�n� p��mkou jeosa �se�ky L�xi� xj� a kter� obsahuje bod xi

���� D�sledek�

�� V R�T � je v�dy konvexn� mnoho�heln�kov� oblast�

�� V R�T � m��e b�t i pr�zdn� mno�ina�

��� De�nice� Voron�ho diagram kt�ho �du V Dk�S� je rozd�len� roviny na Voron�ho oblastiV R�T � pro v�echny podmno�iny T mno�iny S� kter� obsahuj� pr�v� k prvk�

���� Pozn�mka� V D��S�� stejn� jako V Dn�S� pro jSj n jsou trivi�ln� diagramy s jedinouoblast�� a to celou rovinou V D��S� je nejjednodu��� p��pad Voron�ho diagramu ze za��tku t�tokapitoly

� � VORON"HO DIAGRAMY

Vrchol ve V Dk�S� se najde nap� takto" Zvol�me libovoln� t�i body x� y� z � S Pak st�edkru�nice prolo�en� t�mito body je vrcholem hranic ve V Dk�S�� kde k � je po�et bod� uvnit�t�to kru�nice �nepo��taje body x� y� z�Podrobn� popis v�ech vrchol� ve V Dk�S� je obsa�en v n�sleduj�c� v�t�� kter� z�rove� uka�

zuje zaj�mavou souvislost mezi vrcholy a hranami diagram� sousedn�ch ��d� T�m z�sk�meiterativn� konstrukci Voron�ho diagram� v�ech ��d�

���� Vta� Vrcholy hranic oblast� ve V Dk�S� se objev� pr�v� ve dvou Voron�ho diagramechV Dl�S�� V Dl���S�� krom� t�ch� kter� jsou pouze ve V Dn���S�% jSj n� Ka�d� vrchol� kter� seobjev� poprv� ve V Dl�S�� odpov�d� volb�

T� R � fxg� T� R � fyg� T R � fzg

pro jistou podmno�inu R � S� kter� m� l � prvk�� a body x� y� z � S nepat��c� do R �tentovrchol je st�edem kru�nice proch�zej�c� body x� y� z� Tent�� vrchol se pak objev� ve V Dl���S�jako vrchol odpov�daj�c�

T �� R � fy� zg� T �

� R � fx� zg� T � R � fx� yg�

p�i em� p�vodn� hrany ve V Dl�S� vych�zej�c� z tohoto vrcholu jsou v bijekci s hranami vych��zej�c�mi ze stejn�ho vrcholu ve V Dl���S�� jedn� se o opa n� polop��mky �viz obr� �)� Nav�c jeveSn��k � V Dk�S� O�n� vrchol��

D kaz� pou��v� slo�itou konstrukci Nejprve vlo��me rovinu xy do t��rozm�rn�ho prostoru �jed�na osami� tedy proch�z� bodem /�� �� �0� V tomto prostoru sestroj�me rota�n� paraboloid Pdan� rovnic�

P � z�x� y� x� ! y����

Paraboloid P se dot�k� roviny xy pr�v� v bod� /�� �� �0K prvk�m si � S sestroj�me body zi � P jako jejich kolm� projekce na paraboloid P

V ka�d�m zi uva�ujme te�nou rovinu �i k P Parametrizujeme�li �i body kolm� projekce doroviny xy� dostaneme"

p � R��xy� " �i�p� zi ! z��si��p si����

Nyn� si dok��eme n�sleduj�c� lemma"

���� Lemma� Body stejn� vzd�len� od si a sj jsou pr�v� pr�m�tem mno�iny �i � �jD kaz� Hled�me takov� body� pro kter� �i�p� �j�p� Nech* p �x� y�

x�i ! y�i ! xi�x xi� ! yi�y yi� x�j ! y�j ! xj�x xj� ! yj�y yj� x�i ! y�i xix yiy � ! x� ! y�

x�j ! y�j xjx yjy � ! x� ! y�

�x xi�� ! �y yi�� �x xj�� ! �y yj��

tedy vzd�lenost bodu p od bod� si� sj je shodn� �

��� Voron�ho diagramy vy���ch ��d� ��

D

x

s s s s2 3 4 5

z

z

zz

z

1

2

34

5

1s

3

Obr ��" Konstrukce Voron�ho diagram� vy���ch ��d� na p��mce

Pokra�ov�n� d�kazu v�ty �"Roviny �i d�l� R na oblasti D�� � � � �Dm Pro ka�d� bod si � S de�nujme Hi jako ten

poloprostor vymezen� �i� kter� neobsahuje paraboloid P Pro ka�dou rovinu �i mohou nastatve vztahu ke konkr�tn� oblasti D dva p��pady"� Oblast D le�� cel� v Hi �tedy le�� v jin�m poloprostoru ohrani�en�m pii ne� paraboloid P �

Oblast D nele�� v Hi �a le�� ve stejn�m poloprostoru jako P �Obr�zek �� ilustruje situaci v rovin� M�sto paraboloidu zde m�me parabolu a k n� te�n�

p��mkyHi zde bude v�dy ta polorovina� kter� neobsahuje parabolu a jej�� d�lic� p��mka odpov��d� t� te�n� k parabole� jej�� bod dotyku je kolmou projekc� bodu xi z osy x �kter� korespondujes prostorem� ve kter�m hled�me Voron�ho diagramy� na paraboluKe ka�d� oblasti D m��eme de�novat mno�inu T �D� � S t�ch si� pro n�� je D � Hi Nyn�

dok��eme� �e pr�m�t oblasti D zp�t na rovinu xy n�m d� pr�v� Voron�ho oblast mno�iny T �D�Nech* q� � D a q je projekce q� do roviny xy Vezmeme nyn� v �vahu ka�dou dvojici bod�

si� sj � S takovou� �e si � T �D� a sj �� T �D� Pak q� � Hi� q� �� Hj Podle lemmatu �

�� � VORON"HO DIAGRAMY

mus� tedy b�t pr�m�t q� bl��e bodu si ne� sj To ale znamen�� �e q � Hi�j Odtud plyne podlev�ty � �e q � V R�T �D��Nyn� mus�me je�t� dok�zat� �e nen��li bod q pr�m�tem ��dn�ho prvku oblasti D� pak nen�

prvkem V R�T �D�� K tomu budeme pot�ebovat je�t� jedno lemma"

���� Lemma� Pro libovoln� �slo � � k � n a pro ka�d� bod q v rovin� xy lze naj�t bod q�

takov�� �e q� je prvkem n�jak� oblasti D� jej�� mno�ina T �D� m� pr�v� k prvk�� a q je kolm�mpr�m�tem q� na rovinu xy�

D kaz� V bod� q vzty��me kolmici l na rovinu xy Jej� pr�se��k s paraboloidem P ozna��me q�Tento bod le�� v oblasti D�� pro ni� plat�� �e T �D�� � Tato oblast �obsahuj�c� cel� parabo�loid P � je toti� v��i v�em rovin�m �i v poloprostoru obsahuj�c�m P � a tedy nen� v ��dn�m Hi4�dn� rovina �i nen� kolm� na rovinu xy� proto p��mka l protne postupn� v�echny tyto rovinyBudeme�li p��mku l trasovat od bodu q� dol�� p�i ka�d�m protnut� s rovinou �i se dostanemedo poloprostoru Hi T�m se dostaneme do oblasti D� kter� m� o jeden v�ce bod� ve sv� mno�i�n� T �D� ne� p�edch�zej�c� Po protnut� v�ech n rovin tak z�sk�me pro ka�d� ��slo k odpov�daj�c�vzor pr�m�tu q� �

D�ky tomuto lemmatu m��eme dokon�it d�kaz v�ty �Nen��li tedy bod q v rovin� xy pr�m�tem ��dn�ho bodu oblasti D� je jist� pr�m�tem jin�ho

bodu q� oblasti D� takov�� �e T �D� a T �D�� maj� stejn� po�et prvk� Bod q je tedy prvkemV R�T �D���� a nem��e b�t z�rove� prvkem V R�T �D��

si � T �D� jsou pr�v� body ur�uj�c� V R�T �D�� a pat�� do V DjT �D�j�S�Vezm�me libovoln� vrchol v Voron�ho diagramu libovoln�ho ��du V�me� �e mus� b�t pr��

m�tem vrcholu n�kter� oblasti D podle p�edchoz�ch �vah Tedy pouze vrcholy t�chto oblast� semohou st�t vrcholy Voron�ho diagramuNech* v� je vrchol v rozd�len� prostoru rovinami �i Pak v� je pr�nikem t�� rovin �zde

zanedb�me p��pad� kdy se �ty�i takov� roviny prot�naj� v jednom bod� � �ty�i body mno�iny Sle�� na kru�nici� Dost�v�me tedy trs t�� rovin� kter� rozd�luj� prostor na osm oblast� Nav�c��dn� z rovin nen� kolm� na rovinu xy Dv� z t�chto osmi oblast� budou obsahovat po prom�tnut�do roviny xy bod v� uvnit� sebe Nazveme je �horn��� resp �doln�� oblast a ozna��me Dh�resp Dd Mno�inu T �Dh� ozna��me jako R� po�et jej�ch prvk� nech* je l � Body odpov�daj�c�jednotliv�m rovin�m ozna��me x� y� z Je z�ejm�� �e T �Dd� T �Dh� � fx� y� zgZb�vaj�c�ch �est oblast� tvo�� dv� sdru�en� trojice Do oblast� �vy���ch� se dostaneme z horn�

oblasti tak� �e p�ekro��me pr�v� jednu ze t�� rovin� kter� ji ohrani�uj� Po prom�tnut� t�chtooblast� �p��padn� ohrani�en�ch dal��mi rovinami� dostaneme Voron�ho oblasti mno�in R�fxg�R � fyg a R � fzg� podle toho� kterou rovinu jsme p�ekro�ili Obraz v bodu v� po prom�tnut�bude vrcholem takov�ch Voron�ho oblast�� tedy vrcholem ��du lAnalogicky z�sk�me z doln� oblasti t�i �ni���� oblasti� kter� po prom�tnut� odpov�daj� Vo�

ron�ho oblastem mno�in R � fx� yg� R � fy� zg a R � fx� zg Tyto t�i oblast maj� tak� jedenz vrchol� bod v Bod v se tedy opakuje jako vrchol ��du l ! �Celkem dost�v�me� �e ka�d� vrchol bude v pr�m�tu jednou ve V Dl�S� a jednou ve V Dl���S�

s v�jimkou t�ch� kter� se objev� poprv� ve V Dn���S�Ka�d� vrchol Voron�ho diagramu je d�n trojic� bod� vybran�ch z mno�iny S� jejich� odpo�

v�daj�c� roviny se prot�naj� ve vzoru pro tento vrchol Takov�ch pr�se��k� rovin najdeme

�n�

��

co� je O�n� �

��� Voron�ho diagramy vy���ch ��d� ��

S pomoc� pr�v� dok�zan� v�ty se lze pustit do konstrukce Voron�ho diagram� vy���ch ��d�

Algoritmus ��� Nalezen� Voron�ho diagramu libovoln�ho ��du

Vstup� Mno�ina bod� v rovin� S a po�adovan� ��d diagramu k � jSjV�stup� V Dk�S�

� Setroj�me V D��S� a v�echny jeho vrcholy hranic ozna��me jako vrcholy typu I

for j � to k � doP�vodn� vrcholy typu I z�st�vaj� a ozna��me je jako vrcholy typu II P�vodn� vrcholy typuII zmiz� Ten� kter� odpov�dal volb� T �

� R � fy� zg� T �� R � fx� zg� T �

R � fx� yg� sestane vnit�n�m bodem oblasti odpov�daj�c� mno�in� R � fx� y� zgP�vodn� oblasti V Rj�T � pot�ebujeme rozd�lit na ��sti p��slu�ej�c� oblastem V Rj���T �fxg�� kde x � S n T Toto rozd�len� provedeme konstrukc� V D��S n T � provedenou pouzena ��zem�� oblasti V Rj�T � Potom oblast V R��x� v diagramu V D��S n T � v pr�nikus p�vodn� oblast� V Rj�T � d�v� oblast V Rj���T � fxg� Voron�ho diagramu ��du j ! �P�i konstrukci diagramu V D��S nT � sta�� p�itom uva�ovat body S nT soused�c� s vrcholytypu I na hranici oblasti V Rj�T �

Zjednodu�en� se d� tato konstrukce popsat tak� takto" Vezmeme v �vahu ka�d� vrchol vtypu I Ten je pr�se��kem t�� �se�ek �nebo polop��mek�� kter� jsou osami �se�ek� spojuj�c�v�dy n�jakou dvojici bod� mno�iny S Na obr�zku � jsou tyto hrany souvisl� ��ry Mytyto ��ry ve vrcholu v �obr�t�me�� ��m� vzniknou hrany Voron�ho diagramu vy���ho ��du�na obr�zku vyzna�en� p�eru�ovan� Vrchol v z�stane nad�le vrcholemVoron�ho diagramu�ale stane se vrcholem typu II

Vznikl� obr�cen� hrany se mohou prot�nat Najdeme�li takov� pr�se��k� ozna��me ho jakovrchol typu I a ob� hrany do n�ho sm��uj�c� ukon��me Tyto hrany budou osami �se�ekL�x� y� a L�x� z� pro n�jak� t�i body x� y� z � S Nech* si �ten�� rozmysl�� pro� tomu takje Z uva�ovan�ho vrcholu nyn� vypust�me novou hranu Voron�ho diagramu� kter� je osou�se�ky L�y� z�� orientovanou tak� aby le�ela ve v�t��m �hlu sv�ran�m p�vodn�mi hranamiNa obr�zku � jsou p�vodn� hrany nakresleny pln�mi ��rami a nov� hrana p�eru�ovan�

�asov slo�itost� Sestrojen� diagramu V D��S� zabere O�n log n� �asu P�echod od diagramuV Dj�S� k diagramu V Dj���S� zabere �as O�s log s�� kde s je po�et vrchol� typu ILze uk�zat� �e s pro V Dk�S� je nejv��e

k�N �� k�N �� Pki � neomezen�ch oblast� V Di�S�

���� Tvrzen�� Voron�ho diagram ��du k� V Dk�S�� jSj n lze z�skat v ase O�k�n log n��V�echny V Dk�S� lze takto z�skat v ase O�n log n��

���� Pozn�mka� Optim�ln� �as pro nalezen� Voron�ho diagram� v�ech ��d� je O�n� Lze hodos�hnout p��m�m v�po�tem vrchol� pomoc� konstrukce s paraboloidem� kter� byla pou�itav d�kazu v�ty � V�ech t�chto bod� je O�n� a algoritmus je m��e po��tat p��mo analytickypro v�echny mo�n� trojice rovin

Probl�m nejbli���ch soused� lze zobecnit pro libovoln� ��d� stejn� jako Voron�ho diagramyVe vy���ch ��dech v�ak budeme uva�ovat pouze dotazovou variantu probl�mu k nejbli���chsoused� z podkapitoly �

�� � VORON"HO DIAGRAMY

eI�II

Obr �" Obr�cen� polop��mek ve vrcholu typu I p�i konstrukci Voron�ho diagramu vy���ho ��du

ee

ez

x

y

I

Obr �" Nalezen� nov�ho vrcholu typu I jako pr�se��ku hran

��� Voron�ho diagramy ve vy���ch dimenz�ch ��

Probl�m M�me�li d�nu mno�inu bod� S� ��slo k a libovoln� bod v rovin� x� najdi t�ch kbod� mno�iny S� kter� jsou bodu x nejbl��eProbl�m lze �e�it p�edspo��t�n�m Voron�ho diagramu dan�ho ��du nebo v�ech ��d�� a n��

sledn�m vyhled�n�m v takov�m rovinn�m rozd�len� Jak uvid�me v kapitole � � lze v rovinn�chrozd�len�ch vyhled�vat v logaritmick�m �ase

���� D�sledek� Probl�m k nejbli���ch soused� lze �e�it v ase O�log n ! k� s p�edp��pravouO�k�n log n��

Na z�v�r pov�d�n� o Voron�ho diagramech vy���ch ��d� uvedemen�kolik pozn�mek k dualit�Voron�ho oblast mno�iny T � jak jsme ji de�novali� je mno�ina v�ech bod�� kter� jsou bl��e v�embod�mmno�iny T ne� libovoln�mubodu mno�iny SnT To ale znamen�� �e je to oblast takov�chbod�� kter� jsou d�le v�em bod�m mno�iny S n T ne� libovoln�mu bodu mno�iny T Probl�mnejvzd�len�j��ch soused� je tedy du�ln� k probl�mu nejbli���ch soused� a d� se na n�ho p�ev�stHled�me�li toti� k nejvzd�len�j��ch soused� bodu x mezi body mno�iny S� vyhled�me oblastV Rn�k�T � v diagramu V Dn�k�S� a v�sledkem je mno�ina S n T Zejm�na diagram V Dn���S�lze pou��t p�i hled�n� nejvzd�len�j��ho souseda

���� D�sledek� Probl�m k nejvzd�len�j��ch soused� lze �e�it v ase O�log n!�n k�� s p�ed�p��pravou O��n k��n log n��

Je tedy Voron�ho diagram V Dn���S� du�ln� k V D��S� Vezmeme�li polorovinyHi�j z lemma�tu de�novan�

Hi�j " fy � R� j dist�xi� y� � dist�xj� y�gpro ka�dou dvojici bod� xi� xj � S a z nich dostaneme Voron�ho oblast prvn�ho ��du jakoV R�xi�

Ti� j Hi�j� lze du�ln� de�novat opa�n� poloroviny

Hi�j " fy � R� j dist�xi� y� � dist�xj� y�g

a potom analogicky plat� V Rn���xi� Ti� j Hi�j

� Ve v�sledn�mVoron�ho diagramu ��du �n ��budou v�ak existovat oblasti pouze pro body na konvexn�m obalu cel� mno�iny S� co� si m��e�ten�� dok�zat jako cvi�en�

��� Voron�ho diagramy ve vy�ch dimenz�ch

Posledn� mo�nost� roz���en� Voron�ho diagram�� kterou se budeme zab�vat� je zv�t�en� dimenzena�eho prostoru Jak d�le uvid�me� s dimenz� roste rychle slo�itost Voron�ho diagramuU� v dimenzi d � m��e m�t Voron�ho diagram V D��S�� jSj n a� O�n�� hrani�n�ch st�n

Nap� /Preparata���0 uv�d� n�sleduj�c� p��klad"

���� P��klad� M�jme mno�inu n bod� v prostoru se sud�m po�tem prvk� n Nech* polovinaz nich je rozm�st�na na ose z a druh� polovina na kru�nici le��c� v rovin� xy se st�edem v bod�/�� �� �0 Voron�ho oblasti pat�i�n� k bod�m na kru�nici maj� za sousedy v�echny oblasti bod�na p��mce a naopak Celkem je tedy O�n�� hran v�sledn�ho diagramu� p�esto�e m�O�n� oblast�

#asy dosa�en� v rovin� tedy v prostoru nutn� selh�vaj�Nazna��me nyn� postup konstrukce Voron�ho diagramu v prostoru Ud�l�me to tak� �e

pop��eme konstrukci v rovin� s t�m� �e jej� roz�i�itelnost o jednu dimenzi bude intuitivn� jasn�

�Zejm zde plat� vztah Hi�j � Hj�i� Pro lep�� ilustraci duality v�ak uv�d�me tuto notaci�

� � VORON"HO DIAGRAMY

Takov� postup vol�me proto� �e je p�i konstrukci nutno pracovat v prostoru o dimenzi vy���m ne�je prostor v�sledn�ho diagramu V�echny n�sleduj�c� �vahy tedy povedou k diagramu v rovin�Konstrukce bude prob�hat tak� �e rovinu vlo��me do prostoru jako rovinu rovnob��nou

s rovinou xy na �rovni z � Pomoc� zobrazen� inverze vzhledem ke sf��e prom�tneme v�echnymno�iny S z t�to roviny na sf�ru Potom dok��eme �zkou souvislost mezi Voron�ho diagramemp�vodn� mno�iny a konvexn�m obalem obraz� bod� t�to mno�inyBody v prostoru bude pot�eba vlo�it do �ty�rozm�rn�ho prostoru a zde naj�t konvexn� obal

jejich obraz� v inverzi V�echny tyto operace um�me analyticky prov�st� p�esto�e si je neum�mep�edstavit��� De�nice� Pro p /x� y� z0 zna��me jpj p

x� ! y� ! z� Funkce � " R � R de�novan�

�p � R " ��p� p

jpj�se naz�v� inverze vzhledem ke sf��e

k � x� ! y� ! z� �

���� Pozn�mka� Koule k je v inverzi z p�edchoz� de�nice pr�v� mno�inou samodru�n�chbod�

���� Vta� Roviny a sf�ry jsou v inverzi vzhledem ke sf��e k zobrazeny na roviny nebo sf�ry�

D kaz� Uva�ujme sf�ru se st�edem s a polom�rem r Pak jej� rovnice je

jp sj� r�

� �x�p� x�s��� ! �y�p� y�s����

Pro jsj � r uva�me p� ��p�jx yj� �x y� x y�

jp� s

jsj� r�j�

�jpj� !

jsj��jsj� r��

psjpj��jsj� r��

r�

�jsj� r���

Je tedy ��sf�ry� sf�ra se st�edem s� sjsj��r� a polom�rem

jrjjsj��r� j

Jestli�e st�ed s zvol�me pevn� a r � jsj� pak s� �ut�k�� po polop��mce �s do nekone�na�proto obrazem limitn� sf�ry proch�zej�c� po��tkem bude rovina kolm� na �sV�me� �e slo�en� dvou inverz� po sob� d�v� identitu

� � � id

Vezmeme�li tedy v�echny sf�ry proch�zej�c� po��tkem� jsou jejich obrazy v�echny mo�n� ro�viny po��tkem neproch�zej�c� Po aplikaci stejn� inverze zobraz�me tedy tyto roviny na sf�ryproch�zej�c� po��tkemRoviny po��tkem proch�zej�c� se zobraz� samy na sebeCelkem tedy se ka�d� sf�ra zobraz� na sf�ru nebo rovinu� a ka�d� rovina se zobraz� na rovinu

nebo sf�ru �

��� Voron�ho diagramy ve vy���ch dimenz�ch �

0

x

p p p p p

z

zz

z

z

1 2 3 4 5

1

2

3

4

5

3

Obr " Ilustrace kruhov� inverze v dimenzi

� VORON"HO DIAGRAMY

Uva�me rovinu � z �� kter� je te�n� ke sf��e k v bod� ��� �� �� Jej� obraz je sf�rase st�edem s ��� �� �� � a polom�rem �� Uva�me body pi � � i �� � � � � n �mno�inaS� Ozna�me zi ��pi� � �� �� S� fz�� � � � � zng Konvexn� obal BCH�S�� rozd�l�me nadisjunktn� ��sti C� � body viditeln� z po��tku O a C� � neviditeln� p�es BCH Proto�e ��dn��ty�i body v S nele�� na kru�nici� jsou v BCH�S�� sam� troj�heln�ky� Nech* F je neviditeln� st�na v BCH�S�� �tj aspo� jeden bod zi � C�� Pak rovina zadan�vrcholy zi� zj� zk � F se zobraz� na sf�ru kF Na vnit�ek kF se zobraz� ve � poloprostorneobsahuj�c� po��tek a odd�len� rovinou F Odtud plyne� �e vnit�ek kF neobsahuje ��dn�body S Proto st�ed kru�nice� kter� je pr�nikem sf�ry kF s rovinou �� je vrchol V D��S�

Nech* F je viditeln� st�na v BCH�S�� Pak ze stejn�ho d�vodu bude kF proch�zet bodypi� pj� pk a uvnit� budou v�echny body S Proto st�ed kru�nice kF �� je vrchol V Dn���S�

V��e uveden� algoritmus lze zobecnit pro v�echny dimenze d � �Konvexn� obaly v Rd pro d � um�me naj�t v �ase O�nbd��c��� ! O�nbd��c log n�� pro R

speci�ln� v �ase O�n log n� Viz pozn�mka � � a algoritmus typu rozd�l a panuj v RNav�c mus�me rozd�lit vrcholy v BCH�S�� na C�� C� podle �viditelnosti� z po��tku Prak�

ticky test provedeme snadno v�po�tem orientovan�ho objemu p��slu�n�ho rovnob��nost�nu���� Pozn�mka� Z konstrukce V Dn���S� plyne� �e nepr�zdn� oblasti p��slu�� �v interpretacinejvzd�len�j��ch bod�� pr�v� bod�m na hranici konvexn�ho obalu �BCH�S��

��� D�ry a pokryt�

Kr�tce se zm�n�me o sad� probl�m� souvisej�c�ch s Voron�ho diagramy� kter� se daj� souhrnn�ozna�it jako d�ry a pokryt����� De�nice� D�rou pro S � R� rozum�me kruh neobsahuj�c� ��dn� bod mno�iny S

Pokryt� je mno�ina kruh� pokr�vaj�c�ch spole�n� celou mno�inu SBudeme se zab�vat pouze dv�ma probl�my Mo�nost� je v�ak v�ce� z�jemce odkazujeme na/Preparata���0

Probl�my� Najdi nejv�t�� d�ru pro mno�inu S� jej�� st�ed le�� uvnit� konvexn�ho obalu mno�iny S�nejv�t�� pr�zdn� kruh � viz obr�zek ��

Najdi nejmen�� pokryt� mno�iny S skl�daj�c� se z jedin�ho kruhu �nejmen�� pokr�vaj�c�kruh � viz obr�zek �

Na obou ilustrac�ch jsou body� kter� ur�uj� v�sledn� kruh� vyzna�eny pln�m krou�kem� ostatn�body mno�iny pr�zdn�m krou�kem

���� Pozn�mka� Nejmen�� pokr�vaj�c� kruh je jednozna�n� ur�en a bu) proch�z� t�emi bodyz S nebo jeho pr�m�r je pr�m�rem S Ob� mo�nosti ukazuje obr�zek Probl�m nejv�t��ho pr�zdn�ho kruhu je zn�m v opera�n�m v�zkumu jakoMinimum Facilities

Location ProblemProbl�m je du�ln� k � Oba byly studov�ny od roku ���� a je�t� v ��t�ch letech tohoto

stolet� s v�sledky� Nejv�t�� pr�zdn� kruh" O�n��

Nejmen�� pokr�vaj�c� kruh" O�n�

��� D�ry a pokryt� �

Obr �" Nejv�t�� pr�zdn� kruh

3

Obr " Dv� mo�nosti pro nejmen�� pokr�vaj�c� kruh

TRIANGULACE A VYHLED*V*N� V ROVINN+CH ROZD,LEN�CH

S pomoc� Voron�ho diagram� dos�hneme pro oba probl�my n�sleduj�c�ch �as����� Vta� V obou p��padech obsahuje vstupn� mno�ina S n bod��

�� Nejmen�� kruh pokr�vaj�c� S lze sestrojit v ase O�n log n�

�� Nejv�t�� pr�zdn� kruh se st�edem uvnit� CH�S� lze z�skat v ase O�n log n�

D kaz� Nejmen�� pokr�vaj�c� kruh� Pokud kruh proch�z� t�emi body z S� pak jeho st�ed jevrcholem V Dn���S� Takov�ch vrchol� je line�rn� mnoho Nech* kruh �realizuje� pr�m�r SPak jeho st�ed je na ose �se�ky L�xi� xj� #�st t�to osy mus� b�t hranou ve V Dn���S� Tedy sta��proj�t hrany V Dn���S� a hledat nejvzd�len�j�� dvojici bod� z S odpov�daj�c� t�mto hran�m

Nejv�t�� przdn� kruh� V tomto p��pad� je st�ed kruhu nutn� vrcholem V D��S� nebo n��kter�m z nov� vznikl�ch vrchol� V D��S� � BCH�S� My v�ak v�me� �e

� ka�d� hrana V D��S� prot�n� nejv��e dv� hrany BCH�S�

� ka�d� hrana BCH�S� protne alespo� jednu hranu V D��S�Ka�dou hranu V D��S� projdeme nejv��e dvakr�t a najdeme v�echny pr�niky v �ase O�N�V line�rn�m �ase tak� najdeme v�echny vrcholy V D��S� Nejv�ce �asu tedy zabere sestrojen�V D��S� a BCH�S�� co� lze oboje v �ase O�n log n� �

���� Pozn�mka� Pan Megiddo �/Megiddo���0� vylep�il hled�n� nejv�t��ho pr�zdn�ho kruhutak� �e prohl��� a konstruuje jen ��st V Dn���S� a jeho algoritmus pracuje v optim�ln�m �a�se 1�n�

� Triangulace a vyhled�v�n� v rovinn�ch rozdlen�ch

V t�to kapitole se budeme zab�vat nejprve triangulac� mno�iny bod� v rovin� Z�sk�me takrozd�len� roviny na troj�heln�kov� oblastiBudeme d�le po�adovat� abychom v takto vytvo�en� struktu�e mohli efektivn� vyhled�vat�

tedy pro dan� bod zjistit� v kter� ��sti triangulace le�� Tuto �lohu� zvanou vyhledvn� v rovinn�ch rozd�len�ch� zobecn�me na d�len� roviny na mnoho�heln�kov� oblasti� a tak z�sk�mez�rove� algoritmy na vyhled�v�n� ve Voron�ho diagramech uveden�ch v p�edchoz� kapitole

��� Triangulace

B��nou �lohou v mnoha geometrick�ch aplikac�ch je nalezen� triangulace mno�iny bod� v ro�vin� Jde o vytvo�en� s�t� troj�heln�k�� kter� se nep�ekr�vaj� a p�itom pokr�vaj� cel� vnit�ekkonvexn�ho obalu dan� mno�iny P�itom vrcholy troj�heln�k� maj� b�t identick� s body vstupn�mno�iny Jin�mi slovy� hled�me rovinn� graf s vrcholy identick�mi s body dan� mno�iny� p�i��em� st�ny tohoto grafu maj� b�t troj�heln�ky Obr�zek � ukazuje p��klad takov� triangulaceV p�edchoz� kapitole jsme pomoc� Voron�ho diagramu nalezli tzv Delaunayovu triangulaci

�viz de�nice � n�sleduj�c� v�ta a obr�zek ��� Nau�ili jsme se ji tak� konstruovat v �aseO�n log n�Pro danou mno�inu bod� v�ak jist� existuje mnoho triangulac� Proto se �asto na triangu�

la�n� algoritmy aplikuj� r�zn� po�adavkyB��n� po�adavky na triangulaci"� minimalizovat v�hy hran �nap� d�lky�Nen� zn�mo� zda existuje polynomi�ln� algoritmus

�� Triangulace �

e

e e e

eeee

ee

Obr �" Triangulace bod� v rovin�

� minimalizovat �hly troj�heln�k�Nen� zn�mo� zda existuje polynomi�ln� algoritmus

� m�me p�edem zad�nu mno�inu �povinn�ch� hran v triangulaciUvedeme dva algoritmy

Je dok�z�no� �e Delaunayova triangulace minimalizuje maxima �hl� v troj�heln�c�ch Krom�toho m� tato triangulace dal�� p��jemnou vlastnost" uvnit� kru�nice opsan� ka�d�mu jej�mutroj�heln�ku nele�� ji� ��dn� dal�� vrchol triangulaceNaivn� implementace triangulace �tzv hladov�"

Algoritmus ��� Hladov� triangulace �Gready Triangulation�

�n

�mo�n�ch hran uspo��d�me dle velikosti do z�sobn�ku

repeat odeber aktu�ln� �resp nejkrat��� hranu v ze z�sobn�ku a testujeme kompatibilitu�nap� k���en� hran� v T � fvg

� until je dosa�en pot�ebn� po�et hran nebo z�sobn�k je pr�zdn�

#asov� slo�itost"� O�n� log n�

Je�li ��m� doba pot�ebn� pro test kompatibility grafu om vrcholech� pak �as jeO�n���n��

Testujeme�li protnut� nov� p�id�van� hrany se v�emi hranami u� v triangulaci obsa�en�mi�je ��n� O�n� a tedy celkov� �as O�n�

Lep�� test kompatibility� kter� pracuje v �ase O�log n�� byl navr�en v /Gilbert���0� a je uvedentak� v /Preparata���0 P�itom nedojde ke zv��en� pam�*ov�ch n�rok� My zde uvedeme pouzev�sledek��� Tvrzen� Gilbertovo Hladov� triangulace pro n bod� v rovin� se d� prov�st v aseO�n� log n� a prostoru O�n���

��� Pozn�mka� Hladov� triangulace ne�e�� optim�lnost hran M��e v�ak zahrnout p�edemzadanou mno�inu hran povinn�ch

Hladov� triangulace n�s co do �asov� slo�itosti nem��e uspokojit Uvedeme d�le algoritmuslep��� kter� se d� nazvat triangulace pomoc� monot�nn�ch �et�zc

� TRIANGULACE A VYHLED*V*N� V ROVINN+CH ROZD,LEN�CH

ee e e

eeee

Obr �" Monot(nn� �pln� mno�ina �et�zc�

Princip spo��v� v rozd�len� �lohy na postupn� triangulov�n� jednodu���ch oblast� Pro S �R�� jSj n� chceme triangulaci konvexn�ho obalu mno�iny S Rozd�l�me si jej tedy na tzvmonot�nn� polygony a provedeme jejich triangulaci

��� De�nice� Polygon P se naz�v� monot�nn� vzhledem k p��mce l� je�li jednoduch� a jesjednocen�m dvou monot(nn�ch �et�zc� vzhledemk l �tzn pr�m�ty vrchol� na l tvo�� monot(nn�posloupnost�

Nejprve sestroj�me algoritmus na rozd�len� CH�S� na monot(nn� polygony s vrcholy v SKonstruujeme posloupnost monot(nn�ch �et�zc� s vlastnostmi

� �et�zce obsahuj� v�echny body S a v�echny zadan� hrany

pro ka�d� �et�zce Pi� Pj plat�� �e v�echny vrcholy Pj� kter� nepat�� do Pi� le�� na stejn�stran� od Pi

��� De�nice� Syst�m �et�zc� v��e popsan� naz�v�memonot�nn� �pln mno�ina �et�zc �prorovinn� graf G�

P��klad monot(nn� �pln� mno�iny �et�zc� je na obr�zku �

�� De�nice� Nech* G je rovinn� p��mo�ar� graf s vrcholy VG fv�� � � � � vng uspo��dan�milexikogra�cky podle /y� x0 Vrchol vj v G nazveme regulrn�� pokud existuje i � j � k tak� �ehrany �vi� vj� a �vj� vk� pat�� do G Graf G nazveme regulrn�� je�li ka�d� vrchol vj� � � j � nregul�rn� Hrany �vi� vj�� i � j� ozna�ujeme jako vstupn� pro vj �� IN�vj��� resp v�stupn� provi �� OUT �vi��P�edpokl�dejme� �e v G m�me vybr�ny monot(nn� �et�zce spojuj�c� vn s v� a ozna�me w�e�

jako po�et �et�zc�� ve kter�ch hrana e le�� �v�ha e� Klademe

WIN�v� " X

e�IN�v�

w�e�

WOUT�v� " X

e�OUT�v�

w�e�

�� Triangulace �

��� Pozn�mka� Pokud m�me naopak zad�ny v�hy hran vznikl� z mno�iny �et�zc�� um�mesestrojit n�jakou mno�inu �et�zc� kompatibiln� s vahami Pokud syst�m byl �pln�� op�t z�sk�me�pln� syst�m Postupn� z vn tvo��me cesty do v� tak� �e z uspo��dan�ch mno�in IN�vi� �podlehodinov�ch ru�i�ek� zvol�me posledn� jako n�sleduj�c� hranu cesty a sn���me jej� v�hu o �D�ky regul�rnosti G um�me pro ka�d� vrchol v � G naj�t monot(nn� �et�zec proch�zej�c� v

Tomuto algoritmu budeme ��kat balancovn� vah� proto�e najdeme v�hy pro n�jakou �plnoumno�inu �et�zc�� z nich� se daj� podle p�edchoz�ho bodu tyto �et�zce zkonstruovat v line�rn�m�asePot�ebujeme �p�elo�it� vlastnosti monot(nn� �pln� mno�iny �et�zc� do �jazyka vah� N�sle�

duj�c� vlastnosti vah n�m zaru��� �e v�hy budou popisovat n�jakou monot(nn� �plnou mno�inu�et�zc�� w�e� � �

� � � ��k�� �e ka�d� hrana i ka�d� vrchol se objev� v mno�in� �et�zc� ��plnost�

�vj � G� � � j � n " WIN�vj� WOUT�vj�

� � � zaji�*uje� �e p�jde o monot(nn� �et�zce� tedy kolik jich do vrcholu vstoup� �zespodu��tolik jich bude pokra�ovat �v��e�

N�sleduje algoritmus� kter� v regul�rn�m grafu spo��t� takov� v�hy� kter� budou reprezentac�n�jak� monot(nn� �pln� mno�iny �et�zc�Algoritmus ��� Balancov�n� vah

Vstup� Regul�rn� graf GV�stup� V�hy W hran� kter� reprezentuj� n�jakou monot(nn� �plnou mno�inu �et�zc�

� for v�echny hrany e do W �e� " �

for i " to n � do � WIN �vi� "

Pe�IN�vi�W �e�

d " prvn� v�stupn� hrana v OUT �vi� � if WIN�vi� � jOUT �vi�j then �� W �d� " WIN�vi� jOUT �vi�j! �

� for i " n � to do�� WOUT �vi� "

Pe�OUT�vi�W �e�

� d " posledn� vstupn� hrana v IN�vi��� if WOUT�vi� � WIN�vi� then��� W �d� " WOUT�vi� WIN�vi� !W �d�

Spot�ebujeme line�rn� mno�stv� pam�ti #as je tak� line�rn�� proto�e proch�z�me dvakr�t v�e�chny vrcholy �krom� v� a vn�� p�i�em� akce proveden� v ka�d�m pr�chodu je konstantn�Uvedli jsme algoritmus na nalezen� mno�iny �et�zc� regul�rn�ho grafu Budeme v�ak na

celkov�m algoritmu po�adovat� aby pracoval s libovoln� zadanou mno�inou povinn�ch hranTento ne�pln� graf je t�eba nejprve regularizovat� abychom mohli v��e uveden� algoritmusaplikovatRegularizaci grafu provedeme metodou pro�esvn�� kter� ji� byla zm�n�na v kapitole

Metoda pro�es�v�n� �sweep� pot�ebuje n�sleduj�c� pam�*ov� struktury"

� TRIANGULACE A VYHLED*V*N� V ROVINN+CH ROZD,LEN�CH

e e e

e pro5ces+avac+,

p5r+,mky

OUT �vi�

IN�vi�vi

vj vk vl

Obr �" Regularizace grafu � pro�es�vac� algoritmus

� �vertik�ln�� struktura pro zachycen� ud�lost� pro n�s v�znamn�ch� � �uspo��dan� vrcholy od shora dol� �za p�edpokladu� �e ��dn� dva z nich nemaj� shodnouy�ovou sou�adnici�

� �horizont�ln�� struktura pro zachycen� statutu pro�esvac� p��mky

� � � seznam pr�se��k� p��mky uspo��dan� zleva doprava a ka�d�mu intervalu na p��mcep�i�ad�me vrchol s nejni��� y�ovou sou�adnic� �nad n�m�

P�i pr�chodu shora dol� zajist�me� aby z ka�d�ho vrcholu vedla alespo� jedna hrana �nahoru��nebo�li OUT �vi� � � Analogicky po pr�chodu zdola nahoru povede z ka�d�ho vrcholu alespo�jedna hrana �dol�� Obr�zek � ilustruje pr�chod shora dol� a t�i pozice pro�es�vac� p��mky�kter� je v�dy horizont�ln� Na t�to p��mce budou v�dy intervaly s tzv p�i�azen�m vrcholem�s nejni��� y�ovou sou�adnic� nad t�mto intervalem� Pro�es�vac� p��mka v nejvy��� pozici jerozd�lena na p�t interval� U t�� prost�edn�ch je nazna�en vrchol� kter� je jim p�i�azen� V pro�st�edn� pozici proch�z� pro�es�vac� p��mka vrcholem� m�n� se zde jej� stav Intervaly pod bodyvj� vk jsou nejprve vylou�eny dle mno�iny hran OUT �vi� Pot� je vlo�en nov� interval podvrcholem vi Takov� je tak� stav pro�es�vac� p��mky ve t�et� pozici

Algoritmus ��� Regularizace grafu

Vstup� Rovinn� graf GV�stup� Regul�rn� graf obsahuj�c� G

Reprezentace struktur jako vyv��en� vyhled�vac� strom � �pravy v O�log n��� inicializace pro�es�vac� p��mky pro vn �ka�d� hrana v IN�vn� je hranic� intervalu a vn jep�i�azen�m bodem v�ech�

for i " n � to � do � vyhledej interval� ve kter�m le�� vi if jOUT �vi�j � then spoj vi s bodem p�i�azen�m nalezen�mu intervalu � obnov statut pro�es�vac� p��mky �slou�it intervaly ohrani�en� OUT �vi� v jeden� a

ten rozd�lit podle hran IN�vi��

� symetricky jako bod �� zdola nahoru

�� Triangulace �

#as pot�ebn� k jednomu pr�chodu cyklu �analogicky bod �� je d�ky vyhled�v�n� meziintervaly O�log n ! hi�� kde hi je po�et hran vych�zej�c�ch z bodu vi �d�len� na intervaly po�moc� vi� analogicky pro opa�n� pr�chod� Sou�et hi p�es v�echna i je line�rn�� proto v celkov��asov� slo�itosti dominuje O�log n� #as je tedy celkem O�n log n� Prostor je line�rn� �O�n��

��� Vta� Pro danou mno�inu bod� v rovin� S fv�� � � � � vng lze naj�t rozd�len� konvexn�hoobalu CH�S� monot&nn� �plnou mno�inou �et�zc� zahrnuj�c� v�echny p�edem dan� hrany Mv ase O�n log n� a prostoru O�n��

D kaz� V �ase O�n log n� se�ad�me vrcholy a ve stejn�m �ase provedeme regularizaci grafuV �ase O�n� pak provedeme balancov�n� vah a z�rove� sestroj�me po�adovan� �et�zce �

��� Vta� Monot&nn� polygon s n hranami lze triangulovat v ase O�n��

D kaz� V line�rn�m �ase sestroj�me set��d�n� dvou hrani�n�ch monot(nn�ch �et�zc�� nech*u�� � � � � un je v�sledn� posloupnost Pak �ui� � � i � n ��j � i tak� �e �ui� uj� je hranav P Idea algoritmu" v pr�chodu shora dol� lze p�id�vat �diagon�ly� U�ijeme z�sobn�k s p���

stupn�m dnem �k nahl�dnut�� V z�sobn�ku bude v�dy ��st hranice P tak� �e uj� uj��� uj�� tampat��� jestli�e

��ujuj��� uj��uj��� � ���oV z�sobn�ku jsou ulo�eny vrcholy �uspo��dan� podle y�ov� sou�adnice�� kter� u� byly nav�t�veny�ale st�le je�t� se pro n� nena�la vhodn� diagon�laAlgoritmus ��� Triangulace monot�nn�ho polygonu

� u�� u� d�me do z�sobn�ku STACK% i " �

for v�echny ui� i � do

� if ui soused� s v� " bottom�STACK� ale nesoused� s v " top�STACK� then �� p�idej hrany �ui� v��� �ui� v�� � � � � �ui� v� � sma� z�sobn�k a vlo� do n�ho prvky v� ui

elsif ui soused� s v " top�STACK� ale nesoused� s v� " bottom�STACK� then � while d�lka z�sobn�ku je v�t�� ne� � a ��uivtopvtop��� � ���o do �� p�idej hranu �ui� vtop��� a seber vrchol z�sobn�ku

p�idej ui do z�sobn�ku � else &' soused� s ob�ma �� p�idej diagon�ly �ui� vbottom���� � � � � �ui� vtop��� &' algoritmus kon��

Na obr�zku � jsou v ��stech a�� b� a c� ilustrov�ny polohy vrchol� diskutovan� postupn�v bodech �� a � algoritmu Pln� ��ry jsou v�dy hrany u� d��ve zn�m� a p�eru�ovan� ��ryzna�� hrany pr�v� p�id�van� Podrobnou diskusi spr�vnosti algoritmu p�enech�v�me �ten��i

��� Vta� Triangulaci konvexn�ho obalu mno�iny S � R�� jSj n s p�edem zadanou mno�inouhran T � S� lze prov�st v optim�ln�m ase O�n log n� a prostoru O�n��

D kaz� Podle v�ty �� �pln� mno�ina monot(nn�ch �et�zc� d�l�c� cel� CH�S� na line�rn� mnohomonot(nn�ch polygon� s hrani�n�mi �et�zci bez spl�vaj�c�ch hran se najde v �ase O�n log n�P�itom lze z�rove� odeb�rat vznikaj�c� monot(nn� polygony Pak ka�d� hrana je nejv��e ve dvoupolygonech� tj celkem pot�ebujeme �as

�� TRIANGULACE A VYHLED*V*N� V ROVINN+CH ROZD,LEN�CH

e eeee

ui

v� v

v

v�

v�

c�

eeee

ui

v

v�

v�

a�

e v� v

eeee

eeb�

u

v�

v

v�

v�

v� v

Obr �" Mo�n� pozice vrchol� monot(nn�ho polygonu diskutovan� p�i jeho triangulaci

�� Vyhled�v�n� v rovinn�ch rozd�len�ch ��

BCH regularizace �et�zce triangulaceO�n log n� ! O�n log n� ! O�n� ! O�n�

��� Vyhled�v�n� v rovinn�ch rozd�len�ch

Anglick� term�n je Geometric Searching Jde v podstat� o probl�m typu dotazu na p��slu�nostbodu v rovin� �dan�ho dotazem� k bu�ce rovinn�ho rozd�len� �dan�ho p�edem�Jin�mi slovy� m�me d�no pevn� �ve smyslu okam�iku dotazu� rovinn� rozd�len� Na vstup

p�ich�zej� dotazy ve form� bodu a v�stupem je bu�ka rozd�len�� ve kter� tento bod le��Rozd�len� se v�ak m��e �as od �asu m�nit� mluv�me pak o dynamick� struktu�eVyhled�n� lze �e�it proch�zen�m cel� struktury v line�rn�m �ase Dotazy jsou v�ak �astou

operac�� a budeme od nich asi o�ek�vat �as lep��Budeme pou��vat tato kriteria"

� �as pot�ebn� pro odpov�) �pr�m�rn�� nejhor���� spot�ebovan� pam�*� �as pot�ebn� na p�edp��pravu �konstrukce pam�*ov�ch struktur�� �as pot�ebn� na �pravu struktur p�i zm�n� dat �dynamick� struktura�

���� De�nice� Rovinn� rozd�len� je p��mo�ar� vno�en� rovinn�ho grafu do R� Zobecn�n�rovinn� rozd�len� m��e nav�c obsahovat neohrani�en� mnoho�heln�kov� oblasti

Takov� de�nici odpov�daj� v�echny triangulace a Voron�ho diagramy Nau��me se tedy vyhle�d�vat mimo jin� v nichUvedeme nyn� t�i mo�n� p��stupy k �e�en� probl�mu

����� Metoda p�s�

Idea Set��d�me vrcholy podle y�ov� sou�adnice T�m se R� rozpadne na horizont�ln� p�syPr�nik grafu G s jedn�m p�sem se sest�v� z �se�ek� kter� jsou ��stmi hran v G Tyto se nav�cneprot�naj� �mohou m�t jeden spole�n� bod na hranici p�su� Proto m��eme set��dit �se�ky�nap� odleva doprava� T�m z�sk�me zjemn�n� G na �kachli�ky� lexikogra�cky uspo��dan�V t�to struktu�e ji� m��eme efektivn� vyhled�vatPo�et kachli�ek v�ak m��e b�t a� kvadratick�� jak ukazuje p��klad na obr�zku � Tak

obrovsk� n�roky na pam�* jsou pro aplikace s velk�m mno�stv�m dat nep�ijateln�P�esto um�me postavit vyv��en� strom pro O�n�� kachli�ek� ve kter�m se d� vyhled�vat

v �ase O�log�n��� O�log n� #as p��pravy je ohrani�en po�tem kachli�ek� a bude tedy tak�kvadratick�P�i konstrukci kachli�ek lze vyu��t pro�es�v�n�� kde struktura ud�lost� je uspo��dan� seznam

vrchol� a statut pro�es�vac� p��mky jsou hrany uchov�van� ve � � �� stromu

���� Tvrzen�� Metodou p�s� lze vyhled�vat v rovinn�m rozd�len� s n vrcholy v ase O�log n�s pam�t� O�n�� a asem p��pravy O�n���

� TRIANGULACE A VYHLED*V*N� V ROVINN+CH ROZD,LEN�CH

Obr �" Pro tento vzor rozd�len� roviny na dv� ��sti roste po�et kachli�ek kvadraticky oprotipo�tu vrchol�

����� Metoda cest

Jestli�e pou�ijeme �plnou monot(nn� mno�inu �et�zc� v grafu G �tzv cesty�� dostaneme al�goritmus� kter� bude vyhled�vat v �ase O�log� n�� pot�ebn� pam�* bude O�n� a �as p��pravyO�n log n�

� Algoritmus regularizace �� nep�id�v� vrcholy� v�sledn�ch hran je O�n�� pot�ebn� �as jeO�n log n�

� Algoritmus pro nalezen� cest pracuje v �ase O�n� Jestli�e prohled�me cesty zleva doprava�pak v ka�d� cest� p�ibereme alespo� jednu novou hranu� tedy cest je O�n�

� Line�rn�m hled�n�m najdeme dv� n�sleduj�c� cesty� mezi kter�mi se hledan� bod nach�z��proto �as vyhled�n� je O�log� n�

Kdybychom si pamatovali v�echny cesty jako posloupnosti hran� dostali bychom kvadratic�kou pam�*ovou slo�itost D� se v�ak vyu��t faktu� �e hran i cest je dohromady line�rn� mnoho�a p�i mal�m sn��en� �asov�ho v�konu tak� dos�hneme pam�ti O�n�Budeme si pamatovat cesty v bin�rn�m stromu� a ka�dou hranu v tomto stromu ulo��me

pouze pro jednu cestu� a to pro tu� kter� je ve stromu nejv��e z t�ch cest� ve kter�ch se dan�hrana nach�z� Tak zajist�me line�rn� spot�ebu pam�ti P�i vyhled�v�n� pak ale budeme musetmo�n� prohled�vat nejen hrany alokovan� dan� cest�� ale i v�em cest�ch v��e ve stromu T�chtocest bude O�log n�� a v ka�d� bychom prov�d�li vyhled�v�n� v �ase O�log n�� proto m��emeo�ek�vat celkov� �as O�log� n� Skute�n� realizace bude trochu odli�n�� bude ale pracovat vuveden�m �ase a prostoru

���� De�nice� Implicitn� reprezentace cest je tabulka uspo��dan�ch dvojic �L�e�� R�e�� prohrany e � G s vlastnost�� �e e pat�� pr�v� do cest Pj takov�ch� �e L�e� � j � R�e�

���� Pozn�mka� Tabulku implicitn� reprezentace cest lze zkonstruovat v line�rn�m �ase p��mov algoritmu balancov�n� cest �� �

Obr�zek �� a tabulka ilustruj� tabulku implicitn� reprezentace cest pro �est bod� v rovin�

���� De�nice� Redukovan vyhledvac� struktura �RVS� je vyv��en� strom obsahuj�c� v ka��d�m uzlu i vyhled�vac� strom Ti pro y�ov� sou�adnice koncov�ch bod� v�ech hran e� pro kter�

�� Vyhled�v�n� v rovinn�ch rozd�len�ch ��

e

e e e

e

ecesty ���

cesty ���

e�

e�

e

e�e�

e�

e�

e

e�

e��

e��e��

Obr ��" Graf� na n�m� ilustrujeme implicitn� reprezentaci cest

cesta � " � e� �cesta " � e� � e� �cesta � " � e� � e� e�� �cesta " � e� � e� � e�� e�� �cesta � " � e� � e� e � e�� �cesta � " � e e� �

hrana e L�e� R�e� Pos�e�e� � � �e� � e � � �e� e� � � �e� e� � � �e � � �e� � � �e�� e�� � � �e�� �

Tabulka " Popis pr�b�hu cest v grafu a tabulka implicitn� reprezentace cest

� TRIANGULACE A VYHLED*V*N� V ROVINN+CH ROZD,LEN�CH

� � �

�e

e�

� �

e�e

e����

��

e�

e�

e��e��

e�

e�

e�

T� T� T T� T� T�

Obr ��" Redukovan� vyhled�vac� struktura

je i�t� cesta nejv��e polo�enou cestou ve stromu� ve kter� se nach�z� Pro jednotliv� hranyozna��me jejich v�skyt ve stromu jako Pos�e� �viz obr�zek �� a ���

��� Vta� Vyhled�v�n� v redukovan� vyhled�vac� struktu�e prob�h� v aseO�log� n�� prostoruO�n� a p��pravn�m ase O�n log n��

D kaz� Pokud um�me z�skat Pos�e� v �ase alespo� O�n log n�� um�me sestrojit RVS v tomto�ase t�� N�sleduj�c� algoritmus zalo�en� na vyj�d�en� ve dvojkov� soustav� to zvl�dne v �aselogaritmick�m

Algoritmus �� Zji�t�n� Pos�e� pro hranu e

Vstup� hrana e a hodnoty L�e�� R�e�V�stup� hodnota Pos�e�

� if L�e� R�e� then

�� Pos�e� " L�e� a skon�i

else

� poc " �% l " L�e�% r " R�e�% b " TRUE

while l � r do

� poc " poc ! � if l je lich� then b " FALSE

� l " bl� c r " br� c

� if b then �� Pos�e� " L�e�

else � Pos�e� " � l ! ��� poc

#asovou slo�itost vyhled�v�n� a prostor jsme ji� odvodili d��ve Nyn� nab�z�me algoritmustakov�ho vyhled�v�n�

Algoritmus ��� Vyhled�v�n� v RVS

Vstup� bod q a RVS pro cesty s vrcholy v mno�in� S

�� Vyhled�v�n� v rovinn�ch rozd�len�ch ��

V�stup� dv� sousedn� cesty v RVS a jejich hrany� mezi kter�mi bod q le��� nebo informace� �ele�� mimo CH�S�

� Pokud q nele�� v p�su mezi nejvy���m a nejni���m vrcholem� pak nele�� v ��dn� bu�ce

l " �% r " k ! � �k je po�et cest� k ��� ��� P� " P�%Pk�� " Pk%L " horizont�ln� p��mka proch�zej�c� q

el " hrana v Pl prot�naj�c� L

� er " hrana v Pr prot�naj�c� L

� Pokud q nen� mezi hranami el� er� pak nen� v ��dn� bu�ce

� while r � l ! � do

�� m " d�l ! r�� e� if R�el� � m then l " m

�� elsif L�er� � m then r " m

� else najdi hranu v Pm prot�naj�c� L a aktualizuj l� r� el� er

Invariant cyklu �� q le�� mezi Pl� Pr a L prot�n� el� er Proto�e za�neme s l � a r k ! �� jepodm�nka v � poprv� spln�na a m ukazuje na ko�en RVS V dal��ch pr�chodech cyklem � sepak posunujeme od ko�ene k list�m T�m je zaji�t�no� �e pr�nik L s Pm m��eme v�dy hledatv p��slu�n�m vyhled�vac�m stromu Tm �

���� Pozn�mka� /Preparata���0 uv�d� zp�sob� jak dos�hnout v RVS vyhled�vac�ho �asuO�log n� p�i zachov�n� pam�ti na O�n� Ve vyhled�vac� struktu�e se p�idaj� tzv mosty� co�jsou ukazatele mezi jednotliv�mi hranami alokovan�mi v r�zn�ch uzlech nad�azen�ho stromu�odtud n�zev p�emos�ovn�� Pomoc� takov�ch most� se lze z uzlu odpov�daj�c�mu dan� cest�dostat ke v�em hran�m a nemus� se prov�d�t hled�n� ve v�ech uzlech v��e ve stromu

����� Metoda postupn�ho zjem�ov�n�

Ka�d� rovinn� rozd�len� um�me triangulovat tak� �e nep�id�v�me nov� vrcholy a zachov�v�medan� hrany� a to v �ase O�n log n� a prostoru O�n� M��eme se tedy v dal��m omezit na tzvjednoduch rozd�len�� tj takov�� �e v�echny bu�ky rozd�len� jsou troj�heln�ky v�etn� neohra�ni�en�chPostupn� proch�z�me velk� mno�iny nez�visl�ch vrchol� v grafu �tedy t�ch� kter� nesd�l�

hranu�� tyto vypust�me a v�sledek znovu triangulujeme �viz obr�zek � � Po jist�m po�tukrok� dostaneme jedin� troj�heln�k �abychom to zajistili� mus�me p�idat t�i nov� body� jejich�troj�heln�k bude obsahovat v�echny ostatn� body�P�i odstra�ov�n� vrchol� budeme mezi troj�heln�ky ve star� a nov� triangulaci� kter� spolu

inciduj�� udr�ovat ukazatele M��eme tak vytvo�it strom� jeho� ko�enem bude u� zm�n�n� troj��heln�k obsahuj�c� v�echny ostatn� body Ka�d� jednotliv� �rove� stromu bude reprezentovatjednu triangulaci� uzly budou troj�heln�ky S hloubkou stromu budou p�ib�vat vrcholy� a� naposledn� �rovni bude prvotn� triangulace Hrany ve stromu budou odpov�dat relaci incidence� apovedou v�dy mezi uzly sousedn� �rovn� Nep�jde v�ak o typick� strom� proto�e do uzlu m��ev�st v�ce hran z uzl� p�edchoz� �rovn� #�st takov�ho stromu ukazuje obr�zek �� Vyhled�v�n�bude za��nat v ko�eni a pokra�ovat pouze po hran�chNyn� odvod�me slo�itost tohoto algoritmu

�� TRIANGULACE A VYHLED*V*N� V ROVINN+CH ROZD,LEN�CH

e e

e

eeee eee

e e

e

ee ee

Obr � " Vypu�t�n� mno�iny nez�visl�ch vrchol� v grafu

e

eee

e

e

eee

e e e e

ee�

� �

���

Obr ��" #�st vyhled�vac� struktury pro zjem�ov�n�

��

���� Lemma� Nech� G �V�E� je rovinn� graf s n jV j vrcholy s minim�ln�m stupn�m �Nech� V � � V � Pak existuje nez�visl� mno�ina I � V nV � vrchol� stupn� nejv��e - o mohutnostialespo#

�n ! � �jV �j����Nav�c I lze nal�zt v ase O�n��

D kaz� Nech* V �� je mno�ina vrchol� v G se stupni nejv��e �� ozna�me x jV ��j G je rovinn�graf� proto m� nejv��e �n � hran D�le m�me n x vrchol� stupn� alespo� �� a ka�d�jin� vrchol m� stupe� alespo� �� tedy /�x ! ���n x�0� � �n � Odtud x � �n ! � ���Uva�me nyn� podgraf indukovan� uzly V �� V � Ten m� alespo� x jV �j vrchol� a ka�d� m�stupe� nejv��e � Tzn m��eme obarvit vrcholy deseti barvami tak� aby ka�d� dva sousedn�byly obarveny r�zn� To lze prov�st v �ase O�n� �Barvit barvami �� � � � � �� a vrcholy beremev libovoln�m po�ad�� pou�ijeme v�dy nejni��� barvu dosud nepou�itou u soused�� Pak tammus�podle Dirichletova principu existovat mno�ina vrchol� se stejnou barvou o mohutnosti alespo��x jV �j����� a ty spolu po dvou nesoused� Z�rove� �x jV �j���� � �n ! � �jV �j����

���� Vta� Nech� G je jednoduch� rovinn� rozd�len� s n vrcholy� Pak vyhled�n� v hran�ch Glze �e�it v ase O�log n�� prostoru O�n� a v p��pravn�m ase O�n log n��

D kaz� Zvol�me si vhodn� konstantn� po�et vrchol�� pro kter� �lohu �e��me p��mou diskus��nap� n ��� Nech* n � ��� Nech* I je nez�visl� mno�ina vrchol� se stupn�m nep�evy��uj�c�m �� kter� nele�� na hrani�n�m troj�heln�ku Pou�ijeme lemma ��� s jV �j � �hrani�n�troj�heln�ky� To znamen�� �e v �ase O�n� najdeme takovou mno�inu� pro ni� jIj � �n �����Vynech�n�m I z�sk�me G� s nejv��e n jIj � ��n��� ! � P�itom bu�ky v G� jsou mnoho��heln�ky s � � m � � hranami� tj ka�dou z nich um�me triangulovat v konstantn�m �aseO���Rekurzivn� aplikac� tohoto postupu z�sk�me po�adovanou vyhled�vac� strukturu �

Pr�niky

V t�to ��sti uvedeme �e�en� n�kolika �loh� kter� jsou zalo�eny na vyhled�n� pr�niku �nebopr�nik�� jist�ch geometrick�ch objekt�V prvn�m p��pad� p�jde o nalezen� pr�nik� v�ech dvojic �se�ek Budeme tedy m�t za �kol

zjistit� kter� dvojice z nich vybran� se prot�naj� a ve kter�m bod�Ostatn� �lohy budou m�t pon�kud jin� charakter P�jde o nalezen� spole�n�ho pr�niku v�ech

objekt� na vstupu

��� Prot�n�n� �se�ek

M�jme n �se�ek L�� � � � � Ln v rovin� $kolem je naj�t v�echny jejich vz�jemn� pr�se��ky Je�lipo�et pr�se��k� s O�n��� nelze �ekat lep�� �as b�hu algoritmuNajdeme algoritmus pracuj�c� v �ase O��n ! s� log n� metodou pro�esvn�� kde s je d�lka

v�stupu� tedy po�et pr�se��k� Budeme postupovat zleva doprava� tedy pro�es�vac� p��mkabude vertik�ln�

�� PR.NIKY

� Statut pro�esvac� p��mky �vertik�ln� struktura� bude tvo�en aktivn�mi �se�kami� tedyt�mi� kter� pro�es�vac� p��mka pr�v� prot�n�� set��d�n�mi podle v��ky pr�niku s pro�e�s�vac� p��mkou L do vyhled�vac�ho stromu

� Struktura udlost� �horizont�ln� struktura� bude set��d�n� posloupnost koncov�ch bod��se�ek a pr�nik� aktivn�ch �se�ek� le��c�ch napravo od L �ve vyhled�vac�m stromu�

Po�adujeme� aby ka�d� pr�chod novou ud�lost� byl zvl�dnut v �ase O�log n� Pot�ebujeme tedyvhodnou datovou strukturu� poskytuj�c� n�sleduj�c� funkce"Find�p� 6 pro dan� bod najde interval jej obsahuj�c�

Input�q� 6 vlo�� dal�� �se�ku do L nebo ud�lost

Delete�q� 6 zru�� �se�ku nebo ud�lost

Pred�Succ 6 p�edch�dce a n�sledn�k

Interchange�p�q� 6 v�m�na dvou �se�ek prot�naj�c�ch LStruktura pro�es�vac� p��mky je jako seznam aktivn�ch �se�ek inicializov�na na pr�zdnou Naza��tku algoritmu bude v�ak pot�eba set��dit koncov� body �se�ek podle jejich x�ov� sou�adnicea inicializovat podle nich h�strukturuAlgoritmus ��� Nalezen� v�ech pr�se��k� mno�iny �se�ek

Vstup� mno�ina �se�ek L�� � � � � Ln v rovin�V�stup� mno�ina jejich pr�se��k�

� v�struktura " � h�struktura " v�echny koncov� body �se�ek set��d�n� podle x�ov� sou�adnice

� while h�struktura � � do

�� p " bod v h�struktu�e s minim�ln� x�ovou sou�adnic�� odstra� p z h�struktury�� if p je lev� koncov� bod �se�ky then �� nov aktivn� �se�ka��� j " ��slo �se�ky� jej�� je p koncov� bod �Lj��� vlo� Lj do v�struktury��� vyhledej ��sla soused� �i� k� �se�ky Lj ve v�struktu�e�� vlo� Li � Lj a Lj � Lk do h�struktury� pokud existuj���� odstra� Li � Lk z h�struktury� pokud tam je

� elsif p je prav� koncov� bod �se�ky then �� star aktivn� �se�ka je odstran�na�� j " ��slo �se�ky� jej�� je p koncov� bod �Lj�� vyhledej ��sla soused� �i� k� �se�ky Lj ve v�struktu�e�� odstra� Lj z v�struktury� vlo� Li � Lk do h�struktury� je�li napravo od pro�es�vac� p��mky

�� else �� p mus� b�t pr se��k p��mek��� �i� j� " indexy �se�ek� jejich� je p pr�se��k�� zam�� Li a Lj ve v�struktu�e��� vyhledej ��sla �h� k� dal��ch soused� Li a Lj ve v�struktu�e�� vlo� Lh � Li a Lj � Lk do h�struktury� je�li Lh nyn� soused Li �resp Lk soused

Lj�� a jsou�li tyto pr�niky napravo od pro�es�vac� p��mky

�� Pr�nik polorovin ��

��� odstra� Lh � Lj a Li � Lk z h�struktury��� po�li �p� i� j� na v�stup

Invariant algoritmu� je�li p pr�nik aktivn�ch �se�ek �tedy za�azen�ch v sou�asn� dob�ve v�struktu�e� Li� Lj a ve vertik�ln�m p�su nen� ��dn� koncov� bod nebo dal�� pr�nik�pak p se objev� v horizont�ln� struktu�e pro dal�� pr�chod Z toho tak� plyne� �e v�echnypr�niky nalevo od pro�es�vac� p��mky u� byly nalezeny

�as� O�n! s� pr�chod� ud�lostmi� ka�d� v �ase O�log n�� proto v�sledn� �as je O��n !s� log n�

Vertik�ln� struktura je realizovateln� v prostoru O�n� P�i naivn�m p��stupu k horizont�ln�struktu�e �bez odstra�ov�n� v bodech ��� a ���� dostaneme prostor O�n!s�� v opa�n�mp��pad� dos�hneme O�n�

��� Pozn�mka� Modi�kac� algoritmu � lze z�skat algoritmus� kter� v �ase O�n log n� zjist��zda existuje pr�se��k alespo� dvou �se�ek $prava spo��v� ve vypu�t�n� v�ech krok� o�et�uj�c�chnalezen� pr�niky Pokud bychom tento modi�kovan� algoritmus nezastavili po nalezen� prvn�hopr�se��ku� ur�it� nalezne pr�nik s nejmen�� x�ovou sou�adnic�� ne v�ak nutn� jako prvn� nalezen�pr�nik

Mnoho probl�m� vede na �lohu nalezen� pr�se��k� sady �se�ek Uvedeme n�kter� z nichspolu s �asy� kter�ch lze pomoc� na�eho algoritmu dos�hnout

��� D�sledek�

�� Protnut� dvou mnoho�heln�k� lze zjistit v ase O�n log n� a prostoru O�n��

�� Jednoduchost mnoho�heln�ka lze zjistit v ase O�n log n� a prostoru O�n��

� Protnut� hran grafu vno�en�ho do roviny lze zjistit v ase O�n log n� a prostoru O�n��

��� Pr�nik polorovin

Nech* H�� � � � �Hn jsou poloroviny v rovin� $kolem je nal�zt jejich pr�nikTni �Hi

Pou�ijeme metodu rozd�l a panuj Pro tuto metodu je charakteristick� vyu�it� rekurze

Algoritmus ��� Nalezen� pr�niku polorovin

Vstup� poloroviny H�� � � � �Hn

V�stup� jejich pr�nikTni �Hi

� if n � then�� Spo��tej pr�nik dvou polorovin a po�li ho na v�stup

else

� Rozd�l H�� � � � �Hn na dva p�ibli�n� stejn� velk� d�ly a zavolej rekurzivn� sama sebepro ka�d� z nich

Takto z�skan� ��ste�n� v�sledky jsou konvexn�mi mnoho�heln�kov�mi oblastmi �narozd�l od konvexn�ch mnoho�heln�k� nemus� b�t ohrani�en�� Na takov� m��e b�taplikov�na v�ta ��� o nalezen� pr�niku dvou konvexn�ch mnoho�heln�k� v line�rn�m�ase� proto�e v jej�m d�kazu nen� ohrani�enost mnoho�heln�k� pou�ita

�� PR.NIKY

�as� Je�li T �n� �as� kter� algoritmus spot�ebuje� plat� T �n� T �n� � ! O�n� a T ��� �Odtud plyne� �e T �n� O�n log n�Dos�hli jsme tedy �asu O�n log n� Jist� n�s bude zaj�mat� zda lze dos�hnout v�sledku v �ase

lep��m Na p��klad� si uk��eme� �e ne��� P��klad� Poloroviny Hi nech* maj� hranice te�n� k parabole y x� v bodech �xi� x�i �Pr�nik m� hranici d�nu hrani�n�mi p��mkami dan�ch polorovin uspo��dan�mi podle sm�rniceNalezen� jejich pr�niku tedy znamen� pr�v� uspo��d�n� sm�rnic takov�ch hrani�n�ch p��mekProto �e�en� tohoto probl�mu bude �asov� alespo� tak slo�it� jako t��d�n�� tedy O�n log n�Na z�klad� tohoto v�sledku ji� m��eme formulovat v�tu��� Vta� Pr�nik n polorovin lze z�skat v optim�ln�m ase O�n log n��D kaz� plyne z p�edchoz�ch �vah �

��� Pr�nik konvexn�ch mnoho�heln�k�

Budeme nyn� zkoumat nalezen� pr�niku n konvexn�ch mnoho�heln�k�Ka�d� konvexn� k��heln�k je pr�nikem polorovin ohrani�en�ch hranami k��heln�ka �tzv

op�rn� nadroviny� Lze pou��t p�edchoz� v�sledek pro pr�nik polorovin s vyu�it�m znalostiasociativity pr�niku Proto pr�nik n konvexn�ch mnoho�heln�k�� kde i�t� mnoho�heln�k m� kivrchol� �hran�� lze spo��tat v �ase

O�nXi �

ki log�nXi �

ki���

Jestli�e pro jednoduchost ohrani��me po�et vrchol� pro t�chto n mnoho�heln�k� ��slem k� pakdostaneme �asovou slo�itost O�kn log�kn��Ve v��e popsan�m algoritmu jsme postupovali tak� �e jsme rozd�lili v�echny mnoho�heln�ky

podle jejich op�rn�ch p��mek na poloroviny a pak jsme spo��tali pr�nik v�ech t�chto polorovinM��eme v�ak pou��t jin�ho postupu" Nebudeme mnoho�heln�ky rozb�jet� ale rad�ji s nimi conejd�le pracovat jako s objekty vcelkuNa�e procedura bude mno�inu n k��heln�k� d�lit metodou rozd�l a panuj na stejn� dv�

stejn� velk� podmno�iny n� k��heln�k�� a pro n� odd�len� zavol� rekurzivn� sama sebe Pozji�t�n� v�sledk� spo��t� jejich pr�nik metodou uvedenou v d�kazu v�ty ��� Pokud je navstupu jedin� mnoh�heln�k� je pr�nikem sama se sebou a tedy v�stupem algoritmu Tentop��pad slou�� jako zar��ka rekurze#as T �k� n� tohoto algoritmu odvod�me� pokud si uv�dom�me� �e plat�

T �k� n� T �k� n� � ! kn� T �k� �� O�k�

Celkov� dost�v�me �as O�kn log n�

��� J�dro jednoduch�ho mnoho�heln�ka

Budeme se zab�vat probl�mem nalezen� j�dra jednoduch�ho mnoho�heln�kaV �vodn� kapitole jsme uvedli de�nici j�dra jednoduch�ho mnoho�heln�ka �tedy takov�ho�

jeho� hrany se neprot�naj�� Toto j�dro je vlastn� pr�nikem v�ech polorovin� kter� ohrani�uj�vnit�ek jednoduch�ho mnoho�heln�ka

� J�dro jednoduch�ho mnoho�heln�ka ��

e

e

e

eJ+adrov�

e�

v�

e�

v�

e

v

e�

Obr �" J�dro nekonvexn�ho jednoduch�ho mnoho�heln�ka

�� Pozn�mka�� J�dro je v�dy konvexn� mnoho�heln�k �viz obr ��� Jednoduch� mnoho�heln�k je konvexn� pr�v�� kdy� je roven sv�mu j�dru� Pro mnoho�heln�k� kter� nen� jednoduch� �jeho n�kter� hrany se prot�naj� jinde ne� vevrcholech�� j�dro v�bec nede�nujeme

P�i testov�n� p��slu�nosti dan�ho bodu x � R� do vnit�ku dan�ho konvexn�ho mnoho�heln�kajsme vyu��vali bin�rn�ho vyhled�v�n� Tento princip lze pou��t v�dy� kdy� j�dro mnoho�heln��ka P je nepr�zdn�P��m� aplikace pr�niku p��slu�n�ch polorovin d�v� algoritmus nalezen� j�dra o slo�itos�

ti O�n log n�� kde n je po�et hran mnoho�heln�ka Lze to v�ak zlep�it na O�n� n�sleduj�c�mzp�sobemMnoho�heln�k budeme reprezentovat jako dvojit� cyklick� seznam vrchol� vi a hran

ej " v�e�v�e� � � � e��v��e�

Za v� zvol�me vrchol re7exn� �s �hlem v�t��m ne� ���o�� pokud takov� neexistuje� je uva�o�van� mnoho�heln�k konvexn�� tj roven sv�mu j�dru Budeme postupovat po vrcholech v�� � � �mnoho�heln�ku a v ka�d�m kroku z�sk�memnoho�heln�kKi� kter� nemus� b�t ohrani�en� Vzni�kaj�c� mnoho�heln�ky Ki budou v�dy konvexn� aproximac� v�sledn�ho j�dra Posledn� z nich�ozna��me jej K� bude j�drem mnoho�heln�kaBudeme pot�ebovat dva body Fi� Li de�novan� jako nejvzd�len�j�� body dotyku te�en spu��

t�n�ch z vrcholu vi na mnoho�heln�k Ki Body Fi� Li le��c� na te�n�ch fi� li spu�t�n�ch z boduvi na mnoho�heln�k Ki jsou ilustrov�ny na obr�zku ��

Algoritmus ��� Nalezen� j�dra jednoduch�ho mnoho�heln�ka

Vstup� Mnoho�heln�k ej " v�e�v�e� � � � envne�V�stup� Jeho j�dro K �m��e b�t i pr�zdn��Inicializace� Najdeme v�� pokud neexistuje� je p�vodn� mnoho�heln�k sv�m j�drem D�le po�t�ebujeme inicializovat K�� F�� L�"

K� " �e�v�e��F� " bod v nekone�nu na polop��mce�e�v�L� " bod v nekone�nu na polop��mce v�e��

� PR.NIKY

ee

eeee

Ki

Fi

fi

vi

liLi

Obr ��" Te�ny spu�t�n� z bodu na mnoho�heln�k a jejich nejvzd�len�j�� body dotyku

P�echod od Ki ke Ki��� Fi� Li jsou body na hranic�ch op�rn�ch polorovin pro Ki proch�zej�c�chvrcholem vi� a to ty nejvzd�len�j�� v Ki� vi byl re7exn� vrchol� polop��mka vi��vi ur�uje dal�� mo�n� zmen�en� Ki

�� Fi je nalevo od �ei��vi�� �tedy te�na f�� potom zat�m nic nem�n�me� Fi je napravo a Li nalevo� pak mus�me naj�t nov� pr�niky a dostaneme novou ��st

Ki�� Nav�c mus�me aktualizovat Fi� Li

Podobn� pro vi konvexn�Algoritmus se bu) ukon�� ji� v n�kter�m z krok� z vrcholu vi do vrcholu vi�� zji�t�n�m�

�e j�dro je pr�zdn�� nebo po projit� v�ech vrchol� V ka�d� konstrukci n�sleduj�c�ho Ki��

prov�d�me" vypou�t�n� hran �ka�dou nejv��e jednou�� nalezen� nov�ch bod� Fi��� Li�� �posunuj�se v�dy proti sm�ru hod ru�i�ek� Pokud K � �� nemohou Fi a Li ob�hnout kolem cel�homnoho�heln�ka v�ce ne� jednou� najdeme tedy t�mto algoritmem j�dro K v celkem line�rn�m�ase O�n� Bohu�el� jestli�eK �� mohou tyto body ob�hat a� O�n� kr�t kolem dokola� pr�b�halgoritmu si tedy v tomto p��pad� vy��d� �as 2�n��� viz obr �� Jednoduchou modi�kac�algoritmu spo��vaj�c� v p�id�n� testu kontroluj�c�ho ob�h�n� bod� Fi� Li dos�hneme line�rn�ho�asu i v p��pad� K �

�� Pr�nik poloprostor�

V podkapitole jsme se zab�vali nalezen�mpr�niku polorovin Nyn� bude vstupem pro stejnou�lohu mno�ina ��dimenzion�ln�ch poloprostor�Pomoc� konstrukce jist� relace mezi body a nadrovinami v prostoru libovoln� dimenze p�e�

vedeme probl�m nalezen� pr�niku poloprostor� na du�ln� probl�m nalezen� konvexn�ho obalumno�iny bod���� De�nice� Nech* h je �nevertik�ln�� nadrovina v Rd�� dan� rovnic� x� p�x�! � � �!pdxd!pd�� Pak de�nujeme duln� bod k nadrovin� h" �h� /p�� � � � � pd� pd��0 p a duln� nadrovinuk bodu p /p�� � � � � pd� pd��0" �p� � x� p�x� � � � pdxd ! pd��

��� De�nice� Vertikln� vzdlenost bodu p /p�� � � � � pd� pd��0 od nadroviny h � x� q�x�!� � �! qdxd ! qd�� de�nujeme

vd�h� p� " pd�� �p�q� ! � � � pdqd ! qd���

�� Pr�nik poloprostor� ��

v�

Obr ��" 8kared� mnoho�heln�k s pr�zdn�m j�drem

��� Lemma�vd�h� p� vd��p�� �h��p � h� �h� � �p�

D kaz� P��m�m dosazen�m �

��� D�sledek� Nech� p�� p� � R jsou body v prostoru� h�� h� � R roviny� Jestli�e L�p�� p�� �h� � h�� pak L��h��� �h��� � �p�� � �p���Nech* hi je mno�ina rovin v R� h�i p��slu�n� poloprostory nad resp pod hi Chceme dostat

S m�i �

h�i �n�

i m��

h�i S� � S����

���� Lemma� Rovina ha neobsahuje ��dnou st�nu S� pr�v� tehdy� kdy� �ha� nen� vrcholemhorn�ho konvexn�ho obalu mno�iny f�hi� j � � i � ng�D kaz� ha �nadbyte�n��� potom existuje nejbli��� vrchol v v S� a t�i incidentn� st�ny hi� hj � hktak� �e

h�i � h�j � h�k h�i � h�j � h�k � haPak �ha� le�� na nebo pod �v� Nav�c �v� je rovina ur�en� body �hi�� �hj�� �hk� Proto�ha� nen� v p��slu�n�m konvexn�m obalu �

Najdeme�li tedy vrcholy konvexn�ch obal� mno�in

�h�� �� � � � � �h�m�

a�h�m���� � � � � �h

�n ��

zn�me mno�iny S� a S� ze vztahu � Jsou to konvexn� mnohost�ny Spo��t�n�m jejich pr�nikudostaneme pr�nik v�ech poloprostor� Tuto f�zi algoritmu rozeb�r� podrobn�ji /Preparata���0

� � VYHLED*V*N� DLE ROZSAHU

� Vyhled�v�n� dle rozsahu

Anglick� ekvivalent pro tuto t��du probl�m� zn� Range SearchingBudeme m�t zad�nu mno�inu S o n z�znamech �mohou to b�t bu) body nebo cel� objekty

mno�iny bod�� Dotaz je zad�n� rozsahu� tedy ve sm�ru v�ech os maxima a minima� kter�n�s zaj�m� Odpov�d� na dotaz je podmno�ina S� � S� kter� inciduje se zadan�m rozsahemNa �as p��pravy se nebudeme zam��ovat� bude n�s zaj�mat hlavn� pam�* a �as pot�ebn�

k realizaci a zpracov�n� dotazu Podstatnou roli hraje volba vhodn� datov� struktury

�� P��klad� Uva�ujme mno�inu n bod� na p��mce a dotazovan� rozsah je interval /x�� x��0Vyhled�n� provedeme takto"� Bin�rn�m vyhled�v�n�m najdeme nejlev�j�� bod p v intervalu /x�� x��0

Postupn� zpracov�v�me bod za bodem� a� naraz�me na prav� konec x��Pot�ebn� datov� struktura je bin�rn� strom� jeho� listy jsou propojeny ukazately do �et�zu

�threaded binary tree�#as vyhled�n� je 1�log n! k� �optim�ln�� p�i pou�it� pam�ti 1�n�

V dal��m se soust�ed�me na vyhled�v�n� bod� ve v�cerozm�rn�ch prostorech� kter� u� nen� takelement�rn� jako na p��mce Nav�c nenajdeme algoritmus pracuj�c� v optim�ln�m logaritmick�mvyhled�vac�m �ase a p�itom s line�rn�mi n�roky na pam�* Uvedeme t�i algoritmy� kter� budoup�edstavovat jist� kompromisy mezi po�adavky na pam�* a �as

�� Multidimenzion�ln� bin�rn� strom

V t�to podkapitole nade�nujeme strukturu zvanou multidimenzion�ln� nebo tak� k�D stromUvedeme algoritmus na vyhled�n� dle rozsahu v tomto strom� V k�D stromech se daj� prov�d�ttak� operace vkl�d�n� a odstra�ov�n� bod�� jde tedy o dynamickou strukturu Tyto algoritmyjsou uvedeny v /Bentley���0 �� De�nice� Zobecn�n� obd�ln�k v R� je kart�zsk� sou�in interval� /x�� x�0 � /y�� y�0� kdex�� x�� y�� y� � R � f�� �g P�ipou�t�me tedy tak� neohrani�en� p��pady obd�ln�k� �� De�nice� �D strom m� s ka�d�m uzlem spojen obd�ln�k R�v� a mno�inu bod� S�v� � Sobsa�en�ch v R�v�S v spojujeme vybran� bod P �v� � S�v� Bodem P �v� vedeme p��mku rovnob��nou s jednou

z os� kter� rozd�l� S�v� p�ibli�n� na poloviny V d�len� pokra�ujeme p�i obracen� orientace d�lic�p��mky na ka�d� �rovni stromu� a� v z�skan�ch obd�ln�c�ch nejsou ��dn� body z S Takov� uzlyjsou listy �D stromu

�� Pozn�mka� Ka�d� uzel m� tvar �P �v�� t�v��M�v��� kde P �v� je bod spojen� s t�mtouzlem� t�v� je orientace �vertik�ln� nebo horizont�ln��� a M�v� je bu) x�ov� sou�adnice �provertik�ln� uzly� nebo y�ov� �pro horizont�ln� uzly�

Na obr�zku �� je zn�zorn�n �D strom pro mno�inu dev�ti bod� v rovin�A nyn� ji� sl�ben� algoritmus vyhled�v�n� Jde o vyhled�v�n� ve stromu� proto uvedeme

algoritmus� kde vrchol stromu� ve kter�m vyhled�v�n� za��n�� bude d�n parametrickyVyhled�n�v cel� struktu�e se provede vol�n�m t�to procedury se skute�n�m parametrem� kter� je ko�enemstromuAlgoritmus �� Range Searching metodou �D stromu

��� Multidimenzion�ln� bin�rn� strom ��

ee

e

ee

ee

e

e

AB

C

D

E

F

G

IH

ee e

eeeee euuuuuuu u u u

D E F G

IH

B

A

C

VERT

HORIZ

VERT

HORIZ

Obr ��" �D strom pro dev�t bod� v rovin�

�� � VYHLED*V*N� DLE ROZSAHU

Vstup� vrchol v� ve kter�m za��n� vyhled�v�n�� interval D /x�� x�0� /y�� y�0V�stup� na v�stupu se postupn� objevuj� v�sledn� body dotazuVyvoln�� je�li T �D strom� pak SEARCH�root�T ��

Procedure SEARCH� if t�v� vertik�ln� then

�� �l� r� " �x�� x��

else

� �l� r� " �y�� y��

� if l �M�v� � r then

�� if P �v� � D then po�li P �v� na v�stup

if v nen� list then

� if l � M�v� then SEARCH�LSON�v��D� if M�v� � r then SEARCH�RSON �v��D�

Prostor� �D strom pot�ebuje pam�* 1�n�P��prava� �D strom se sestroj� v �ase O�n log n��as vyhledn�� Nen� logaritmick�� jak by se mohlo zd�t Algoritmus toti� nav�t�vuje �adu uzl�

stromu �zbyte�n��� tj ani� by to vedlo k p��sp�vku do v�stupu Podrobn�j�� �nep��jem�nou� diskus� se ov���� �e jejich po�et je nejv��e O�

pn�� proto vyhled�n� prob�hne v �ase

O�pn! s�� kde s je d�lka v�stupu

Odvozen� �asov�ch i pam�*ov�ch slo�itost� pro rozsahov� dotaz v d�D stromu �tedy libovoln�dimenze� je uvedeno v /Preparata���0 s v�sledky" � Tvrzen�� Pomoc� obecn�ch d�D strom� lze pro v�echny dimenze d � �e�it rozsahov�dotaz pro n bod� v Rd v ase O�dn����d ! s�� p�i pam�ti 1�dn� a v ase p��pravy 1�dn log n��

�� Metoda p��m�ho p��stupu

Budeme nyn� pracovat pouze v rovin� s mno�inou S bod� o mohutnosti n Ka�d�m bodemp � S prolo��me horizont�ln� i vertik�ln� p��mku Tyto p��mky rozd�l� rovinu na �n ! ���

�zobecn�n�ch� obd�ln�k� �viz obr�zek ��� Zvol�me�li rozsahD /x�� x�0�/y�� y�0 a pohybujeme�li ka�d�m krajn�m bodem tohoto rozsahu �x�� y��� �x�� y�� uvnit� jednoho z v��e uveden�ch�n! ��� obd�ln�k�� v�sledek dotazu z�stane st�le stejn� M�me tedy celkem

�n! �

���n! �

� O�n��

mo�n�ch v�sledk� �vybereme v�dy z �n! �� p�s� na ka�d� z os� K jejich ulo�en� do pam�tije v�ak pot�eba O�n�� prostoru� proto�e v�sledky maj� d�lku O�n�Velikost pam�ti pot�ebn� pro proveden� dotazu se v�ak d� zmen�it Pro rozsahD /x�� x�0�

/y�� y�0 provedeme p��m� p��stup pouze ve sm�ru osy x Tak dostaneme ukazatel na vyhled�vac�strom v�ech bod� mno�iny S� kter� le�� v dan�m x�ov�m p�su� odpov�daj�c�m intervalu /x�� x��0na ose x Jin�mi slovy� pro ka�dou dvojici p�s�� kter�ch je n ! �� si pamatujeme vyhled�vac�strom v�ech bod� z S� kter� le�� mezi t�mito p�sy

��� Metoda p��m�ho p��stupu ��

e

e

ee

Obr ��" Rozd�len� roviny na �n ! ��� zobecn�n�ch obd�ln�k� horizont�ln�mi a vertik�ln�mip��mkami proch�zej�c�mi zadan�mi body

Provedeme nejd��ve normov�n� re�ln�ch sou�adnic na celo��seln� sou�adnice �� � � � � n� tznse�ad�me tyto sou�adnice podle velikosti a o��slujeme podle po�ad� Dostaneme pak v �aseO�log n� pro dan� interval dv� ��sla i� j � f�� � � � � n ! �g Dvojice �i� j� odpov�d� bin�rn�muvyhled�vac�mu stromu s �j i� listy Celkem pot�ebujeme pam�*

nXi �

n��Xj i��

�j i� �n! �� �n! ��

� O�n�

V�imn�me si� �e p�i radik�ln�m sn��en� pot�ebn� pam�ti �o dva ��dy�� z�stal zachov�n logarit�mick� vyhled�vac� �asDal��ho vylep�en� tohoto p��stupu se d� dos�hnout tzv kalibrac� Budeme vyhled�vat na ose

x postupn� ve dvou �rovn�ch Osa x bude rozd�lena tzv hrubou kalibrac� na intervaly� jejich�hrani�n�mi body z�st�vaj� x�ov� sou�adnice bod� mno�iny S� ale ne nutn� v�echny Jemnkalibrace n�m u� kone�n� rozd�l� ka�d� interval hrub� kalibrace na kone�n� intervaly P�ivyhled�v�n� podle zadan�ho intervalu /x�� x�0 takto dostaneme dvojici hrub�ch interval�� kter�jsou intervalem /x�� x�0 pln� pokryty� a dv� dvojice jemn�ch interval� po stran�ch krajn�chhrub�ch interval� Ka�d� dvojice hrub�ch interval� ukazuje na n�jak� vyhled�vac� strom� aka�d� dvojice jemn�ch interval� uvnit� jednoho hrub�ho intervalu ukazuje na sv�j vyhled�vac�strom bod� S obsa�en�ch v odpov�daj�c�ch p�sechNa obr�zku �� je zn�zorn�na kalibrace osmi bod�� rozd�len� na hrub� a jemn� intervaly�

a d�le hrub� i jemn� intervaly� zasa�en� dan�m rozsahem �ozna�eny � a � Obr�zek ilustrujespeci�ln� p��pad� kdy dvojice ur�en�ch interval� v obou kalibrac�ch spolu soused� Obecn� do�staneme v hrub� kalibraci n�jakou dvojici interval� a v jemn� jednu nebo dv� dvojice� v�dyuvnit� jednoho hrub�ho intervaluP�edpokl�dejme� �e hrub� kalibrace obsahuje n� interval� �� � � � �� M�me O�n���

mo�n�ch dvojic t�chto interval�� a ka�d� takov� dvojice ukazuje na strom o velikosti O�n�Pot�ebn� pam�* je tedy O�n����� Ka�d� rozd�len� hrub� jednotky m� n��� jemn�ch interval��hrub�ch jednotek je n� Pro ka�dou dvojici jemn�ch interval�� kter�ch je v ka�d�m hrub�mintervalu O�n�������� si pamatujeme vyhled�vac� strom o velikosti O�n���� Celkov� pam�* pro

�� � VYHLED*V*N� DLE ROZSAHU

ueueeueeu�

�Jemn+a kalibrace

Hrub+a kalibrace

Zadan+y interval

body na ose x

Obr ��" Kalibrace osmi bod� na ose a zasa�en� intervaly

jemnou kalibraci je tedy O�n���� Spolu s hrubou kalibrac� je pot�ebn� prostor dohromady

O�n����� !O�n����

Minima dos�hneme pro � �� �tedy hrub�ch interval� jepn� stejn� jako jemn�ch uvnit�

ka�d�ho hrub�ho�� a toto minimum je O�n�� #asov� se nic nezm�n�� pouze logaritmicky pro�ch�z�me t�i stromy za sebou �mus� b�t vyv��en��� proto �as je O�� log n� O�log n�Zvy�ujeme�li po�et �rovn� kalibrac� na k� vyjde v�dy optimum jako k

pn interval� na ka�d�

�rovni kalibrace� a v�sledn� prostor bude O�n����k� p�i zachov�n� logaritmick�ho �asu �� Tvrzen�� Pro ka�d� � " � � � � � lze vyhled�v�n� podle rozsahu v mno�in� n bod�v rovin� uskute nit v ase O�log n� p�i pam��ov� n�ro nosti O�n�����

�� Rozsahov� strom

Pro dal�� metodu budeme pot�ebovat datovou strukturu vhodnou pro dynamick� zpracov�v�n��se�ek s koncov�mi body v p�edem zn�m� �statick�� mno�in� hodnot Tato datov� strukturanach�z� velice rozmanit� uplatn�n�� my se s n� setk�me je�t� v p���t� kapitole Proto ji zavedemeobecn�ji� ne� budeme bezprost�edn� pot�ebovat

�� De�nice� Zn�me�li p�edem mno�inu koncov�ch bod� uva�ovan�ch �se�ek� zkonstruujemestrom �se�ek � kter� je ilustrov�n na obr�zku � M�me�li d�no n mo�n�ch koncov�ch bod��dostaneme pr�v� n � �se�ek� kter� u� neobsahuj� ��dn� dal�� koncov� body Tyto �se�ky jsoupr�v� listy konstruovan�ho stromu �se�ek Konstrukce stromu je z�ejm� z obr�zku

Strom �se�ek bude slou�it k uchov�v�n� �aplikac� po�adovan�ch� informac� o uva�ovan�ch�se�k�ch K pou�it� pot�ebujeme implementovat operace INSERT a DELETE slou��c� k vlo�en�a zru�en� p��slu�n� informace o dan� �se�ce Budeme stru�n� hovo�it o �alokov�n�� �se�ky vuzlech stromu

Algoritmus �� Operace INSERT na stromu �se�ek

Vstup� $se�ka �b� e� a ko�en v �se�kov�ho stromu s uzly u �B�u�� E�u��V�stup� Tent�� strom s alokovanou �se�kou �b� e�Vyvoln�� INSERT��b� e�� v�

� if b � B�v� and e � E�v� then

�� alokuj �b� e� k v

�� Rozsahov� strom ��

� � � � �

���

��

��

QQQQQ�����

��

���

��

��������������

���

AAA

��� ���

Obr �" Strom �se�ek pro normalizovanou sadu bod� na p��mce

else

� if b � b�B�v� ! E�v��� c then �� INSERT�b� e� LSON�v��

if b�B�v� ! E�v��� c � e then

� INSERT�b� e�RSON�v��

Tato procedura pracuje v �ase O�log n ! s�� kde s je �as pot�ebn� k alokaci pot�ebn�informace Zejm�na je z algoritmu patrn�� �e ka�d� vstupn� �se�ka �b� e� bude alokov�nav O�log�e b�� uzlech Podrobn�j�� rozbor ukazuje� �e interval �b� e� se rozlo�� na nejv��edlog�e b�e! blog�e b�c �se�ek� kter� jsou uzly v na�em stromu �se�ekProcedura DELETE je zcela shodn� s INSERT� a� na v�m�nu p��kazu �alokuj� v �� p���

kazem �zru� alokaci�

�� P��klad� Zpracov�n� rozsahov�ho dotazu na p��mce pak lze prov�st tak� �e rozsah �kter� jevlastn� �se�kou� zpracujeme procedurou INSERT pro strom �se�ek vytvo�en� pro zadan� bodymno�iny S V tomto p��pad� je v�znam p��kazu �alokuj� takov�� �e na v�stup d�me v�echnybody mno�iny S pat��c� do p��slu�n� �se�ky

Nyn� m��eme navrhnout dal�� metodu zpracov�n� rozsahov�ho dotazu� a to nad mno�inoubod� v prostoru libovoln� dimenze Pracujeme obecn� v d�dimenzion�ln�m prostoru a zpraco�v�v�me postupn� sou�adnice x�� � � � � xd Pro dimenzi d � de�nujeme rozsahov� strom jakostandardn� vyhled�vac� strom z p��kladu ��Pro d � de�nujeme rozsahov� strom jako strom �se�ek T � pro mno�inu bod� na p��mce

fx��p�% p � Sg Vzali jsme tedy v �vahu pouze prvn� sou�adnice bod� a normovali a vytvo�ili�se�kov� strom z p�edchoz� podkapitoly Do stromu se v�ak nebudou vkl�dat ��dn� �se�kyVzory interval� /B�v�� E�v�0 pro uzel v v projekci Rd � R dan� sou�adnic� x� ozna��me

Sd�v� Jsou to ty body� jejich� prvn� sou�adnice le�� v intervalu odpov�daj�c�m uzlu v� tedyv�echny body p � S takov�� �e B�v� � x��p� � E�v� Pro tyto body de�nujeme mno�inuSd���v� " f�x��p�� � � � � xd�p��% p � Sd�v�g bod� �d ���n� dimenze� kter� vzniknou z Sd�v�naopak odstran�n�m prvn�ch sou�adnic Uzel v d�le obsahuje ukazatel na rozsahov� stromv dimenzi �d �� pro mno�inu Sd���v�

�� � �LOHY O OBD"LN�C�CH

V�imn�me si� �e pro realizaci rozsahov�ho stromu bude pot�eba v�ce ne� line�rn� mnohopam�*ov�ho prostoru Rozsahov� strom ni��� dimenze se toti� konstruuje velice velkoryse Je�li nap� strom na obr�zku � prim�rn� strukturou rozsahov�ho stromu� pak bod odpov�daj�c�bodu � po normov�n� se objev� jako �d ���dimenzion�ln� bod v uzlech �� � ��� � ��� � ����je vhodn� m�t intervaly z jedn� strany otev�en� a z druh� zav�en�� zde jsme pou�ili zpravazav�en�� v opa�n�m p��pad� by se bod � objevil v uzlu ��� � Lze tedy zpozorovat pravidlo��e pro ka�d� bod najdeme pr�v� jednu cestu z ko�ene k listu stromu� pro ni� je v ka�d�mrozsahov�m stromu dimenze �d �� odpov�daj�c�m uzlu t�to cesty dan� bod obsa�enVyhled�v�n� prob�h� tak� �e ka�d� z alokovan�ch interval� pro sou�adnici x� vede k d�l��mu

�d ���rozm�rn�mu probl�mu Vezmeme tedy interval rozsahu odpov�daj�c� prvn� sou�adnici anajdeme v rozsahov�m stromu ty uzly� jejich� odpov�daj�c� intervaly /B�v�� E�v�0 jsou cel� v roz�sahov�m intervalu obsa�eny� a to z�rove� uzly nejv��e ve stromu� kter� t�to podm�nce vyhovuj�V nich pak �e��me stejn� probl�m o dimenzi ni��� V dimenzi � jde o probl�m z p��kladu ��Nech* Q�n� d� je vyhled�vac� �as pro n d�rozm�rn�ch bod� D�l��ch probl�m� je

Q�n� d� O�log n� !X

Q�n�v�� d ���

kde s��t�n� prob�h� p�es alokovan� uzly v a n�v� E�v� B�v� Alokovan�ch uzl� je m�n� ne� dlog ne a n�v� � n� proto m��eme aproximovat

Q�n� d� O�log n��Q�n� d ��

Q�n� �� O�log n� Q�n� d� O�logd n�

Podobnou �vahou odvod�me pot�ebnou pam�*

S�n� d� O�n logd�� n�

�� Vta� Pomoc� rozsahov�ch strom� lze rozsahov� dotaz v d�dimenz�ch zvl�dnout v aseO�logd n� a pam�ti O�n logd�� n��

��� Pozn�mka� S pou�it�m podobn� konstrukce jako v redukovan� vyhled�v�c� struktu�epou��van� k vyhled�v�n� v rovinn�ch rozd�len�ch �rozeb�r� podkapitola � � lze sn��it �aspot�ebn� pro algoritmus T�to technice se ��k� p�emos�ovn�� a spo��v� v p�id�n� jist�ch uka�zatel� mezi sekund�rn�mi stromy Viz pozn�mka ��� a /Preparata���0 Dos�hneme tak �asuO�logd�� n� p�i prostoru O�n logd�� n�

�lohy o obd�ln�c�ch

V aplikac�ch se �asto objevuj� �tvary� jejich� st�ny jsou kolm� na sou�adn� osy Hovo��me oisoortogonln�ch objektech V t�to kapitole se budeme zab�vat �lohami v rovin�� za�neme alena p��mce� tedy s �se�kami

��� M�ra sjednocen� �se�ek

M�me d�no n interval� /a�� b�0� � � � � /an� bn0 v R Chceme z�skat m�ru �tedy celkovou d�lku�jejich sjednocen�

��� M�ra sjednocen� obd�ln�k� ��

Uspo��d�me koncov� body �se�ek a budeme je postupn� proch�zet zleva doprava Budemev ka�d� chv�li v�d�t� uvnit� kolika �se�ek se nach�z�me V ka�d�m bod� zv���me nebo sn���metento po�et podle toho� zda jsme narazili na lev� nebo prav� koncov� bod Z�rove� uprav�mepr�b��nou m�ru� tedy p�i�teme vzd�lenost k dal��mu bodu� pokud budeme uvnit� alespo� jedn��se�kyAlgoritmus ��� M�ra sjednocen� interval�

Vstup� �se�ky /a�� b�0� � � � � /an� bn0 na p��mceV�stup� m�ra jejich sjednocen�

� �X���� � � � �X� n�� " uspo��dan� posloupnost po��te�n�ch a koncov�ch bod� �se�ek

X��� " X���

� M " �

C " �

� for i " � to n do

�� if C � � then M " M !X�i� X�i ��� if X�i� lev� konec then C " C ! � else C " C �

�asu dominuje krok ��slo �� tedy O�n log n�

��� M�ra sjednocen� obd�ln�k�

Stejnou �lohu nyn� �e��me pro obd�ln�ky v rovin�Pou�ijeme metodu pro�esvn� Pro�es�vac� p��mka bude vertik�ln� a budeme prostor pro�

ch�zet zleva doprava Zastavovat se budeme v krajn�ch bodech x�ov�ch interval� obd�ln�k�V ka�d�m takov�m bod� spo��t�me m�ru sjednocen� �se�ek� kter� protnou pro�es�vac� p��mku�a vyn�sobenou vzd�lenost� k dal��mu vrcholu ji p�i�teme k pr�b��n� po��tan� m��eP�i p�echodu od X�i �� k X�i� mus�me obnovit m�ru sjednocen� p��slu�n�ch interval� ve

sm�ru osy y P�i pro�es�v�n� lze jako statut ud�lost� s v�hodou pou��t �se�kov� strom z de�nice�� Procedury na stromu �se�ek si v�ak mus�me zprecizovat� tzn up�esnit zp�sob zachov�v�n�informace o m��e Nejprve tedy budeme de�novat operace na stromu �se�ek INSERT� UPDATE�DELETE

Globln� prom�nn�� C�v� � po�et �se�ek� kter� jsou alokov�ny% m�v� � p��sp�vek do m�ryprocedure INSERT�b� e� v�� if b � B�v� and E�v� � e then C�v� " C�v� ! �

else

�a� b � b�B�v� ! E�v��� c then INSERT�b� e� LSON�v���b� b�B�v� ! E�v��� c � e then INSERT�b� e�RSON�v��

� UPDATE�v�Procedura DELETE je du�ln� k INSERT� tj m�sto p�i��t�n� se jedni�ka ode��t�

procedure UPDATE�v�� if C�v� � � then m�v� " E�v� B�v�

else

� � �LOHY O OBD"LN�C�CH

�a� if v nen� list then m�v� " m�LSON�v�� !m�RSON�v���b� else m�v� " �

Hlavn� program bude vypadat takto"

Algoritmus ��� M�ra sjednocen� obd�ln�k�

Vstup� Mno�ina n iso�ortogon�ln�ch obd�ln�k�V�stup� M�ra jejich sjednocen�

� do �X���� � � � �X� n�� uspo��d�me posloupnost x�ov�ch sou�adnic bod�� v p��pad� rov�nosti spodn� p�ed vrchn� �tj v�etn� n�sobnost��

X��� " X���

� M " �

inicializuj �se�kov� strom T pro y�ov� sou�adnice bod�

� for i � to n do

�� m� " m�root�T ��� M " M !m� � �X�i� X�i ����� if X�i� je lev� bod then

��� INSERT�bi� ei� root�T ��� else�� DELETE�bi� ei� root�T ��

Proch�z�me O�n� bod�� v nich� prov�d�me logaritmick� operace na strom� �se�ek� tedy algo�ritmus prob�hne v �ase O�n log n�

Stoj� za pov�imnut�� �e pro obd�ln�ky jsme v ka�d�m bod� m�li vlastn� za �kol spo��tatm�ru sjednocen� n �se�ek� tedy �loha se n�m redukovala na probl�m o dimenzi ni��� Tentop��stup lze uplatnit v libovoln� dimenziPro objekty podobn� ortogon�ln�m obd�ln�k�m obecn� v Rd lze aplikovat pro�es�v�n� po�

stupn� ve v�ech dimenz�ch a� dojde na p��mku Nap� pro d � redukujeme �lohu na �e�en� nprobl�m� v R�� celkov� �as je tedy O�n� log n� D�ky t�to �vaze dost�v�me n�sleduj�c� v�tu��� Vta� M�ra sjednocen� iso�ortogon�ln�ch objekt� v Rd� d � � se d� spo �tat v aseO�nd�� log n�

��� Pozn�mka� Pro d � � to v�ak jde zvl�dnout v �ase O�nd��� pomoc� datov� strukturyzvan� quadtree � viz /Finkel��0

��� Obvod sjednocen� obd�ln�k�

Obvod sjednocen� obd�ln�k� �d�lka hranice� lze spo��tat stejnou metodou jako m�ru jejichsjednocen� Budeme op�t pou��vat strom �se�ek jako statut pro�es�vac� p��mky p�i pro�es�v�n��mus�me v�ak upravit n�kter� ��sti algoritmu tak� abychom dostali obvod m�sto m�ryVertik�ln� komponenty p�isp�vaj� p�i p�echodu od X�i �� k X�i� pr�v� d�lkoumi� pou�itou

u� v p�edchoz�m algoritmuNech* Pi je sjednocen� disjunktn�ch komponent statutu ud�lost� Po�et disjunktn�ch kompo�

nent v Pi vyn�soben� dv�ma ulo��m do parametru � K �dr�b� parametru � je t�eba parametr�LBD�v�� RBD�v�"

�� Uz�v�ry sjednocen� obd�ln�k� ��

LBD�v� � je�li B�v� doln� bod intervalu v /B�v�� E�v�0� PiLBD�v� � jinakRBD�v� � je�li E�v� horn� bod intervalu v /B�v�� E�v�0� PiRBD�v� � jinakAlgoritmus je velmi podobn� jako algoritmus na spo��t�n� m�ry sjednocen� obd�ln�k� �� ��

proto uvedeme pouze zm�ny v procedu�e UPDATE a hlavn�m programuprocedure UPDATE

� if C�v� � � then�a� ��v� " %m�v� " E�v� B�v�

�b� LBD�v� " �%RBD�v� " �

else if v nen� list tt then

�a� ��v� " ��LSON �v�� ! ��RSON �v�� �RBD�LSON �v�� � LBD�RSON �v���b� LBD�v� " LBD�LSON �v��

�c� RBD�v� " RBD�RSON �v��

�d� m�v� " m�LSON �v�� !m�RSON �v��

� else LBD�v� �� RBD�v� �� ��v� �� m�v� �

Algoritmus ��� Obvod sjednocen� obd�ln�k�

Vstup� Mno�ina n iso�ortogon�ln�ch obd�ln�k�V�stup� Obvod jejich sjednocen�

� do �X���� � � � �X� n�� uspo��d�me posloupnost x�ov�ch sou�adnic bod�� v p��pad� rov�nosti spodn� p�ed vrchn�

X��� " X���

� m� " �%P " �

inicializuj �se�kov� strom T pro y�ov� sou�adnice bod�

� for i � to n do

�� �� " ��root�T ��

� if X�i� je lev� bod then

� � INSERT�bi� ei� root�T ��

�� else

��� DELETE�bi� ei� root�T ��

� m� " m�root�T ��

�� P " �� � �X�i� X�i ��� ! jm� m�j! P

�� m� " m�

�as� p�i n zastaven�ch pro�es�vac� p��mky� kdy ka�d� spot�ebuje logaritmick� �as� dost�v�mecelkov� �as O�n log n�

� LITERATURA

e

u e

uqSW /x�� y�0 p� /x�� y�0

qNE /x�� y�0p� /x�� y�0

Obr �" SW a NE body k nesrovnateln� dvojici bod�

��� Uz�v�ry sjednocen� obd�ln�k�

��� De�nice� O bodech p� �x�� y��� p� �x�� y�� �ekneme� �e jsou neporovnateln�� jestli�e�x� x���y� y�� � �V takov�m p��pad� nazveme body qSW �x�� y�� a qNE �x�� y��� kde x� � x� a y� � y� �

SW �South�West� a NE �North�East� body k bod�m p�� p� �viz obr�zek ��

��� De�nice� Oblast R � R� je NE� �resp SW�� uzav�en�� jestli�e pro ka�d� dva neporov�nateln� body p�� p� � R le�� i jejich qNE �resp qSW � v R�� Vta� NE�� SW� i NE�SW�uz�v�r sjednocen� ortogon�ln�ch obd�ln�k� lze spo �tat v aseO�n log n��

D kaz� D� se naj�t algoritmus pou��vaj�c� op�t metodu pro�esvn� pracuj�c� v tomto �asePopisuje jej nap� /Preparata���0 �

SW�uz�v�r sjednocen� obd�ln�k� m� praktick� uplatn�n� v datab�z�ch

Literatura

/Mehlhorn��0 Kurt Mehlhorn� Data Structures and Algorithms� Springer Verlag� ���

/Preparata���0 Franco Preparata� Michael Shamos� Computational Geometry� Springer Ver�lag� ����

/R�nyi���0 A R�nyi� R Sulanke� 9Uber die konvexe Hulle von n zuf9allig gewahlten Punk�ten� I� Z� Wahrschein� � ����� ����

/Raynaud���0 H Raynaud� Sur l.enveloppe convexe des nuages des points al�atoires dansRn� I� J� Appl� Prob� �� ����� ����

/Chazelle���0 B M Chazelle� Optimal algorithms for computing depths and layers� Proc���st Allerton Conference on Comm�� Control and Comput�� ����� Oct����

/MIT0 Introduction to Algorithms� Chapter Minimum Spanning Trees

/Megiddo���0 N Megiddo� Linear time algorithm for linear programming in R and relatedproblems� SIAM J� Comput� � ��� �������� Nov ����

/Gilbert���0 P N Gilbert� New results on planar triangulations� Tech Rep ACT����Coord Sci Lab� University of Illinois at Urbana� July ����

LITERATURA ��

/Bentley���0 J L Bentley� Multidimensional binary search trees used for associative se�arching� Communications of the ACM ��� ������� ������

/Finkel��0 R A Finkel� J L Bentley� Quad�trees% a data structure for retrieval oncomposite keys� Acta Informatica � ��� �����


Recommended