An incremental algorithm for simultaneous construction of 2D Voronoi diagram and Delaunay triangulation based on a face-based data structure. (July 2022)

• Record Type: Journal Article
• Authors: Shivanasab, Pooya; Ali Abbaspour, Rahim
• Is Part Of: Advances in engineering software. Volume 169(2022)
• Publication Date: 2022-07
• Subjects: Delaunay triangulation -- Voronoi diagram -- Computational geometry -- Incremental algorithms -- Data structures -- Point Insertion; Computer-aided engineering -- Periodicals; Engineering -- Computer programs -- Periodicals; Engineering -- Software -- Periodicals; Periodicals; 620.0028553
• DOI: 10.1016/j.advengsoft.2022.103129
• Languages: English
• ISSNs: 0965-9978

Abstract

Highlights: A new face-based data structure for storing information of the Voronoi diagram and Delaunay triangulation is proposed. A simple, fast and robust incremental algorithm with optimal complexity is proposed. Data structure could be easily converted to other edge-based data structures. Abstract: In this paper, a new incremental algorithm with an overall complexity of O ( n logn ) for constructing both the 2D Voronoi diagram (VD) and Delaunay triangulation (DT) is proposed. Moreover, a new face-based data structure is proposed which is more cost-effective in terms of memory than the previous edge-based data structures. The proposed data structure maintains the VD and DT in separate matrices, while establishing a connection between these two, allowing extracting neighborhoods and geometric information without the need for further processing in many applications. Moreover, the proposed data structure can be easily converted to the other edge-based data structures such as the Doubly Connected Edge List. The proposed algorithm for finding the nearest neighbor to the added point, in this incremental algorithm, has O( logn ) complexity. Evaluations performed by points with different numbers and distributions confirm the high robustness of the proposed algorithm against different point distributions and its O( n logn ) overall complexity.