Den beregningsmæssige geometri er det algoritmiske felt, der beskæftiger sig med algoritmer, der manipulerer geometriske begreber .
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.
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.
Nogle strukturer, der kan bruges i starten af problemet eller inde i algoritmen, er centrale i algoritmisk geometri: polyhedra , Voronoi-diagrammer og trekanter .
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 .
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:
Et problem er pest af dimension : klassiske algoritmer bliver ubrugelige, hvis dataene tilhører et stort rum. En klassisk teknik er at bruge sandsynlighedsalgoritmer .