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

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2013-04-20T04:40:27.450Z
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.
Jeffε
CC BY-SA 3.0
2013-04-20T01:20:12.677Z
2013-04-20T01:20:12.677Z
David Eppstein
<p>Given a set of points $V \subset \mathbb{R}^d$, the <em>Voronoi diagram</em> 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 <a href="http://en.wikipedia.org/wiki/Voronoi_diagram" rel="nofollow">Wikipedia</a>.</p>

<p>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 &gt; 3$ there are even worse cases.</p>

<p>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.</p>

<p>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 <em>outer Voronoi diagram</em>.</p>

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

<ds.data-structures><cg.comp-geom><voronoi>
Outer part of Voronoi diagram in 3D
Alex ten Brink
# Outer part of Voronoi diagram in 3D

(Asked by: username_0 on 2013-04-19)

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](http://en.wikipedia.org/wiki/Voronoi_diagram).

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?

**Tags:** ds.data-structures, cg.comp-geom, voronoi

---

## 1 answers

### Answer by username_1 on 2013-04-20. Score: 6 | Accepted answer

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.

> **Comments:**
> **username_2**: 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.  

---

