Skip to main content
U.S. flag

An official website of the United States government

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



Javier Bernal


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.
NIST Interagency/Internal Report (NISTIR) - 4340
Report Number


algorithm, computational geometry, expected complexity, expected linear, expected time analysis, Voronoi diagram


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], (Accessed June 15, 2024)


If you have any questions about this publication or are having problems accessing it, please contact

Created June 1, 1990, Updated November 10, 2018