Given a set of points $V \subset \mathbb{R}^d$, the Voronoi diagram divides $\mathbb{R}^d$ into $|V|$ parts such that for every $v \in V$, the part of $\mathbb{R}^d$ for which $v$ is closer than any other point in $V$ is exactly a part of the diagram. See also Wikipedia.

It is well known that for $d=2$, its complexity is $\Theta(n)$ and it can be computed in $O(n \log n)$ time. For $d=3$ however, there are families of pointsets for which the Voronoi diagram has complexity $\Theta(n^2)$, and for $d > 3$ there are even worse cases.

However, from what I've seen, all these bad cases seem to occur 'inside' the pointset, and for the purpose I have in mind, this inside is irrelevant.

Let $m = \max \{ |uv| \mid u, v \in V \}$. Suppose therefore we take a bounding box around our pointset $V$ and increase its size by some constant factor $c$ so that any point in $V$ is at least $m (c-1)/2$ away from this larger box. We take the Voronoi diagram for $V$ and remove the part that is inside the box. We name this new diagram the outer Voronoi diagram.

What is the worst-case complexity of the outer Voronoi diagram for $d=3$? What if $d>3$? If this complexity is smaller than the normal Voronoi diagram, can we also compute it faster?


1 Answer 1


I think it's still quadratic, for arbitrarily large choice of $c$.

Let $\epsilon$ be small, and place two line segments $s_1$ and $s_2$ of length $\epsilon^2$, each tangent to the unit sphere at their midpoints, at distance roughly $\epsilon$ apart from each other. Because the line segments are so short, the Voronoi diagram of the two line segments approximates the Voronoi diagram of the two midpoints, which is just a plane $P$ bisecting the sphere. At the center of the sphere, the two equal closest sites are the midpoints of the segments.

Now, place equally spaced points on each segment. This will cause the Voronoi diagram of the points of a single segment $s_i$ to consist of two halfplanes separated by many thin slabs bounded by parallel planes, that all pass near the center of the sphere. These slabs intersect $P$ in thin parallel two-dimensional stripes, whose slope can be controlled by the angle at which $s_i$ is placed relative to the sphere. By choosing the angles of $s_1$ and $s_2$ so that they are skew to each other, the stripes for $s_1$ on $P$ can be made to cross the stripes for $s_2$ on $P$, near the center of the sphere. This in turn means that for each pair of a Voronoi region from $s_1$ and a Voronoi region from $s_2$, there is a boundary between the two regions near the center of the sphere. Thus, the Voronoi diagram has quadratic complexity in a region of space (the center of the sphere) that is far from a bounding box of the generating sites.

  • 5
    $\begingroup$ You can get precisely the same effect with an arbitrarily small segment of the moment curve $(t, t^2, t^3)$ or the helix $(t, \cos t, \sin t)$. In both cases, every pair of Voronoi cells shares a common facet that passes outside the scaled bounding box of the points. All $\Omega(n^2)$ Voronoi vertices lie in an arbitrarily small region of the center of a sphere that osculates the curve within the segment that contains all the points. $\endgroup$
    – Jeffε
    Commented Apr 20, 2013 at 4:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.