Improvements to randomized incremental Delaunay insertion
Delaunay triangulation construction is one of the fundamental problems we are facing in computer graphics and computational geometry. As a result, many solutions have been developed, incremental insertion being one of the most popular algorithms. Although it is not worst-case optimal, it is simple. robust and behaves well in expected time. This paper suggests two improvements to the algorithm. The first one speeds up the computation without increasing memory requirements. The second refinement decreases memory requirements, trading space for small slow down. Both improvements are easy to implement and can be used either side-by-side or each of them independently. (C) 2002 Elsevier Science Ltd. All rights reserved.
delaunay triangulation computer graphics computational geometry incremental insertion point location