Computergeometri

Det primære mål med forskning i kombinatorisk computergeometri er at udvikle effektive algoritmer og datastrukturer til løsning af problemer, der er formuleret i form af grundlæggende geometriske objekter: punkter, linjestykker, polygoner, polyedre osv.

Nogle af disse problemer synes så enkle, at de slet ikke blev betragtet som problemer, før computerne kom frem. Overvej f.eks. problemet med det nærmeste par:

• Givet n punkter i planen, find de to med den mindste afstand til hinanden.

Man kunne beregne afstandene mellem alle punktpar, som der er n(n-1)/2 af, og derefter vælge det par med den mindste afstand. Denne brute-force-algoritme tager O(n2) tid; dvs. at dens udførelsestid er proportional med kvadratet på antallet af punkter. Et klassisk resultat inden for beregningsgeometri var formuleringen af en algoritme, der tager O(n log n). Der er også blevet opdaget randomiserede algoritmer, der tager O(n) forventet tid, samt en deterministisk algoritme, der tager O(n log log log n) tid.

ProblemklasserRediger

Kerneproblemerne inden for beregningsgeometri kan klassificeres på forskellige måder, efter forskellige kriterier. Der kan skelnes mellem følgende generelle klasser.

Statiske problemerRediger

I problemerne i denne kategori er der givet et input, og det tilsvarende output skal konstrueres eller findes. Nogle grundlæggende problemer af denne type er:

• Konvekse skrog: Givet et sæt af punkter, find det mindste konvekse polyeder/polygon, der indeholder alle punkterne.
• Skæring af linjestykker: Find skæringspunkterne mellem et givet sæt linjestykker.
• Delaunay-triangulering
• Voronoi-diagram: Givet et sæt punkter, opdel rummet efter, hvilke punkter der ligger tættest på de givne punkter.
• Linear programmering
• Nærmeste punktpar: Givet et sæt af punkter, find de to punkter med den mindste afstand til hinanden.
• Det fjerneste punktpar
• Største tomme cirkel: Givet et sæt af punkter, find den største cirkel med centrum inden for deres konvekse skrog og uden at omslutte nogen af dem.
• Euklidisk korteste vej: Forbind to punkter i et euklidisk rum (med polyedriske forhindringer) ved hjælp af den korteste vej.
• Polygontriangulering: Forbind to punkter i et euklidisk rum (med polyedriske forhindringer) ved hjælp af en korteste vej: Givet en polygon, opdeling af dens indre i trekanter
• Meshgenerering
• Boolske operationer på polygoner

Den beregningsmæssige kompleksitet for denne klasse af problemer vurderes ud fra den tid og plads (computerhukommelse), der kræves for at løse en given probleminstans.

Geometriske forespørgselsproblemerRediger

I geometriske forespørgselsproblemer, der almindeligvis er kendt som geometriske søgeproblemer, består input af to dele: søgrumsdelen og forespørgselsdelen, som varierer i løbet af probleminstanserne. Søgerummet skal typisk forbehandles på en sådan måde, at flere forespørgsler kan besvares effektivt.

Nogle grundlæggende geometriske forespørgselsproblemer er:

• Rangesøgning: Forbehandling af et sæt punkter for effektivt at tælle antallet af punkter inden for et forespørgselsområde.
• Punktplacering:
• Nærmeste nabo: Udarbejdelse af en datastruktur, der effektivt fortæller, i hvilken celle et søgepunkt er placeret: Forbehandling af et sæt punkter med henblik på effektivt at finde ud af, hvilket punkt der ligger tættest på et forespørgselspunkt.
• Ray tracing:

Hvis søgeområdet er fast, anslås den beregningsmæssige kompleksitet for denne klasse af problemer normalt ved:

• den tid og plads, der er nødvendig for at konstruere den datastruktur, der skal søges i
• den tid (og undertiden en ekstra plads), der er nødvendig for at besvare forespørgsler.

For det tilfælde, hvor søgerummet kan variere, se “Dynamiske problemer”.

Dynamiske problemerRediger

En anden stor klasse er de dynamiske problemer, hvor målet er at finde en effektiv algoritme til at finde en løsning gentagne gange efter hver inkrementel ændring af inputdataene (tilføjelse eller sletning af input geometriske elementer). Algoritmer til problemer af denne type involverer typisk dynamiske datastrukturer. Ethvert geometrisk beregningsproblem kan omdannes til et dynamisk problem, men det koster en øget behandlingstid. F.eks. kan problemet med søgning efter områder konverteres til et dynamisk problem med søgning efter områder ved at sørge for tilføjelse og/eller sletning af punkter. Det dynamiske konvekse skrogproblem består i at holde styr på det konvekse skrog, f.eks. for det dynamisk skiftende sæt af punkter, dvs, mens inputpunkterne indsættes eller slettes.

Den beregningsmæssige kompleksitet for denne klasse af problemer anslås ved:

• den tid og plads, der er nødvendig for at konstruere den datastruktur, der skal søges i
• den tid og plads, der er nødvendig for at ændre den søgte datastruktur efter en inkrementel ændring i søgeområdet
• den tid (og undertiden en ekstra plads), der er nødvendig for at besvare en forespørgsel.

VariationerRediger

Nogle problemer kan behandles som tilhørende en af kategorierne, afhængigt af konteksten. Overvej f.eks. følgende problem.

• Punkt i polygon: Afgør, om et punkt er inden for eller uden for en given polygon.

I mange anvendelser behandles dette problem som et enkeltstående problem, dvs. som tilhørende den første klasse. F.eks. er et almindeligt problem i mange anvendelser inden for computergrafik at finde ud af, hvilket område på skærmen der er klikket på af en pegepind. I nogle applikationer er den pågældende polygon imidlertid invariant, mens punktet repræsenterer en forespørgsel. F.eks. kan indgangspolygonen repræsentere en grænse i et land, og et punkt er et flys position, og problemet er at finde ud af, om flyet har overtrådt grænsen. Endelig er de skiftende inputdata i CAD-applikationer i det tidligere nævnte eksempel med computergrafik ofte lagret i dynamiske datastrukturer, hvilket kan udnyttes til at fremskynde punkt-i-polygon-forespørgsler.

I nogle sammenhænge med forespørgselsproblemer er der rimelige forventninger til rækkefølgen af forespørgslerne, hvilket kan udnyttes enten til effektive datastrukturer eller til strammere beregningskompleksitetsestimater. I nogle tilfælde er det f.eks. vigtigt at kende det værste tilfælde for den samlede tid for hele sekvensen af N forespørgsler, snarere end for en enkelt forespørgsel. Se også “amortiseret analyse”.