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 het convexe omhulsel van een gegeven meetkundig lichaam.

Het primaire doel van onderzoek in de combinatorische computationele meetkunde is het ontwikkelen van algoritmes en datastructuren voor het oplossen van problemen in termen van meetkundige basisobjecten: punten, lijnstukken, veelhoeken, veelvlakken, enzovoort. De algoritmen nodig voor de constructieve ruimtemeetkunde zijn daar een voorbeeld van. Er zijn problemen die tot de komst van computers zo eenvoudig leken dat ze helemaal niet als problemen werden gezien, bijvoorbeeld het probleem van het dichtste puntenpaar. Dat gaat het er om gegeven een aantal punten in het vlak, de twee te vinden die het dichtst bij elkaar liggen.