Observera det allmänna fallet när algoritmens indata är en ändlig oordnad mängd punkter på ett kartesiskt plan. Ett viktigt specialfall, där punkterna ges i den ordning i vilken de genomkorsar en enkel polygons gräns, beskrivs senare i ett separat underavsnitt.
Om inte alla punkter ligger på samma linje är deras konvexa skrov en konvex polygon vars hörn är några av punkterna i inmatningsmängden. Den vanligaste representationen är en lista över dess hörn ordnade längs gränsen medurs eller moturs. I vissa tillämpningar är det lämpligt att representera en konvex polygon som en skärningspunkt mellan en uppsättning halvplan.
Nedre gräns för beräkningskomplexitetRedigera
För en ändlig uppsättning punkter i planet kan den nedre gränsen för beräkningskomplexiteten för att hitta det konvexa höljet som representeras som en konvex polygon lätt visas vara densamma som för sortering med hjälp av följande reduktion. För mängden x 1 , … , x n {\displaystyle x_{1},\dots ,x_{n}}
tal att sortera anser man att mängden punkter ( x 1 , x 1 2 ) , … , ( x n , x n 2 ) {\displaystyle (x_{1},x_{1}^{2}),\dots ,(x_{n},x_{n}^{2})}
av punkter i planet. Eftersom de ligger på en parabel, som är en konvex kurva, är det lätt att se att det konvexa skrovets hörn, när man går längs gränsen, ger den sorterade ordningen av talen x 1 , … , x n {\displaystyle x_{1},\dots ,x_{n}}
. Det är uppenbart att det krävs linjär tid för den beskrivna omvandlingen av tal till punkter och för att sedan extrahera deras sorterade ordning. I det allmänna fallet kan därför det konvexa höljet av n punkter inte beräknas snabbare än sortering.
Den nedre standardgränsen Ω(n log n) för sortering är bevisad i beslutsträdsmodellen för databehandling, där endast numeriska jämförelser men inte aritmetiska operationer kan utföras; i denna modell kan dock konvexa skrov inte alls beräknas. Sortering kräver också Ω(n log n) tid i den algebraiska beslutsträdsmodellen för beräkning, en modell som är mer lämplig för konvexa skrov, och i denna modell kräver konvexa skrov också Ω(n log n) tid. I modeller för datoraritmetik som gör det möjligt att sortera tal snabbare än O(n log n)-tid, t.ex. genom att använda algoritmer för sortering av heltal, kan planära konvexa skrov också beräknas snabbare: Grahams skanningsalgoritm för konvexa skrov består av ett enda sorteringssteg som följs av ett linjärt antal ytterligare arbetsmoment.
Optimala utmatningskänsliga algoritmerRedigera
Som anges ovan är komplexiteten för att hitta ett konvext hölje som en funktion av ingångsstorleken n lägre begränsad av Ω(n log n). Komplexiteten hos vissa algoritmer för konvexa skrov kan dock karakteriseras i termer av både ingångsstorlek n och utgångsstorlek h (antalet punkter i skrovet). Sådana algoritmer kallas utmatningskänsliga algoritmer. De kan vara asymptotiskt effektivare än Θ(n log n)-algoritmer i de fall då h = o(n).
Den nedre gränsen för värsta fallets körtid för utmatningskänsliga konvexa skrovalgoritmer fastställdes till Ω(n log h) i det plana fallet. Det finns flera algoritmer som uppnår denna optimala tidskomplexitet. Den tidigaste introducerades av Kirkpatrick och Seidel 1986 (som kallade den ”the ultimate convex hull algorithm”). En mycket enklare algoritm utvecklades av Chan 1996 och kallas Chans algoritm.
AlgoritmerRedigera
Kända algoritmer för konvexa skrov är listade nedan, ordnade efter datum för första publicering. Tidskomplexiteten för varje algoritm anges i termer av antalet ingångspunkter n och antalet punkter på skrovet h. Observera att h i värsta fall kan vara lika stort som n.
- Gift wrapping, a.k.a. Jarvis march – O(nh)
En av de enklaste (även om den i värsta fall inte är den mest tidseffektiva) plana algoritmerna. Skapad oberoende av Chand & Kapur 1970 och R. A. Jarvis 1973. Den har en tidskomplexitet på O(nh), där n är antalet punkter i mängden och h är antalet punkter i skrovet. I värsta fall är komplexiteten Θ(n2). - Graham scan – O(n log n)
En något mer sofistikerad, men mycket effektivare algoritm som publicerades av Ronald Graham 1972. Om punkterna redan är sorterade efter en av koordinaterna eller efter vinkeln till en fast vektor tar algoritmen O(n) tid. - Quickhull
Skapat oberoende av varandra 1977 av W. Eddy och 1978 av A. Bykat. Precis som quicksort-algoritmen har den en förväntad tidskomplexitet på O(n log n), men kan i värsta fall degenerera till O(n2). - Divide and conquer – O(n log n)
En annan algoritm med en tidskomplexitet på O(n log n), publicerad 1977 av Preparata och Hong. Denna algoritm är också tillämplig på tredimensionella fall. - Monotone chain, a.k.a. Andrew’s algorithm- O(n log n)
Publicerad 1979 av A. M. Andrew. Algoritmen kan ses som en variant av Graham scan som sorterar punkterna lexikografiskt efter deras koordinater. När inmatningen redan är sorterad tar algoritmen O(n) tid. - Incremental convex hull algorithm – O(n log n)
Publicerad 1984 av Michael Kallay. - Kirkpatrick-Seidel-algoritm – O(n log h)
Den första optimala utmatningskänsliga algoritmen. Den modifierar divide and conquer-algoritmen genom att använda tekniken ”marriage-before-conquest” och lågdimensionell linjär programmering. Publicerad av Kirkpatrick och Seidel 1986. - Chans algoritm – O(n log h)
En enklare optimal utmatningskänslig algoritm som skapades av Chan 1996. Den kombinerar gift wrapping med utförandet av en O(n log n)-algoritm (t.ex. Graham scan) på små delmängder av inmatningen.
Akl-Toussaint heuristikEdit
Följande enkla heuristik används ofta som ett första steg i implementeringar av algoritmer för konvexa skrov för att förbättra deras prestanda. Den är baserad på Selim Akls och G. T. Toussaints effektiva algoritm för konvexa skrov från 1978. Tanken är att snabbt utesluta många punkter som ändå inte skulle ingå i det konvexa skrovet. Metoden bygger på följande idé. Hitta de två punkterna med de lägsta och högsta x-koordinaterna och de två punkterna med de lägsta och högsta y-koordinaterna. (Var och en av dessa operationer tar O(n).) Dessa fyra punkter bildar en konvex fyrhörning, och alla punkter som ligger i denna fyrhörning (utom de fyra ursprungligen valda hörnen) ingår inte i det konvexa skrovet. Att hitta alla dessa punkter som ligger i denna fyrhörning är också O(n), och därmed är hela operationen O(n). Eventuellt kan punkterna med de minsta och största summorna av x- och y-koordinater samt de med de minsta och största skillnaderna av x- och y-koordinater också läggas till fyrhörningen, vilket bildar en oregelbunden konvex oktagon, vars insida säkert kan kasseras. Om punkterna är slumpmässiga variabler kommer detta bortkastade förbehandlingssteg för en smal men vanligt förekommande klass av sannolikhetsdensitetsfunktioner att få en algoritm för konvexa skrov att köras på linjär förväntad tid, även om komplexiteten i värsta fall för algoritmen för konvexa skrov är kvadratisk i n.
On-line och dynamiska problem med konvexa skrovRedigera
Diskussionen ovan tar hänsyn till det fall då alla inmatningspunkter är kända i förväg. Man kan överväga två andra inställningar.
- Online konvexa skrovproblem: Ingångspunkterna erhålls sekventiellt en efter en. Efter att varje punkt har kommit in måste det konvexa skrovet för den hittills erhållna punktmängden beräknas effektivt.
- Dynamiskt underhåll av det konvexa skrovet: Ingångspunkterna kan införas eller tas bort sekventiellt, och det konvexa höljet måste uppdateras efter varje införande eller borttagning.
Införandet av en punkt kan öka antalet hörn i det konvexa höljet med högst 1, medan borttagningen kan omvandla ett konvext hölje med n hörn till ett hölje med n-1 hörn.
Den online-versionen kan hanteras med O(log n) per punkt, vilket är asymptotiskt optimalt. Den dynamiska versionen kan hanteras med O(log2 n) per operation.
Enkel polygonEdit
Det konvexa skrovet av en enkel polygon delas av polygonen i bitar, varav en är själva polygonen och resten är fickor som avgränsas av en bit av polygongränsen och en enda skrovkant. Även om många algoritmer har publicerats för problemet med att konstruera det konvexa höljet av en enkel polygon är nästan hälften av dem felaktiga. McCallum och Avis tillhandahöll den första korrekta algoritmen. en senare förenkling av Graham & Yao (1983) och Lee (1983) använder endast en enda datastruktur med en stapel. Deras algoritm går igenom polygonen medurs, med början från dess vänstra hörn. När den gör det lagrar den en konvex sekvens av hörn på stapeln, de hörn som ännu inte har identifierats som hörande till fickor. Vid varje steg följer algoritmen en väg längs polygonen från stackens topp till nästa topp som inte ligger i en av de två fickor som gränsar till stackens topp. När de två översta topparna på stapeln tillsammans med denna nya topp inte befinner sig i konvexa positioner, tar algoritmen bort stapeln innan den slutligen lägger den nya toppen på stapeln. När den klockvisa traverseringen når startpunkten returnerar algoritmen sekvensen av stackens toppar som skrovet.