Kirkpatrickin algoritmi

Kuperan rungon rakentaminen "jakaa ja hallitse" -menetelmällä - algoritmi kuperan rungon rakentamiseksi .

Kuvaus

Annettu joukko pisteitä . $S$ $N$

Jos ( on jokin pieni kokonaisluku), rakenna kupera runko jollakin tunnetuista menetelmistä ja lopeta, muussa tapauksessa siirry vaiheeseen 2. ${\displaystyle N\leq N_{0))$ $N_{0}$
Jaetaan alkuperäinen joukko mielivaltaisesti kahteen suunnilleen samankokoiseen osajoukkoon ja ( sisältää pisteitä ja sisältää pisteitä). $S$ $S_{1}$ $S_{2}$ $S_{1}$ $N/2$ $S_{2}$ $NN/2$
Etsi rekursiivisesti kunkin osajoukon kupera runko ja . $S_{1}$ $S_{2}$
Alkuperäisen joukon kupera runko rakennetaan kahden kuperan monikulmion ja yhdistelmän kuperaksi rungoksi . $CH(S_{1})$ $CH(S_{2})$

Koska: , tämän algoritmin monimutkaisuus on ratkaisu rekursiiviselle suhteelle , jossa on kahden kuperan monikulmion, joilla kullakin on lähellä kärkipisteitä , liiton kuperan rungon rakennusaika . Se näytetään seuraavaksi . $CH(S)=CH(S1\cup S2)=CH(CH(S_{1})\cup CH(S_{2}))$ $T(N)\leq 2T(N/2)+f(N)$ $f(N)$ $N/2$ $T(N)=O(N\log N)$

Määritelmät

Kuperaan monikulmion tukiviiva on viiva, joka kulkee polygonin jonkin kärjen kautta siten, että kaikki monikulmion sisäpisteet ovat samalla puolella suoraa . $P$ $l$ $P$ $l$

Kuperaan monikulmioon voit rakentaa tukiviivoja pisteestä , joka ei kuulu siihen. Käytämme sitä tosiasiaa, että viiva , jossa on jokin monikulmion kärki, on tukiviiva jos ja vain jos reunat ja sijaitsevat samassa puolitasossa, jonka rajaa tämä viiva. On helppo huomata, että pahimmassa tapauksessa monikulmion kärkien yksi läpikulku tarvitaan tukilinjojen rakentamiseen , eli niitä etsitään lineaarisessa ajassa. $P$ $A$ ${\displaystyle AP_{i))$ $P_{i}$ $P$ $P$ ${\näyttötyyli (P_{i-1}, P_{i})}$ ${\näyttötyyli (P_{i}, P_{i+1})}$ $P$

Toteutus

Olkoon meillä jo rakennettu kupera runko ja . $P_{1}$ ${\näyttötyyli P_{2))$

Etsitään jokin monikulmion sisäinen piste (esimerkiksi minkä tahansa kolmen kärjen painopiste ). Tällainen piste on sisäpiste . $A$ $P_{1}$ $P_{1}$ $A$ $CH(P_{1}\cup P_{2})$
Kaksi tapausta on mahdollista:
1. Piste ei ole polygonin sisäpiste . Piirretään kaksi vertailuviivaa pisteen läpi kulkevalle monikulmiolle . Nämä viiteviivat kulkevat kärkien ja monikulmion läpi . Kaikki kolmion sisällä olevat pisteet eivät kuulu kuperan rungon rajaan . Kaikki muut pisteet järjestetään napakulman mukaan suhteessa pisteeseen yhdistämällä kaksi järjestettyä kärkiluetteloa ajassa ja käyttämällä sitten Grahamin läpikulkumenetelmää tuloksena olevaan listaan , joka vaatii vain lineaarista aikaa. $A$ ${\näyttötyyli P_{2))$ ${\näyttötyyli P_{2))$ $A$ $B$ $C$ ${\näyttötyyli P_{2))$ $ABC$ $CH(P_{1}\cup P_{2})$ $A$ $O(N_{1})+O(N_{2})=O(N)$
2. Piste on polygonin sisäpiste . Järjestä molempien polygonien kärjet keskustan ympärillä yhdistämällä kaksi järjestettyä kärkiluetteloa ja sen jälkeen . $A$ ${\näyttötyyli P_{2))$ $A$ $P_{1}$ ${\näyttötyyli P_{2))$ $O(N)$
Nyt Grahamin algoritmia voidaan soveltaa tuloksena olevaan kärkilistaan, paitsi vaihe, jossa pisteet lajitellaan napakoordinaatin mukaan, sitten se suoritetaan lineaarisessa ajassa.

Nyt saadaan kupera monikulmioiden liiton kupera runko . $P_{1}\cup P_{2}$

Algoritmin monimutkaisuus

Kaiken kaikkiaan algoritmin kaikki kolme vaihetta valmistuvat ajallaan . Siten saadaan relaatio , jonka ratkaisu, kuten tiedetään , on , joka määrittää algoritmin monimutkaisuuden. $O(N)$ $f(N)=O(N)$ $T(N)\leq 2T(N/2)+O(N)$ $T(N)=O(N\log N)$

Linkit

http://www.cs.umd.edu/~samir/754/kshand.ps _