A semidynamic construction of higher-order voronoi diagrams and its randomized analysis |
| |
Authors: | Jean -Daniel Boissonnat Olivier Devillers Monique Teillaud |
| |
Affiliation: | (1) Institut National de Recherche en Informatique et Automatique, B.P. 93, 06902 Sophia-Antipolis cedex, France |
| |
Abstract: | Thek-Delaunay tree extends the Delaunay tree introduced in [1], and [2]. It is a hierarchical data structure that allows the semidynamic construction of the higher-order Voronoi diagrams of a finite set ofn points in any dimension. In this paper we prove that a randomized construction of thek-Delaunay tree, and thus of all the orderk Voronoi diagrams, can be done inO(n logn+k3n) expected time and O(k2n) expected storage in the plane, which is asymptotically optimal for fixedk. Our algorithm extends tod-dimensional space with expected time complexityO(k(d+1)/2+1n(d+1)/2) and space complexityO(k(d+1)/2n(d+1)/2). The algorithm is simple and experimental results are given.This work has been supported in part by the ESPRIT Basic Research Action No. 3075 (ALCOM). |
| |
Keywords: | Computational geometry Dynamic algorithm Randomized complexity analysis Orderk Voronoi diagram |
本文献已被 SpringerLink 等数据库收录! |