Algorytm Chana
W geometrii obliczeniowej The algorytm Chan pochodzi od jej wynalazcy Timothy M. Chan (en) reaguje z algorytmem wyjściowego oblicza wypukłej zbioru z punktów w 2D lub 3. Złożoność czasowa jest gdzie jest liczbą punktów wypukły kadłub. W wymiarze 2 algorytm łączy algorytm w (na przykład ścieżkę Grahama ) i spacer Jarvisa w celu uzyskania algorytmu w . Algorytm Chana jest ważny, ponieważ jest prostszy niż algorytm Kirkpatricka-Seidela i łatwo rozszerza się do wymiaru 3. Paradygmat użyty w algorytmie opiera się na pracy Franka Nielsena.
P{\ styl wyświetlania P}
nie{\ styl wyświetlania n}
O(nielogh){\ displaystyle {\ mathcal {O}} (n \ log h)}
h{\ styl wyświetlania h}
O(nielognie){\ displaystyle {\ mathcal {O}} (n \ log n)}
O(nielogh){\ displaystyle {\ mathcal {O}} (n \ log h)}![{\ displaystyle {\ mathcal {O}} (n \ log h)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a9470a317308c81039cf1f67c67273fee318e81d)
Algorytm
Wersja, w której znana jest liczba punktów h w obwiedni wypukłej
Najpierw przedstawiamy algorytm, który wykorzystuje wartość i nazywamy ten parametr . To założenie nie jest realistyczne i później je usuniemy. Algorytm podzielony jest na dwie fazy.
h{\ styl wyświetlania h}
m=h{\ styl wyświetlania m = h}![{\ styl wyświetlania m = h}](https://wikimedia.org/api/rest_v1/media/math/render/svg/83027e6ec2f7c7af6c516d4ac76d0af7f27addc4)
Faza 1: wstępne obliczenie obwiedni wypukłych dla podzbiorów
Algorytm rozpoczyna się od podziału na co najwyżej podzbiorów z co najwyżej punktami w każdym podzbiorze. Następnie obliczamy wypukłą kadłub każdego z podzbiorów za pomocą algorytmu (na przykład ścieżki Grahama ). Zauważ, że ponieważ każdy z nich ma podzbiory punktów, ta faza wymaga operacji.
P{\ styl wyświetlania P}
1+nie/m{\ styl wyświetlania 1 + n / m}
Q{\ styl wyświetlania Q}
m{\ styl wyświetlania m}
Q{\ styl wyświetlania Q}
O(nielognie){\ displaystyle {\ mathcal {O}} (n \ log n)}
O(nie/m){\ styl wyświetlania {\ matematyczny {O}} (n / m)}
O(m){\ displaystyle {\ matematyczne {O}} (m)}
O(nie/m)O(mlogm)=O(nielogm){\ displaystyle {\ mathcal {O}} (n / m) {\ mathcal {O}} (m \ log m) = {\ mathcal {O}} (n \ log m)}![{\ displaystyle {\ mathcal {O}} (n / m) {\ mathcal {O}} (m \ log m) = {\ mathcal {O}} (n \ log m)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/30a95ede53589f45d3e042a8c3c8247f41d4b8ea)
Faza 2: obliczenie wypukłej obwiedni
Druga faza polega na wykonaniu spaceru Jarvisa przy użyciu wypukłych obwiedni obliczonych wstępnie w fazie 1, aby przyspieszyć obliczenia. Na każdym etapie spaceru Jarvisa rozważamy punkt obwiedni wypukłej i staramy się obliczyć punkt w taki sposób, aby wszystkie pozostałe punkty znajdowały się na prawo od prostej . Jeśli kadłub wypukły jest znany z punktów, to można go obliczyć za pomocą przeszukiwania dychotomizującego . Obliczamy dla wszystkich podzbiorów fazy 1 w . Następnie określamy tę samą technikę, jak w przypadku spaceru Jarvisa, ale biorąc pod uwagę tylko punkty, w których znajduje się podzbiór fazy 1. Ponieważ spacer Jarvisa powtarza obliczenia raz, druga faza wykonuje operacje. Tak , podejmuje operacje.
pja{\ styl wyświetlania p_ {i}}
pja+1=fa(pja,P){\ displaystyle p_ {i + 1} = f (p_ {i}, P)}
P{\ styl wyświetlania P}
pjapja+1{\ displaystyle p_ {i} p_ {i + 1}}
Q{\ styl wyświetlania Q}
m{\ styl wyświetlania m}
fa(pja,Q){\ styl wyświetlania f (p_ {i}, Q)}
O(logm){\ displaystyle {\ mathcal {O}} (\ log m)}
fa(pja,Q){\ styl wyświetlania f (p_ {i}, Q)}
O(nie/m){\ styl wyświetlania {\ matematyczny {O}} (n / m)}
Q{\ styl wyświetlania Q}
O(nie/mlogm){\ displaystyle {\ mathcal {O}} (n / m \ log m)}
fa(pja,P){\ styl wyświetlania f (p_ {i}, P)}
fa(pja,Q){\ styl wyświetlania f (p_ {i}, Q)}
Q{\ styl wyświetlania Q}
fa(pja,P){\ styl wyświetlania f (p_ {i}, P)}
O(h){\ displaystyle {\ matematyczne {O}} (h)}
O(nielogm){\ displaystyle {\ mathcal {O}} (n \ log m)}
m=h{\ styl wyświetlania m = h}
O(nielogh){\ displaystyle {\ mathcal {O}} (n \ log h)}![{\ displaystyle {\ mathcal {O}} (n \ log h)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a9470a317308c81039cf1f67c67273fee318e81d)
Algorytm gdzie h nie jest znany
Opisany wcześniej algorytm wykorzystuje . Tak , zdajemy sobie z tego sprawę w spacerze Jarvisa pod koniec etapów. Tak więc, trzeba to zrealizować (a wypukłej obwiedni oblicza się dopiero do końca). Tak , również zdajemy sobie z tego sprawę, ponieważ algorytm zatrzymuje się i oblicza wypukłą obwiednię.
m=h{\ styl wyświetlania m = h}
m<h{\ styl wyświetlania m <h}
m+1{\ styl wyświetlania m + 1}
m<h{\ styl wyświetlania m <h}
O(nielogm){\ displaystyle {\ mathcal {O}} (n \ log m)}
m>h{\ styl wyświetlania m> h}![{\ styl wyświetlania m> h}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2bd3222cf31191d54db3416aba2d88e8c55ff8d3)
Chodzi o to, aby rozpocząć algorytm od małej wartości for (w poniższej analizie używamy 2, ale w praktyce najlepiej sprawdzają się liczby w okolicy 5), a następnie zwiększyć wartość until , w tym przypadku otrzymujemy wypukłą obwiednię.
m{\ styl wyświetlania m}
m{\ styl wyświetlania m}
m>h{\ styl wyświetlania m> h}![{\ styl wyświetlania m> h}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2bd3222cf31191d54db3416aba2d88e8c55ff8d3)
Jeśli zbyt wolno zwiększamy wartość , musimy powtórzyć fazę 1 i 2 zbyt wiele razy, a czas wykonania jest zbyt długi. I odwrotnie, jeśli zwiększymy wartości zbyt szybko, ryzykujemy osiągnięcie wartości, która jest zbyt duża w porównaniu do , a czas wykonania jest zbyt długi. Podobnie do strategii stosowanej w algorytmie Chazelle'a i Matouška, algorytm Chana podbija wartość do kwadratu w każdej iteracji bez przekraczania . Innymi słowy przyjmuje wartości 2, 4, 16, 256 itd. a przy numerze iteracji (zaczynając od 0) mamy . Całkowity czas wykonania algorytmu wynosi
m{\ styl wyświetlania m}
m{\ styl wyświetlania m}
m{\ styl wyświetlania m}
h{\ styl wyświetlania h}
m{\ styl wyświetlania m}
nie{\ styl wyświetlania n}
m{\ styl wyświetlania m}
t{\ styl wyświetlania t}
m=min(nie,22t){\ styl wyświetlania m = \ min (n, 2 ^ {2 ^ {t}})}![{\ styl wyświetlania m = \ min (n, 2 ^ {2 ^ {t}})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/02659da504676646143ef9f6183764591ced962d)
Σt=0⌈loglogh⌉O(nielog(22t))=O(nie)Σt=0⌈loglogh⌉O(2t)=O(nie⋅21+⌈loglogh⌉)=O(nielogh).{\ displaystyle \ suma _ {t = 0} ^ {\ lceil \ log \ log h \ rceil} {\ matematyczne {O}} \ po lewej (n \ log (2 ^ {2 ^ {t}}) \ po prawej) = {\ mathcal {O}} (n) \ suma _ {t = 0} ^ {\ lceil \ log \ log h \ rceil} O (2 ^ {t}) = {\ mathcal {O}} \ lewo ( n \ cdot 2 ^ {1+ \ lceil \ log \ log h \ rceil} \ right) = {\ mathcal {O}} (n \ log h).}
W wymiarze 3
Aby uogólnić algorytm w wymiarze 3, należy użyć innego algorytmu zamiast spaceru Grahama i użyć wersji 3D spaceru Jarvisa. Złożoność czasowa pozostaje w .
O(nielognie){\ displaystyle {\ mathcal {O}} (n \ log n)}
O(nielogh){\ displaystyle {\ mathcal {O}} (n \ log h)}![{\ displaystyle {\ mathcal {O}} (n \ log h)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a9470a317308c81039cf1f67c67273fee318e81d)
Ulepszenia
W artykule Chana znajduje się kilka sugestii, które mogą poprawić działanie algorytmu w praktyce:
- Obliczając wypukłe obwiednie podzbiorów, możemy wyeliminować punkty, które nie znajdują się w wypukłej obwiedni dla innych iteracji.
- Gdy wzrasta, możemy obliczyć nowe obwiednie wypukłe, scalając poprzednie obwiednie wypukłe, zamiast przeliczać je od zera.m{\ styl wyświetlania m}
![m](https://wikimedia.org/api/rest_v1/media/math/render/svg/0a07d98bb302f3856cbabc47b2b9016692e3f7bc)
Rozszerzenia
Artykuł Chana zawiera inne kwestie, które można uwrażliwić na dane wyjściowe przy użyciu tej samej techniki, na przykład:
- Oblicz krzywą minimalną ( dolną obwiednię ) zestawu segmentów. Hershberger podaje algorytm, w którym można poprawić o , gdzie jest liczba segmentów na krzywej minimum.nie{\ styl wyświetlania n}
O(nielognie){\ displaystyle {\ mathcal {O}} (n \ log {} n)}
O(nielogh){\ displaystyle {\ mathcal {O}} (n \ log {} h)}
h{\ styl wyświetlania h}![h](https://wikimedia.org/api/rest_v1/media/math/render/svg/b26be3e694314bc90c3215047e4a2010c6ee184a)
- Oblicz wypukłą kopertę w wyższym wymiarze. Możemy zachować złożoność w if pozostaje wielomianem w .O(nielogh){\ displaystyle {\ mathcal {O}} (n \ log {} h)}
h{\ styl wyświetlania h}
nie{\ styl wyświetlania n}![nie](https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b)
Bibliografia
-
(w) Timothy M. Chan , „ Optymalne algorytmy zależne od wyników, wypukły kadłub w dwóch i trzech wymiarach ” , Geometria dyskretna i obliczeniowa , tom. 16,1996, s. 361-368 ( prezentacja online )
-
(w :) Frank Nielsen , „ Grupowanie i zapytania: paradygmat uzyskiwania algorytmów wrażliwych na dane wyjściowe ” , „ Geometria dyskretna i obliczeniowa” , tom. 1763,2000, s. 250–257 ( prezentacja online ).
-
Frank Nielsen, „ Adaptacyjne algorytmy geometryczne ” , na INRIA ,1996, Praca doktorska.
-
B. Chazelle i Jiří Matoušek , „ Derandomizing algorytmu wypukłego kadłuba wrażliwego na dane wyjściowe w trzech wymiarach ”, Geometria obliczeniowa , t. 5,1995, s. 27-32 ( prezentacja online ).
-
(w) J. Hershberger , „ Znalezienie górnej obwiedni n odcinków linii w czasie O (n log n) ” , Listy przetwarzania informacji , tom. 33,1989, s. 169-174 ( prezentacja online ).
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">