Delaunay property and proximity results of the L-algorithm for digital plane probing

Abstract

When processing the geometry of digital surfaces (boundaries of voxel sets), linear local structures such as pieces of digital planes play an important role. To capture such geometrical features, plane-probing algorithms have demonstrated their strength: starting from an initial triangle, the digital structure is locally probed to expand the triangle approximating the plane parameters more and more precisely (converging to the exact parameters for infinite digital planes). Among the different plane-probing algorithms, the L-algorithm is a plane-probing algorithm variant which takes into account a generally larger neighborhood of points for its update process. We show in this paper that this algorithm has the advantage to guarantee the so-called Delaunay property of the set of probing points, which has interesting consequences: it provides a minimal basis of the plane and guarantees an as-local-as-possible computation.

Jacques-Olivier Lachaud

Professor of Computer Science

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