Computationele geometrie

Computationele geometrie of computationele meetkunde is een vakgebied binnen de informatica dat zich bezighoudt met algoritmes die in de meetkunde kunnen worden gebruikt, bijvoorbeeld bij het modelleren van 3D-computergraphics. Het vakgebied heeft meer praktische toepassingen zoals op het gebied van computergraphics, CAD en CAM en computersimulatie. Voorbeelden van problemen die onder de computationele meetkunde vallen zijn de delaunay-triangulatie en het bepalen van de convexe omhulling van een gegeven meetkundige vorm.

Combinatorische computationele geometrie

Het primaire doel van onderzoek in combinatorische computationele meetkunde is het ontwikkelen van efficiënte algoritmes en datastructuren voor het oplossen van problemen in termen van meetkundige basisobjecten: punten, lijnstukken, veelhoeken, polyhedra, enz.

Sommige van deze problemen lijken zo eenvoudig dat ze helemaal niet als problemen werden gezien tot de komst van computers. Neem bijvoorbeeld het dichtste puntenpaarprobleem:

• Gegeven n punten in het vlak, vind de twee met de kleinste afstand tot elkaar.