A Comprehensive Survey on Delaunay Triangulation : Applications, Algorithms, and Implementations Over CPUs, GPUs, and FPGAs
Loading...
Access rights
openAccess
publishedVersion
URL
Journal Title
Journal ISSN
Volume Title
A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Date
Major/Subject
Mcode
Degree programme
Language
en
Pages
24
Series
IEEE Access, Volume 12, pp. 12562-12585
Abstract
Delaunay triangulation is an effective way to build a triangulation 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., maximising 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 localisation, to name a few application domains. This review paper revolves around three main pillars: (I) algorithms, (II) implementations over central processing units (CPUs), graphics processing units (GPUs), and field programmable gate arrays (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.Description
Publisher Copyright: © 2013 IEEE.
Other note
Citation
Elshakhs, Y S, Deliparaschos, K M, Charalambous, T, Oliva, G & Zolotas, A 2024, 'A Comprehensive Survey on Delaunay Triangulation : Applications, Algorithms, and Implementations Over CPUs, GPUs, and FPGAs', IEEE Access, vol. 12, pp. 12562-12585. https://doi.org/10.1109/ACCESS.2024.3354709