Euclidean DT in 3 dimensions

In this chapter, we explore how the algorithms of chapters 3 and 5 can be extended to 3 dimensions. First, we remind the algorithms that can be used to produce approximate Euclidean DT in 3 dimensions. Secondly, we consider the error detection and correction methods of chapter 3 and 5 and discuss the possibility of extending them to 3 dimensions. Thirdly, we evaluate the computational complexity of algorithms that would use this approach, and show that it can not compete with Saito's method. Alternatively, we propose a new hybrid method that combines our optimal 2D distance transformation algorithms with Saito's along the third axis. We show that this is the best available algorithm for large data sets, especially when one considers anisotropic volumes.