Beräkningsgeometri

Det primära målet för forskningen inom kombinatorisk beräkningsgeometri är att utveckla effektiva algoritmer och datastrukturer för att lösa problem som uttrycks i termer av grundläggande geometriska objekt: punkter, linjesträckningar, polygoner, polyeder osv.

Vissa av dessa problem verkar så enkla att de inte betraktades som problem alls förrän datorerna kom. Tänk till exempel på problemet med det närmaste paret:

• Givet n punkter i planet, hitta de två som har det minsta avståndet till varandra.

Man skulle kunna beräkna avstånden mellan alla punktpar, av vilka det finns n(n-1)/2, och sedan välja det par som har det minsta avståndet. Denna brutala algoritm tar O(n2) tid, dvs. dess genomförandetid är proportionell mot kvadraten på antalet punkter. Ett klassiskt resultat inom beräkningsgeometri var formuleringen av en algoritm som tar O(n log n). Randomiserade algoritmer som tar O(n) förväntad tid, liksom en deterministisk algoritm som tar O(n log log n) tid, har också upptäckts.

ProblemklasserRedigera

Kärnproblemen inom beräkningsgeometri kan klassificeras på olika sätt, enligt olika kriterier. Följande allmänna klasser kan urskiljas.

Statiska problemEdit

I problemen i denna kategori ges en viss indata och motsvarande utdata måste konstrueras eller hittas. Några grundläggande problem av denna typ är:

• Konvexa skrov:
• Linjesträckning: Givet en uppsättning punkter, hitta den minsta konvexa polyedern/polygonen som innehåller alla punkter.
• Linjesträckning: Hitta den minsta konvexa polyedern/polygonen som innehåller alla punkter:
• Delaunay-triangulering
• Voronoi-diagram: Hitta skärningspunkterna mellan en given uppsättning linjesegment: Givet en uppsättning punkter, dela upp rummet enligt vilka punkter som ligger närmast de givna punkterna.
• Linjär programmering
• Närmaste punktpar:
• Första par av punkter
• Första par av punkter
• Största tomma cirkel: Givet en uppsättning punkter, hitta den största cirkeln med centrum inom deras konvexa skrov och som inte omsluter någon av dem.
• Euklidisk kortaste väg: Den största cirkeln är den största cirkeln med centrum inom deras konvexa skrov och som inte omsluter någon av dem.
• Förbind två punkter i ett euklidiskt rum (med polyedriska hinder) genom en kortaste väg.
• Polygontriangulering: Givet en polygon, dela upp dess inre i trianglar
• Maskgenerering
• Boolska operationer på polygoner

Den beräkningsmässiga komplexiteten för denna klass av problem uppskattas genom den tid och det utrymme (datorminne) som krävs för att lösa en viss probleminstans.

Geometriska frågeproblemRedigera

I geometriska frågeproblem, allmänt kända som geometriska sökproblem, består indata av två delar: sökrumsdelen och frågedelen, som varierar över probleminstanserna. Sökutrymmet måste vanligtvis förbehandlas så att flera frågor kan besvaras på ett effektivt sätt.

Några grundläggande geometriska frågeproblem är:

• Räckviddssökning: Förbehandla en uppsättning punkter för att på ett effektivt sätt räkna antalet punkter inom en frågeregion.
• Punktplacering:
• Närmaste granne: För att kunna beräkna en punkt i ett område som är uppdelat i celler, skapa en datastruktur som på ett effektivt sätt talar om i vilken cell en punkt är belägen.
• Förbehandling av en uppsättning punkter för att på ett effektivt sätt hitta vilken punkt som ligger närmast en frågepunkt.
• Strålspårning:

Om sökutrymmet är fixerat uppskattas vanligtvis beräkningskomplexiteten för denna klass av problem genom:

• den tid och det utrymme som krävs för att konstruera den datastruktur som ska sökas i
• den tid (och ibland ett extra utrymme) som krävs för att besvara frågor.

För det fall då sökutrymmet tillåts variera, se ”Dynamiska problem”.

Dynamiska problemRedigera

En annan stor klass är de dynamiska problemen, där målet är att hitta en effektiv algoritm för att hitta en lösning upprepade gånger efter varje inkrementell modifiering av indatadata (tillsats eller borttagning av ingående geometriska element). Algoritmer för problem av denna typ omfattar vanligtvis dynamiska datastrukturer. Alla geometriska beräkningsproblem kan omvandlas till dynamiska problem, till priset av ökad behandlingstid. Till exempel kan problemet med att söka efter områden omvandlas till ett dynamiskt problem med att söka efter områden genom att man tillåter tillägg och/eller borttagning av punkter. Det dynamiska problemet med konvexa skrov består i att hålla reda på det konvexa skrovet, t.ex. för den dynamiskt föränderliga uppsättningen punkter, dvs, medan ingångspunkterna läggs till eller tas bort.

Den beräkningsmässiga komplexiteten för denna klass av problem uppskattas genom:

• den tid och det utrymme som krävs för att konstruera datastrukturen som ska sökas i
• den tid och det utrymme som krävs för att ändra den sökta datastrukturen efter en inkrementell förändring av sökutrymmet
• den tid (och ibland ett extra utrymme) som krävs för att besvara en förfrågan.

VariationerRedigera

Vissa problem kan behandlas som tillhörande någon av kategorierna, beroende på sammanhanget. Tänk till exempel på följande problem.

• Punkt i polygon:

I många tillämpningar behandlas detta problem som ett problem med en enda punkt, dvs. det tillhör den första klassen. I många tillämpningar av datorgrafik är till exempel ett vanligt problem att ta reda på vilket område på skärmen som en pekare klickar på. I vissa tillämpningar är dock polygonen i fråga invariant, medan punkten representerar en fråga. Den inmatade polygonen kan t.ex. representera ett lands gräns och en punkt är ett flygplans position, och problemet är att avgöra om flygplanet har brutit mot gränsen. Slutligen, i det tidigare nämnda exemplet med datorgrafik, i CAD-tillämpningar lagras de föränderliga indata ofta i dynamiska datastrukturer, vilket kan utnyttjas för att påskynda punkt-i-polygon-förfrågningar.

I vissa sammanhang av förfrågningsproblem finns det rimliga förväntningar på sekvensen av förfrågningar, vilket kan utnyttjas antingen för effektiva datastrukturer eller för snävare beräkningsuppskattningar av beräkningskomplexiteten. I vissa fall är det till exempel viktigt att känna till det värsta fallet för den totala tiden för hela sekvensen av N förfrågningar, snarare än för en enskild förfrågan. Se även ”amorterad analys”.