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.

On the expected complexity of the 3-dimensional Voronoi diagram

Published

Author(s)

Javier Bernal

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, work by Bentley, Weide and Yao is extended to show that the Voronoi diagram for 5 has an expected 0{n) number of faces. A consequence of the proof of this result is that the Voronoi diagram for 5 can be constructed in expected 0[n) time.
Citation
NIST Interagency/Internal Report (NISTIR) - 4321
Report Number
4321

Keywords

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

Citation

Bernal, J. (1990), On the expected complexity of the 3-dimensional Voronoi diagram, NIST Interagency/Internal Report (NISTIR), National Institute of Standards and Technology, Gaithersburg, MD, [online], https://doi.org/10.6028/NIST.IR.4321 (Accessed March 28, 2024)
Created May 1, 1990, Updated November 10, 2018