Beschouw het algemene geval waarin de invoer van het algoritme een eindige ongeordende verzameling punten op een cartesisch vlak is. Een belangrijk speciaal geval, waarin de punten worden gegeven in de volgorde waarin ze de rand van een eenvoudige veelhoek doorkruisen, wordt verderop in een aparte subsectie beschreven.
Als niet alle punten op dezelfde lijn liggen, dan is hun convexe schil een convexe veelhoek waarvan de hoekpunten enkele punten uit de invoerverzameling zijn. De meest gebruikelijke voorstelling is de lijst van de hoekpunten, gerangschikt langs de rand met de klok mee of tegen de klok in. In sommige toepassingen is het handig om een convexe veelhoek voor te stellen als een snijpunt van een verzameling halve vlakken.
Ondergrens aan de computationele complexiteitEdit
Voor een eindige verzameling punten in het vlak is de ondergrens aan de computationele complexiteit van het vinden van de convexe schil voorgesteld als een convexe veelhoek gemakkelijk aan te tonen hetzelfde als voor sorteren met behulp van de volgende reductie. Voor de verzameling x 1 , … , x n {{1},x_{n}}
getallen te sorteren beschouw je de verzameling punten ( x 1 , x 1 2 ) , … , ( x n , x n 2 ) {\displaystyle (x_{1},x_{1}^{2}),\dots ,(x_{n},x_{n}^{2})}
van punten in het vlak. Aangezien zij op een parabool liggen, die een convexe kromme is, is het gemakkelijk in te zien dat de hoekpunten van de convexe schil, wanneer zij langs de rand worden doorkruist, de gesorteerde volgorde van de getallen x 1 , … , x n {{1},\dots,x_{n}}
. Het is duidelijk dat lineaire tijd nodig is voor de beschreven transformatie van getallen in punten en vervolgens voor het extraheren van hun gesorteerde volgorde. Daarom kan in het algemene geval de convexe schil van n punten niet sneller worden berekend dan sorteren.
De standaard Ω(n log n) ondergrens voor sorteren is bewezen in het beslissingsboommodel van rekenen, waarin alleen numerieke vergelijkingen maar geen rekenkundige bewerkingen kunnen worden uitgevoerd; in dit model kunnen convexe schillen echter helemaal niet worden berekend. Sorteren vergt ook Ω(n log n) tijd in het algebraïsche beslisboommodel van rekenen, een model dat geschikter is voor convexe hulls, en in dit model vergen convexe hulls ook Ω(n log n) tijd. Echter, in rekenmodellen voor computers waarmee getallen sneller dan O(n log n) tijd gesorteerd kunnen worden, bijvoorbeeld met behulp van integer sorteeralgoritmen, kunnen ook planaire convexe hulls sneller berekend worden: het Graham-scanalgoritme voor convexe hulls bestaat uit een enkele sorteerstap gevolgd door een lineaire hoeveelheid extra werk.
Optimale outputgevoelige algoritmenEdit
Zoals gezegd is de complexiteit van het vinden van een convexe romp als functie van de ingangsgrootte n lager begrensd door Ω(n log n). De complexiteit van sommige convexhullalgoritmen kan echter worden gekarakteriseerd in termen van zowel de inputgrootte n als de outputgrootte h (het aantal punten in de hull). Dergelijke algoritmen worden output-gevoelige algoritmen genoemd. Zij kunnen asymptotisch efficiënter zijn dan Θ(n log n) algoritmen in gevallen waarin h = o(n).
De ondergrens van de slechtst denkbare looptijd van output-gevoelige convex-romp-algoritmen werd vastgesteld op Ω(n log h) in het vlakke geval. Er zijn verschillende algoritmen die deze optimale tijdcomplexiteit bereiken. Het vroegste algoritme werd in 1986 geïntroduceerd door Kirkpatrick en Seidel (die het “het ultieme convex-rompalgoritme” noemden). Een veel eenvoudiger algoritme is ontwikkeld door Chan in 1996, en wordt Chan’s algoritme genoemd.
AlgoritmenEdit
Bekende convex-romp algoritmen staan hieronder opgesomd, gerangschikt naar de datum van eerste publicatie. De tijdcomplexiteit van elk algoritme is vermeld in termen van het aantal invoerpunten n en het aantal punten op de romp h. Merk op dat in het slechtste geval h even groot kan zijn als n.
- Gift wrapping, a.k.a. Jarvis mars – O(nh)
Een van de eenvoudigste (hoewel niet de meest tijdsefficiënte in het slechtste geval) planaire algoritmen. Onafhankelijk gecreëerd door Chand & Kapur in 1970 en R. A. Jarvis in 1973. Het heeft O(nh) tijdcomplexiteit, waarbij n het aantal punten in de verzameling is, en h het aantal punten in de romp. In het slechtste geval is de complexiteit Θ(n2). - Graham scan – O(n log n)
Een iets verfijnder, maar veel efficiënter algoritme, gepubliceerd door Ronald Graham in 1972. Als de punten al gesorteerd zijn op een van de coördinaten of op de hoek met een vaste vector, dan neemt het algoritme O(n) tijd. - Quickhull
Onafhankelijk gecreëerd in 1977 door W. Eddy en in 1978 door A. Bykat. Net als het quicksort-algoritme heeft het de verwachte tijdcomplexiteit van O(n log n), maar het kan in het ergste geval ontaarden in O(n2). - Verdeel en heers – O(n log n)
Een ander O(n log n) algoritme, in 1977 gepubliceerd door Preparata en Hong. Dit algoritme is ook van toepassing op het driedimensionale geval. - Monotone keten, ook bekend als Andrew’s algoritme- O(n log n)
Gepubliceerd in 1979 door A. M. Andrew. Het algoritme kan worden gezien als een variant van Graham scan die de punten lexicografisch sorteert op hun coördinaten. Als de invoer al gesorteerd is, neemt het algoritme O(n) tijd in beslag. - Incremental convex hull algoritm – O(n log n)
In 1984 gepubliceerd door Michael Kallay. - Kirkpatrick-Seidel algoritme – O(n log h)
Het eerste optimale output-gevoelige algoritme. Het wijzigt het verdeel-en-heers algoritme door gebruik te maken van de techniek van huwelijk-voor-verovering en laag-dimensionale lineaire programmering. Gepubliceerd door Kirkpatrick en Seidel in 1986. - Chan’s algoritme – O(n log h)
Een eenvoudiger optimaal output-gevoelig algoritme gemaakt door Chan in 1996. Het combineert gift wrapping met de uitvoering van een O(n log n) algoritme (zoals Graham scan) op kleine deelverzamelingen van de invoer.
Akl-Toussaint heuristicEdit
De volgende eenvoudige heuristiek wordt vaak gebruikt als de eerste stap in implementaties van convex hull algoritmen om hun prestaties te verbeteren. Het is gebaseerd op het efficiënte convexe-romp algoritme van Selim Akl en G.T. Toussaint, 1978. Het idee is om snel veel punten uit te sluiten die toch geen deel zouden uitmaken van de convexe romp. Deze methode is gebaseerd op het volgende idee. Zoek de twee punten met de laagste en hoogste x-coördinaten, en de twee punten met de laagste en hoogste y-coördinaten. (Elk van deze bewerkingen vergt O(n).) Deze vier punten vormen een convexe vierhoek, en alle punten die in deze vierhoek liggen (behalve de vier oorspronkelijk gekozen hoekpunten) maken geen deel uit van de convexe schil. Het vinden van al deze punten die in deze vierhoek liggen is ook O(n), en dus is de hele operatie O(n). Eventueel kunnen ook de punten met de kleinste en grootste som van x- en y-coördinaten en die met de kleinste en grootste verschillen van x- en y-coördinaten aan de vierhoek worden toegevoegd, en zo een onregelmatige convexe achthoek vormen, waarvan de binnenkanten veilig kunnen worden weggegooid. Als de punten willekeurige variabelen zijn, dan zal voor een kleine maar veel voorkomende klasse van kansdichtheidsfuncties, deze wegwerp voorbewerkingsstap een convex-romp algoritme laten lopen in lineaire verwachte tijd, zelfs als de worst-case complexiteit van het convex-romp algoritme kwadratisch is in n.
On-line en dynamische convex-romp problemenEdit
De discussie hierboven beschouwt het geval waarin alle invoerpunten van tevoren bekend zijn. Men kan twee andere instellingen overwegen.
- Online convex hull probleem: Invoerpunten worden achtereenvolgens een voor een verkregen. Nadat elk punt op de invoer is aangekomen, moet de convexe schil voor de tot dan toe verkregen puntenverzameling efficiënt worden berekend.
- Dynamisch convexe-romp onderhoud: De inputpunten kunnen opeenvolgend worden ingevoegd of verwijderd, en de convexe schil moet na elke invoeg/verwijderoperatie worden bijgewerkt.
Invoeging van een punt kan het aantal hoekpunten van een convexe schil met hoogstens 1 doen toenemen, terwijl verwijdering een convexe schil met n hoekpunten kan omzetten in een convexe schil met n-1 hoekpunten.
De online versie kan worden afgehandeld met O(log n) per punt, wat asymptotisch optimaal is. De dynamische versie kan worden afgehandeld met O(log2 n) per operatie.
Eenvoudige veelhoekEdit
De convexe schil van een eenvoudige veelhoek wordt door de veelhoek verdeeld in stukken, waarvan er één de veelhoek zelf is en de rest vakken zijn begrensd door een stuk van de veelhoeksgrens en een enkele rand van de schil. Hoewel er veel algoritmen zijn gepubliceerd voor het probleem van het construeren van de convexe romp van een eenvoudige veelhoek, is bijna de helft daarvan onjuist.McCallum en Avis leverden het eerste juiste algoritme.Een latere vereenvoudiging door Graham & Yao (1983) en Lee (1983) gebruikt slechts een enkele stapel-datastructuur. Hun algoritme doorkruist de veelhoek met de klok mee, beginnend bij het meest linkse hoekpunt. Daarbij slaat het een convexe reeks hoekpunten op de stapel op, de hoekpunten waarvan nog niet is vastgesteld dat ze binnen de pockets vallen. Bij elke stap volgt het algoritme een pad langs de veelhoek vanaf de top van de stapel naar het volgende hoekpunt dat niet in een van de twee pockets naast de top van de stapel ligt. Dan, zolang de bovenste twee hoekpunten op de stapel samen met dit nieuwe hoekpunt niet in convexe positie zijn, popt het de stapel, alvorens tenslotte het nieuwe hoekpunt op de stapel te duwen. Wanneer de traverse met de klok mee het beginpunt bereikt, geeft het algoritme de volgorde van de stapeltelpunten terug als de romp.