Algoritmisk geometri

Den beregningsmæssige geometri er det algoritmiske felt, der beskæftiger sig med algoritmer, der manipulerer geometriske begreber .

Definition og første eksempler

Algoritmisk geometri er studiet af algoritmer, der manipulerer geometriske objekter . For eksempel er det algoritmiske problem, der består, givet et sæt punkter i det plan, der er beskrevet af deres koordinater, ved at finde det par af punkter, hvis afstand er minimal , et problem med geometriske algoritmer.

Historie og anvendelser

En af disciplinens oprindelser er det faktum, at computermodeller, det vil sige virtual reality, erstatter modeller i design af objekter fra 1970'erne. Disse modeller tillader derefter undersøgelse af en lang række virkelige fænomener. Den disciplin, der utvivlsomt har bidraget mest historisk til udviklingen af ​​beregningsgeometri, er computergrafik . Imidlertid er beregningsgeometri ofte involveret i generelle algoritmiske problemer på nuværende tidspunkt.

Algoritmisk geometri bruges i dag i computergrafik, robotik, geografiske informationssystemer og computerdesign.

Klassisk datastruktur

Nogle strukturer, der kan bruges i starten af ​​problemet eller inde i algoritmen, er centrale i algoritmisk geometri: polyhedra , Voronoi-diagrammer og trekanter .

Klassiske problemer

Konveks konvolut

Den konvekse konvolut af et sæt punkter på flyet er den mindste konvekse polygon, der indeholder alle punkterne. Denne opfattelse kan straks generaliseres til dimensioner større end 2.

Den bedst kendte algoritme, der gør det muligt at bestemme den konvekse konvolut for ethvert sæt n- punkter i 2D ( Grahams sti ) eller 3D er i O ( n log ( n )) . Uden yderligere viden om dataene kan man ikke gøre det bedre end Ω ( n log ( n )); imidlertid findes der flere O ( n ) algoritmer til at behandle tilfældet med enkle polygoner (ikke-selvskærende polygoner) givet i rækkefølgen af ​​punkterne. Der er også algoritmer, hvor kompleksiteten er givet som en funktion af antallet af punkter n, men også som en funktion af antallet af punkter i den konvekse kuvert (dvs. algoritmens output): Jarvis-gangen er en algoritme i O ( nh ) og Chans algoritme er i O ( n log h ).

I tilfælde af en hvilken som helst dimension d ( d > 3) findes de bedst kendte algoritmer .

Generelle algoritmiske problemer

Algoritmisk geometri giver optimale løsninger til problemer beskrevet i et afgrænset univers. Denne beskæftiger sig faktisk med problemer, der er angivet i form af punkter arrangeret på et afgrænset gitter [1, X ] × [1, Y ] af dimension 2. Ved udvidelse behandler det de samme problemer på gitre med højere dimensioner og med intervaller på heltal (dimension 1).

For eksempel, givet et sæt punkter S i intervallet af heltal [1, U ], er det muligt at drage fordel af den afgrænsede karakter af universet [1, U ] for at løse nogle problemer under deres kompleksitet minimal for et ubegrænset univers . Det mest trivielle og mest kendte tilfælde er, at lineær sortering , skovlen kommer ud . Elementerne i S kan sorteres i tide | S | + U browsing S gang og lagring hvert element findes i "bucket", svarende til en række spande nummereret 1 til U .

Mange algoritmiske problemer finder optimale løsninger i et afgrænset univers:

Nogle andre vigtige spørgsmål

Vanskeligheder og teknikker

Et problem er pest af dimension  : klassiske algoritmer bliver ubrugelige, hvis dataene tilhører et stort rum. En klassisk teknik er at bruge sandsynlighedsalgoritmer .

Noter og referencer

  1. Francis Lazarus, “  Algoritmisk geometri: forelæsningsnotater  ” , om Laboratoire GIPSA
  2. Jean-Daniel Boissonnat , “  Algoritmisk geometri: fra geometriske data til data geometri  ” , om Collège de France .

Se også

Relaterede artikler

eksterne links