Overvej det generelle tilfælde, hvor algoritmens input er et endeligt uordnet sæt af punkter på et kartesisk plan. Et vigtigt specialtilfælde, hvor punkterne er givet i den rækkefølge, hvori de gennemløber en simpel polygons grænse, beskrives senere i et særskilt underafsnit.
Hvis ikke alle punkter ligger på den samme linje, er deres konvekse skrog et konvekst polygon, hvis hjørner er nogle af punkterne i inddatamængden. Dens mest almindelige repræsentation er en liste over dens toppunkter ordnet langs dens grænse med eller mod uret. I nogle anvendelser er det praktisk at repræsentere en konveks polygon som et skæringspunkt mellem et sæt halvplaner.
Nedre grænse for beregningskompleksitetRediger
For et endeligt sæt af punkter i planen er den nedre grænse for beregningskompleksiteten for at finde det konvekse skrog repræsenteret som en konveks polygon let at vise, at den er den samme som for sortering ved hjælp af følgende reduktion. For mængden x 1 , … , x n {\displaystyle x_{1},\dots ,x_{n}}
tal til sortering betragter man mængden af punkter ( x 1 , x 1 2 ) , … , ( x n , x n 2 ) {\displaystyle (x_{1},x_{1}^{2}),\dots ,(x_{n},x_{n}^{2})}
af punkter i planen. Da de ligger på en parabel, som er en konveks kurve, er det let at se, at hjørnerne af det konvekse skrog, når de passeres langs grænsen, giver den sorterede rækkefølge af tallene x 1 , … , x n {\displaystyle x_{1},\dots ,x_{n}}
. Det er klart, at der kræves lineær tid til den beskrevne omdannelse af tal til punkter og derefter til at udtrække deres sorterede rækkefølge. I det generelle tilfælde kan det konvekse skrog af n punkter derfor ikke beregnes hurtigere end sortering.
Standard Ω(n log n)-nedre grænse for sortering er bevist i beslutningstræ-modellen for databehandling, hvor der kun kan foretages numeriske sammenligninger, men ikke aritmetiske operationer; i denne model kan konvekse skrog imidlertid slet ikke beregnes. Sortering kræver også Ω(n log n)-tid i den algebraiske beslutningstræ-model for beregning, en model, der er mere velegnet til konvekse skrog, og i denne model kræver konvekse skrog også Ω(n log n)-tid. I modeller for computeraritmetik, der gør det muligt at sortere tal hurtigere end O(n log n)-tid, f.eks. ved hjælp af algoritmer til sortering af hele tal, kan plane konvekse skrog også beregnes hurtigere: Graham-scanningsalgoritmen for konvekse skrog består af et enkelt sorteringstrin efterfulgt af en lineær mængde yderligere arbejde.
Optimale output-følsomme algoritmerRediger
Som nævnt ovenfor er kompleksiteten af at finde et konvekse skrog som en funktion af inputstørrelsen n lavere begrænset af Ω(n log n). Kompleksiteten af nogle konvekse skrogalgoritmer kan imidlertid karakteriseres ved både inputstørrelse n og outputstørrelse h (antallet af punkter i skroget). Sådanne algoritmer kaldes output-sensitive algoritmer. De kan være asymptotisk mere effektive end Θ(n log n)-algoritmer i tilfælde, hvor h = o(n).
Den nedre grænse for den værst tænkelige løbetid for outputfølsomme konvekse skrogalgoritmer blev fastlagt til at være Ω(n log h) i det plane tilfælde. Der findes flere algoritmer, som opnår denne optimale tidskompleksitet. Den tidligste blev introduceret af Kirkpatrick og Seidel i 1986 (som kaldte den “den ultimative konvekse skrogalgoritme”). En meget enklere algoritme blev udviklet af Chan i 1996 og kaldes Chans algoritme.
AlgoritmerRediger
Kendte konvekse skrogalgoritmer er anført nedenfor, ordnet efter datoen for den første offentliggørelse. Tidskompleksiteten for hver algoritme er angivet i form af antallet af indgangspunkter n og antallet af punkter på skroget h. Bemærk, at h i værste tilfælde kan være lige så stort som n.
- Gift wrapping, a.k.a. Jarvis march – O(nh)
En af de enkleste (om end ikke den mest tidseffektive i værste tilfælde) planar-algoritmer. Udviklet uafhængigt af hinanden af Chand & Kapur i 1970 og R. A. Jarvis i 1973. Den har O(nh) tidskompleksitet, hvor n er antallet af punkter i mængden, og h er antallet af punkter i skroget. I værste tilfælde er kompleksiteten Θ(n2). - Graham scan – O(n log n)
En lidt mere sofistikeret, men meget mere effektiv algoritme, offentliggjort af Ronald Graham i 1972. Hvis punkterne allerede er sorteret efter en af koordinaterne eller efter vinklen i forhold til en fast vektor, tager algoritmen O(n) tid. - Quickhull
Uafhængigt af hinanden udarbejdet i 1977 af W. Eddy og i 1978 af A. Bykat. Ligesom quicksort-algoritmen har den en forventet tidskompleksitet på O(n log n), men kan degenerere til O(n2) i værste tilfælde. - Divide and conquer – O(n log n)
En anden O(n log n)-algoritme, offentliggjort i 1977 af Preparata og Hong. Denne algoritme kan også anvendes i det tredimensionelle tilfælde. - Monoton kæde, også kendt som Andrews algoritme – O(n log n)
Udgivet i 1979 af A. M. Andrew. Algoritmen kan ses som en variant af Graham scan, der sorterer punkterne leksikografisk efter deres koordinater. Når input allerede er sorteret, tager algoritmen O(n) tid. - Incremental convex hull algorithm – O(n log n)
Publiceret i 1984 af Michael Kallay. - Kirkpatrick-Seidel-algoritme – O(n log h)
Den første optimale output-sensitive algoritme. Den modificerer divide and conquer-algoritmen ved at anvende teknikken “marriage-before-conquest” og lavdimensionel lineær programmering. Udgivet af Kirkpatrick og Seidel i 1986. - Chans algoritme – O(n log h)
En enklere optimal outputfølsom algoritme, der blev skabt af Chan i 1996. Den kombinerer gaveindpakning med udførelse af en O(n log n)-algoritme (såsom Graham scan) på små delmængder af input.
Akl-Toussaint heuristikRediger
Følgende simple heuristik anvendes ofte som det første trin i implementeringer af konvekse skrogalgoritmer for at forbedre deres ydeevne. Den er baseret på Selim Akl og G. T. Toussaint’s effektive konvekse skrogalgoritme fra 1978. Ideen er hurtigt at udelukke mange punkter, som alligevel ikke ville være en del af det konvekse skrog. Denne metode er baseret på følgende idé. Find de to punkter med de laveste og højeste x-koordinater og de to punkter med de laveste og højeste y-koordinater. (Hver af disse operationer tager O(n).) Disse fire punkter danner en konveks firkant, og alle punkter, der ligger i denne firkant (bortset fra de fire oprindeligt valgte toppunkter), er ikke en del af det konvekse skrog. At finde alle disse punkter, der ligger i denne firekant, er også O(n), og dermed er hele operationen O(n). Eventuelt kan punkterne med de mindste og største summer af x- og y-koordinater samt punkterne med de mindste og største forskelle af x- og y-koordinater også tilføjes til firkanten, hvorved der dannes en uregelmæssig konveks ottekant, hvis indersider kan kasseres uden risiko. Hvis punkterne er tilfældige variabler, vil dette bortkastede forbehandlingstrin for en snæver, men almindeligt forekommende klasse af sandsynlighedsdensitetsfunktioner få en konveks skrogalgoritme til at køre på lineær forventet tid, selv om den konvekse skrogalgoritmes værst tænkelige kompleksitet er kvadratisk i n.
On-line og dynamiske konvekse skrogproblemerRediger
Den ovenstående diskussion omhandler det tilfælde, hvor alle inputpunkter er kendt på forhånd. Man kan overveje to andre indstillinger.
- Online konvekse skrogproblem: Indgangspunkterne fås sekventielt et ad gangen. Efter hvert punkt ankommer på input, skal det konvekse skrog for den hidtil opnåede punktmængde beregnes effektivt.
- Dynamisk vedligeholdelse af det konvekse skrog: Indgangspunkterne kan indsættes eller slettes sekventielt, og det konvekse skrog skal opdateres efter hver indsættelse/sletning.
Indsættelse af et punkt kan højst øge antallet af hjørner i et konvekse skrog med 1, mens sletning kan omdanne et konvekse skrog med n hjørner til et skrog med n-1 hjørner.
Online-versionen kan håndteres med O(log n) pr. punkt, hvilket er asymptotisk optimalt. Den dynamiske version kan håndteres med O(log2 n) pr. operation.
Simple polygonEdit
Det konvekse skrog af en simpel polygon er opdelt af polygonen i stykker, hvoraf det ene er selve polygonen, og resten er lommer afgrænset af et stykke af polygonens afgrænsning og en enkelt skrogkant. Selv om der er blevet offentliggjort mange algoritmer for problemet med at konstruere det konvekse skrog af en simpel polygon, er næsten halvdelen af dem ukorrekte. McCallum og Avis leverede den første korrekte algoritme. en senere forenkling af Graham & Yao (1983) og Lee (1983) anvender kun en enkelt stak datastruktur. Deres algoritme gennemgår polygonen med uret og starter fra det yderste venstre hjørne. I den forbindelse lagrer den en konveks sekvens af toppunkter på stakken, nemlig dem, der endnu ikke er blevet identificeret som værende inden for lommer. Ved hvert trin følger algoritmen en sti langs polygonen fra toppen af stakken til det næste toppunkt, som ikke befinder sig i en af de to lommer, der støder op til toppen af stakken. Så længe de to øverste to toppunkter på stakken sammen med dette nye toppunkt ikke er i konveks position, springer den ud af stakken, før den endelig skubber det nye toppunkt ind på stakken. Når den med uret gennemløbet når frem til startpunktet, returnerer algoritmen sekvensen af stakkens toppunkter som skellet.