Het primaire doel van het onderzoek in de combinatorische computationele meetkunde is het ontwikkelen van efficiënte algoritmen en gegevensstructuren voor het oplossen van problemen die worden gesteld in termen van geometrische basisobjecten: punten, lijnstukken, veelhoeken, veelvlakken, enz.
Sommige van deze problemen lijken zo eenvoudig dat ze tot de komst van computers helemaal niet als problemen werden beschouwd. Neem bijvoorbeeld het probleem van het dichtstbijzijnde paar:
- Gegeven n punten in het vlak, zoek de twee met de kleinste afstand tot elkaar.
Men zou de afstanden tussen alle puntenparen kunnen berekenen, waarvan er n(n-1)/2 zijn, en dan het paar met de kleinste afstand kiezen. Dit brute-force algoritme neemt O(n2) tijd in beslag, d.w.z. dat de uitvoeringstijd evenredig is met het kwadraat van het aantal punten. Een klassiek resultaat in de computationele meetkunde was de formulering van een algoritme dat O(n log n) duurt. Er zijn ook gerandomiseerde algoritmen ontdekt die O(n) verwachte tijd vergen, en een deterministisch algoritme dat O(n log n) tijd vergt.
ProbleemklassenEdit
De kernproblemen in de computationele meetkunde kunnen op verschillende manieren worden geclassificeerd, volgens verschillende criteria. De volgende algemene klassen kunnen worden onderscheiden.
Statische problemenEdit
In de problemen van deze categorie wordt een bepaalde invoer gegeven en moet de bijbehorende uitvoer worden geconstrueerd of gevonden. Enkele fundamentele problemen van dit type zijn:
- Convexe schil: Gegeven een verzameling punten, vind de kleinste convexe veelvlak/polygoon die alle punten bevat.
- Lijnsegment doorsnijding: Vind de snijpunten tussen een gegeven verzameling lijnsegmenten.
- Delaunay triangulatie
- Voronoi-diagram: Gegeven een verzameling punten, verdeel de ruimte volgens welke punten het dichtst bij de gegeven punten liggen.
- Lineair programmeren
- Paar dichtst bij elkaar liggende punten: Gegeven een verzameling punten, vind de twee met de kleinste afstand van elkaar.
- Verste paar punten
- Grootste lege cirkel: Gegeven een verzameling punten, vind een grootste cirkel met het middelpunt binnen hun convexe schil en die geen van hen insluit.
- Euclidisch kortste pad: Verbindt twee punten in een Euclidische ruimte (met veelvlakkige hindernissen) door een kortste pad.
- Polygoontriangulatie: Gegeven een veelhoek, verdeel zijn interieur in driehoeken
- Mesh generatie
- Booleaanse operaties op veelhoeken
De computationele complexiteit voor deze klasse van problemen wordt geschat door de tijd en ruimte (computer geheugen) die nodig is om een gegeven probleem instantie op te lossen.
Geometrische zoekproblemenEdit
In geometrische zoekproblemen, algemeen bekend als geometrische zoekproblemen, bestaat de invoer uit twee delen: het zoekruimtedeel en het zoekvraagdeel, dat varieert over de probleemgevallen. De zoekruimte moet typisch worden voorbewerkt, zodanig dat meerdere zoekopdrachten efficiënt kunnen worden beantwoord.
Enkele fundamentele geometrische zoekproblemen zijn:
- Bereik zoeken: Een verzameling punten voorbewerken, om efficiënt het aantal punten binnen een zoekgebied te tellen.
- Puntlokatie: Gegeven een verdeling van de ruimte in cellen, produceer een datastructuur die efficiënt vertelt in welke cel een opvraagpunt zich bevindt.
- Dichtstbijzijnde buur: Een set van punten voorbewerken, om efficiënt te vinden welk punt het dichtst bij een opvraagpunt ligt.
- Ray tracing: Gegeven een verzameling objecten in de ruimte, produceer een datastructuur die efficiënt vertelt welk object een opgevraagde straal als eerste snijdt.
Als de zoekruimte vast is, wordt de computationele complexiteit voor deze klasse van problemen gewoonlijk geschat door:
- de tijd en ruimte die nodig zijn om de datastructuur te construeren waarin gezocht moet worden
- de tijd (en soms een extra ruimte) om de opvragen te beantwoorden.
Voor het geval dat de zoekruimte mag variëren, zie “Dynamische problemen”.
Dynamische problemenEdit
Een andere belangrijke klasse zijn de dynamische problemen, waarbij het doel is een efficiënt algoritme te vinden voor het vinden van een oplossing, herhaaldelijk na elke incrementele wijziging van de invoergegevens (toevoeging of schrapping van ingevoerde geometrische elementen). Algoritmen voor dit soort problemen impliceren gewoonlijk dynamische gegevensstructuren. Elk van de computationele geometrische problemen kan worden omgezet in een dynamisch probleem, ten koste van een langere verwerkingstijd. Zo kan bijvoorbeeld het range searching probleem worden omgezet in het dynamic range searching probleem door te voorzien in het toevoegen en/of verwijderen van de punten. Het dynamische convexe-rompprobleem is het bijhouden van de convexe-romp, b.v., voor de dynamisch veranderende reeks punten, d.w.z, terwijl de invoerpunten worden ingevoegd of verwijderd.
De computationele complexiteit voor deze klasse van problemen wordt geschat door:
- de tijd en ruimte die nodig is om de te doorzoeken gegevensstructuur te construeren
- de tijd en ruimte om de doorzochte gegevensstructuur te wijzigen na een incrementele verandering in de zoekruimte
- de tijd (en soms een extra ruimte) om een query te beantwoorden.
VariatiesEdit
Sommige problemen kunnen worden behandeld als behorend tot een van beide categorieën, afhankelijk van de context. Beschouw bijvoorbeeld het volgende probleem.
- Punt in veelhoek: Beslis of een punt binnen of buiten een gegeven veelhoek ligt.
In veel toepassingen wordt dit probleem behandeld als een enkelvoudig probleem, d.w.z. behorend tot de eerste klasse. Bijvoorbeeld, in veel toepassingen van computergrafiek is een veel voorkomend probleem te vinden welk gebied op het scherm wordt aangeklikt door een aanwijzer. In sommige toepassingen is de polygoon in kwestie echter invariant, terwijl het punt een vraag voorstelt. De ingevoerde veelhoek kan bijvoorbeeld een grens van een land voorstellen en een punt is een positie van een vliegtuig, en het probleem is te bepalen of het vliegtuig de grens heeft geschonden. Tenslotte, in het eerder genoemde voorbeeld van computer graphics, in CAD toepassingen worden de veranderende invoergegevens vaak opgeslagen in dynamische datastructuren, die kunnen worden benut om de punt-in-polygoon queries te versnellen.
In sommige contexten van query problemen zijn er redelijke verwachtingen over de volgorde van de queries, die kunnen worden benut voor ofwel efficiënte datastructuren of voor strakkere schattingen van de computationele complexiteit. In sommige gevallen is het bijvoorbeeld belangrijk om de worst case voor de totale tijd te weten voor de hele reeks van N queries, in plaats van voor een enkele query. Zie ook “geamortiseerde analyse”.