Delaunay properties of digital straight segments


We present new results concerning the Delaunay triangulation of the set of points of pieces of digital straight lines. More precisely, we show how the triangulation topology follows the arithmetic decomposition of the line slope as well as its combinatorial decomposition (splitting formula). A byproduct is a linear time algorithm for computing the Delaunay triangulation and the Voronoi diagram of such sets.

Proc. International Conference on Discrete Geometry for Computer Imagery (DGCI2011), volume 6607 of Lecture Notes in Computer Science, pp 308-319, 2011. Springer, Cham
Jacques-Olivier Lachaud
Jacques-Olivier Lachaud
Professor of Computer Science

My research interests include digital geometry, geometry processing, image analysis, variational models and discrete calculus.