Bernal, J.
(1990),
An expected linear 3-dimensional Voronoi diagram algorithm, NIST Interagency/Internal Report (NISTIR), National Institute of Standards and Technology, Gaithersburg, MD, [online], https://doi.org/10.6028/NIST.IR.4340
(Accessed October 24, 2025)
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
Secure .gov websites use HTTPS
A lock (
) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.
An expected linear 3-dimensional Voronoi diagram algorithm
Published
Author(s)
Abstract
Let 5 be a set of n sites chosen independently from a uniform distribution in a cube in 3 dimensional Euclidean space. In this paper, an expected 0{n) algorithm for constructing the Voronoi diagram for 5 together with numerical results obtained from an implementation of the algorithm are presented.Citation
NIST Interagency/Internal Report (NISTIR) - 4340
Report Number
4340
NIST Pub Series
Pub Type
NIST Pubs
Download Paper
Keywords
algorithm, computational geometry, expected complexity, expected linear, expected time analysis, Voronoi diagram
Citation
Issues
If you have any questions about this publication or are having problems accessing it, please contact [email protected].
Created June 1, 1990, Updated November 10, 2018