Signed Euclidean DT with error detection and correction.

In this chapter, we consider signed distance transformations. We show that the approximate signed distance maps contains sufficient information to allow the detection and correction of errors, notwithstanding the method used to produce them.
First, we consider a few properties of the Voronoi diagram of a discrete set of points, both on a continuous plane or on a discrete grid. Errors in signed EDT always occur near the corners of the Voronoi polygons, which can easily be detected and corrected. The algorithm's computational complexity is evaluated.
This time, the error detection paradigm can be extended to 3 dimensions. We evaluate the difficulty of a 3D exact EDT by error correction and compare a few alternatives.