Outer part of Voronoi diagram in 3D

Question

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?

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.