On the average complexity of 3D-Voronoi diagrams of random points on convex polytopes

Oct 29, 2026

Upload by Melati

It is well known that the complexity of the 3-dimensional Voronoi diagram of n points, measured by the number of vertices, edges, and faces, can be as large as O(n^2). Under independently identically distributed points chosen uniformly from a full-dimensional region such as a cube or sphere, the expected complexity drops to O(n). This paper studies the intermediate case where points are drawn from a 2-dimensional region embedded in 3D space, and proves that when points come from a Poisson distribution on a convex polytope surface, the expected complexity is O(n).

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages35

Reading Time1 h 28 min

AccessFree to download

Abstract

Introduction

Voronoi diagram and complexity definition

Worst-case behavior in 3D

Average-case behavior in full-dimensional regions

Points sampled from lower-dimensional sets

Motivation: 2D surfaces in 3D

Prior work and research gap

Computational Geometry 25 (2003) 197–231 [www.elsevier.com/locate/comgeo](www.elsevier.com/locate/comgeo) On the average complexity of 3D-Voronoi diagrams of random points on convex polytopes ✩ Mordecai J. Golin a, Hyeon-Suk Na b a Department of Computer Science, Hong Kong Univ. of Sci. & Technology, Kowloon, HongKong b Department of Mathematics, Pohang University of Science and Technology, Pohang, South Korea Received 1 August 2001; accepted 23 January 2002 Communicated by J.D. Boissonnat Abstract It is well known that the complexity, i.e. the number of vertices, edges and faces, of the 3-dimensional Voronoi diagram of n points can be as bad as 􀀂(n2 ) . It is also known that if the points are chosen Independently Identically Distributed uniformly from a 3-dimensional region such as a cube or sphere, then the expected complexity falls to O(n) . In this paper we introduce the problem of analyzing what occurs if the points are chosen from a 2-dimensional region in 3-dimensional space. As an example, we examine the situation when the points are drawn from a Poisson distribution with rate n on the surface of a convex polytope. We prove that, in this case, the expected complexity of the resulting Voronoi diagram is O(n) . 􀀁 2003 Elsevier Science B.V. All rights reserved. Keywords: Voronoi diagrams; Convex polytopes; Random points; Average case analysis 1. Introduction Given a set Sn = {p1 , p2 , . . . , pn } ⊆ Rk of n points in k-dimensional Euclidean space, the Voronoi Diagram, VD(Sn), of Sn is a very well understood subdivision of Rk . For each point pi ∈ Sn there is an associated (convex) cell Ci = 􀀁x ∈ Rk: ∀j i, d(x, pi) 􀀁 d(x, pj)􀀂 , where d( · , ·) is the Euclidean distance function. By deﬁnition these cells partition Rk . The complexity of VD(Sn) is the number of lower dimensional pieces that compose VD(Sn). For example, in the planar case, ✩ The work of both authors was partially supported by HK RGC CERG grants 6082/97E, 6137/98E and 6206/02E. E-mail addresses: [golin@cs.ust.hk](golin@cs.ust.hk) (M.J. Golin), [hsnaa@postech.ac.kr](hsnaa@postech.ac.kr) (H.-S. Na). 0925-7721/03/$ – see front matter 􀀁 2003 Elsevier Science B.V. All rights reserved. doi:10.1016/S0925-7721(02)00123-2 198 M.J. Golin, H.-S. Na / Computational Geometry 25 (2003) 197–231 k = 2, VD(Sn) contains edges E and vertices V. The complexity of VD(Sn) will be | VD(Sn)| = |E| + |V| . Since it is also known that the 2-dimensional Voronoi Diagram is a planar graph, Euler’s theorem immediately implies that | VD(Sn)| = 􀀂(n) [11] . If k = 3 then VD(Sn) is composed not only of edges E and vertices V but also of the faces F of the convex cells. The complexity of VD(Sn) will then be | VD(Sn)| = |E| + |V| + |F| . In three dimensions it can be proven that | VD(Sn)| = O(n2) . For some cases, such as when all of the points in Sn are on the moment curve {(t, t2 , t 3 ) : t ∈ R}, it can be easily proven that |V| = 􀀂(n 2) so | VD(Sn)| = 􀀂(n 2) [7] . Another well known example of this worst-case behavior is built around two line segments L 1 ={(x, 0 , 0): x ∈ [0 , 12]} and L2 = { (1, y, 1): y ∈ [ 12 , 1]}; given any n 1 points on L 1 and any n2 points on L2 , |V| = 􀀂(n 1n2) . In particular if n 1 = n2 = ~~n~~2 then |V| = 􀀂(n 2) . Moving away from worst-case behavior to average-case behavior it has been shown that if n points of Sn are independently identically distributed (IID) chosen from the uniform distribution over a“reasonably” smooth full dimensional bounded region P such as a cube or sphere then E(| VD(Sn)|) =􀀂(n) [4–6] .1 Dropping the condition that P has full dimensionality dramatically changes the situation. For example, if we set P = L 1 ∪ L2 to be the union of the two 1-dimensional segments previously deﬁned and choose n points Sn uniformly at ‘random’ from P then n 1 = |Sn ∩ L1 |, the number of points on L 1 , is a binomial random variable with parameters n, 12 , so E(n 1) = ~~n~~2 and E(n21) ∼ ~~n~~42 . Since n2 = |Sn

FAQs

What is the worst-case complexity of a 3D Voronoi diagram of n points?

The complexity, defined by the number of vertices, edges, and faces, can be as bad as O(n^2).

How does expected complexity behave when points are uniformly sampled from a full-dimensional 3D region?

If the points are independently identically distributed uniformly from a reasonably smooth full-dimensional region (e.g., a cube or sphere), the expected complexity falls to O(n).

What expected complexity does the paper prove for points on the surface of a convex polytope?

When points are drawn from a Poisson distribution with rate n on the surface of a convex polytope, the expected complexity of the resulting Voronoi diagram is O(n).

Oct 29, 2026

Upload by Melati