Computing 2D constrained delaunay triangulation using the GPU
Related Experiment Video
Updated: May 13, 2026

High-resolution, High-speed, Three-dimensional Video Imaging with Digital Fringe Projection Techniques
Published on: December 3, 2013
Meng Qi1, Thanh-Tung Cao, Tiow-Seng Tan
1National University of Singapore, Singapore. qimeng@comp.nus.edu.sg
Abstract:
We propose the first graphics processing unit (GPU) solution to compute the 2D constrained Delaunay triangulation (CDT) of a planar straight line graph (PSLG) consisting of points and edges. There are many existing CPU algorithms to solve the CDT problem in computational geometry, yet there has been no prior approach to solve this problem efficiently using the parallel computing power of the GPU. For the special case of the CDT problem where the PSLG consists of just points, which is simply the normal Delaunay triangulation (DT) problem, a hybrid approach using the GPU together with the CPU to partially speed up the computation has already been presented in the literature. Our work, on the other hand, accelerates the entire computation on the GPU. Our implementation using the CUDA programming model on NVIDIA GPUs is numerically robust, and runs up to an order of magnitude faster than the best sequential implementations on the CPU. This result is reflected in our experiment with both randomly generated PSLGs and real-world GIS data having millions of points and edges.
Related Concept Videos
Computed Tomography
The technique was invented in the 1970s and is based on the principle that as X-rays pass through the body, they are absorbed or reflected at different levels. In the technique, a patient lies on a motorized platform while a computerized axial tomography (CAT) scanner rotates...
Gauss's Law: Planar Symmetry
Parallel-axis Theorem
Three-Dimensional Analysis of Strain
Area Computation by the Alternative Coordinate Method
Design Example: Traverse Angle Computations

