Published in

Springer, Algorithmica, 4(9), p. 329-356, 1993

DOI: 10.1007/bf01228508

Links

Tools

Export citation

Search in Google Scholar

A semidynamic construction of higher-order voronoi diagrams and its randomized analysis

Journal article published in 1993 by Jean-Daniel Boissonnat, Olivier Devillers ORCID, Monique Teillaud
This paper is available in a repository.
This paper is available in a repository.

Full text: Download

Green circle
Preprint: archiving allowed
Upload
Orange circle
Postprint: archiving restricted
Upload
Red circle
Published version: archiving forbidden
Policy details
Data provided by SHERPA/RoMEO

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 orderlek Voronoi diagrams, can be done in O(n logn+k 3n) 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 lceil(d+1)/2rceil+1 n lfloor(d+1)/2rfloor) and space complexityO(k lceil(d+1)/2rceil n lfloor(d+1)/2rfloor). The algorithm is simple and experimental results are given.