A comprehensive survey on Delaunay Triangulation: Applications, Algorithms, and Implementations over CPUs, GPUs, and FPGAs
Journal
IEEE Access
Date Issued
January 1, 2024
DOI
10.1109/ACCESS.2024.3354709
Abstract
Delaunay triangulation is an effective way to build a <italic>triangulation</italic> of a cloud of points, i.e., a partitioning of the points into simplices (triangles in 2D, tetrahedra in 3D, and so on), such that no two simplices overlap and every point in the set is a vertex of at least one simplex. Such a triangulation has been shown to have several interesting properties in terms of the structure of the simplices it constructs (e.g., maximizing the minimum angle of the triangles in the bi-dimensional case) and has several critical applications in the contexts of computer graphics, computational geometry, mobile robotics or indoor localization, to name a few application domains. This review paper revolves around three main pillars: (I) algorithms, (II) implementations over <italic>central processing units</italic> (CPUs), <italic>graphics processing units</italic> (GPUs), and <italic>field programmable gate arrays</italic> (FPGAs), and (III) applications. Specifically, the paper provides a comprehensive review of the main state-of-the-art algorithmic approaches to compute the Delaunay Triangulation. Subsequently, it delivers a critical review of implementations of Delaunay triangulation over CPUs, GPUs, and FPGAs. Finally, the paper covers a broad and multi-disciplinary range of possible applications of this technique.
File(s)![Thumbnail Image]()
Name
A_Comprehensive_Survey_on_Delaunay_Triangulation_Applications_Algorithms_and_Implementations_Over_CPUs_GPUs_and_FPGAs.pdf
Size
2.51 MB
Format
Adobe PDF
Checksum (MD5)
abf46953342a9bcc6267d9fe6fa02d68