Delete and insert operations in Voronoi/Delaunay methods and applications

This paper presents simple point insertion and deletion operations in Voronoi diagrams and Delaunay triangulations which may be useful for a wide variety of applications, either where interactivity is important, or where local modification of the topology is preferable to global rebuilding. While incremental point insertion has been known for many years, point deletion is relatively unknown. The robustness and efficiency of a new algorithm are described. A variety of potential applications are summarized, and the included computer program may be used as the basis for many new projects. (C) 2003 Elsevier Science Ltd. All rights reserved.