Graphics Reference
In-Depth Information
property that, for all such quadrilaterals, the minimum of the six angles in the two
triangles that triangulate it will not increase if one switches to the other triangulation
and replaces the diagonal that is the common edge by the other diagonal. Although
Delaunay triangulations maximize the minimal angle of triangles, it is easy to give
examples that it does not minimize the maximal angle.
17.8.4 Theorem.
Using a Voronoi diagram a Delaunay triangulation can be com-
puted in O(n) time after a precomputation time of the Voronoi diagram of O(n log n).
Proof.
See [Aure91] or [BKOS97].
Rather than computing a Delaunay triangulation from a Voronoi diagram, which
involves computing and storing the vertices of that diagram, there are algorithms that
compute it directly. The three main approaches are divide-and-conquer ([GuiS85] and
[Dwye87]), sweepline ([Fort87]), and incremental ([GreS77], [ClaS89], [BDST92],
[FanP93], [BoiT93], [Lisc94], [BKOS97], [Devi98]). According to tests described in
[SuDr95] and [Shew96] the divide-and-conquer algorithms seem to be the fastest with
the sweepline algorithms the next fastest and the incremental algorithms the slowest,
although the simplest. An algorithm based on the divide-and-conquer approach that
also extends to higher dimensions can be found in [CiMS98].
Finally, if one wants to generalize to higher dimensions, one can build on what is
known for Voronoi diagrams in that case or again try to deal with the problem directly.
For a survey of this topic see [Aure91]. A specific implementation for a Delaunay tri-
angulation for three dimensions can be found in [FanP95].
