Beregning av den konvekse konvolutten

I geometrisk algoritme er beregningen av den konvekse konvolutten et algoritmisk problem . Den består, gitt et sett med poeng, i beregningen av den konvekse konvolutten .

Definisjon

Det konvekse skroget til et sett med punkter er det minste konvekse settet som inneholder dem alle. Det er en polyhedron hvis hjørner er punktene i settet. Beregningen av den konvekse konvolutten består i å beregne en kompakt representasjon av konvolutten, ofte toppunktene derav.

Dette er et problem som har mange applikasjoner, for eksempel innen mønstergjenkjenning, og som er sentralt i beregningsgeometri .

Algoritmer for den plane saken

Den plane saken er tilfelle der punktene er ordnet i flyet. Vi måler kompleksiteten i tid som en funksjon av antall punkter på inngangen n , og av antall punkter på konvolutten h . Det er mange algoritmer for denne saken.

Jarvis Walk

Ideen med Jarvis-turen (eller gaveinnpakningsalgoritmen ) er å "pakke" punktpunktet i et "gavepakning": vi henger dette papiret på et av punktene, vi strekker det, så snur vi rundt punktet Sky. Kompleksiteten til algoritmen er O (nh) .

Grahams reise

Den Kurset Graham (aka Graham skanning ) er å finne det punktet av minste x-aksen, liksom alle andre punkter fra vinkelen de gjør med det (og x-aksen), og deretter vurdere trillingene av påfølgende punkter, for å finne ut hvilke som er i konvolutten. Kompleksiteten er den ved sortering , det vil si O (n.log (n)) .

Chans algoritme

Den Chan algoritmen , fortsetter i etapper. Først en partisjonering av punktene i flere grupper, deretter beregningen av de konvekse konvoluttene til disse gruppene med en algoritme i O (n.log (n)) (som Graham- turen ), og til slutt en Jarvis-gange med disse konvoluttene som allerede er beregnet . Dens kompleksitet er i O (n.log (h)) .

Quickhull

Quickhull er en splitt og erobringsalgoritme . Den gjennomsnittlige kompleksiteten er O (n.log (n)). Dens verste fall er O (n²).

Shamos algoritme

Shamos ' algoritme er en delings- og erobringsalgoritme. Dens kompleksitet er O (n.log (n)).

Kirkpatrick og Seidel algoritme

Den algoritme av Kirkpatrick og Seidel  (i) har en kompleksitet O (n.log (h)) .

Andre algoritmer

Andre algoritmer eksisterer, som Andrews algoritme.

Algoritmer for høyere dimensjoner

Den Preparata-Hong algoritmen arbeider for dimensjonene 2 og 3.

For dimensjoner større enn 2 fungerer quickhull-algoritmen og Chans algoritme.

Tilnærming

Det er også algoritmer for å tilnærme den konvekse konvolutten.

Merknader og referanser

  1. Franco P. Preparata og Michael Ian Shamos, “ Convex hulls : Basic algorithms” , i Computational Geometry , Sringer, 1985( online presentasjon )
  2. Arnaud Jehanne, "  Calculer une envelope konvexe  " , på University of Bordeaux .

Eksterne linker