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
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
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��
��
���
��������
���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 ����