<p>In 2010 <a href="http://link.springer.com/chapter/10.1007%2F978-3-642-15775-2_34">Hemmer et al.</a> gave an exact algorithm for the Voronoi diagram of lines in $\mathbb{R}^3$. In their introduction, they state that the $\Omega(n^2)$ lower bound and $O(n^{3+\varepsilon})$ upper bound are still the best known on the combinatorial complexity of the resulting Voronoi diagram. Their algorithm runs in time $O(n^{3+\varepsilon})$, matching the upper bound on the combinatorial complexity.</p>

<p>As far as I know, theirs was the first (and still, only) exact algorithm for this problem, so I would guess that there haven't been any further improvements on the combinatorial complexity front either.</p>

CC BY-SA 3.0
2015-12-06T00:58:36.717Z
2015-12-06T02:09:26.817Z
2015-12-06T02:09:26.817Z
Huck Bennett
<p>The problem is still open, although some progress was made on related problems (see  <a href="http://arxiv.org/abs/1312.2194" rel="nofollow">http://arxiv.org/abs/1312.2194</a>). It is known that if you are willing to use an approximate metric then the upper bound drops to near quadratic. See the work by Koltun and Sharir, I think.</p>

CC BY-SA 3.0
2016-05-02T02:08:23.533Z
2016-05-02T02:08:23.533Z
Sariel Har-Peled
<p>Let $S$ be a set of lines (or line segments) in $\mathbb{R}^3$. Consider the Voronoi diagram $VD(S)$. The best lower bound on the complexity of $VD(S)$ is $\Omega(n^2)$ and the best upper bound is $O(n^{3+\epsilon})$ [1]. What is the current state of research on this problem? Is anything more recent than the references in [2] known?</p>

<p>[1] Almost tight upper bounds for lower envelopes in higher dimensions.</p>

<p>[2] <a href="http://cs.smith.edu/~orourke/TOPP/P3.html">http://cs.smith.edu/~orourke/TOPP/P3.html</a></p>

<co.combinatorics><computational-geometry><convex-geometry>
Voronoi Diagram of Lines
user36641
# Voronoi Diagram of Lines

(Asked by: username_0 on 2015-12-05)

Let $S$ be a set of lines (or line segments) in $\mathbb{R}^3$. Consider the Voronoi diagram $VD(S)$. The best lower bound on the complexity of $VD(S)$ is $\Omega(n^2)$ and the best upper bound is $O(n^{3+\epsilon})$ [1]. What is the current state of research on this problem? Is anything more recent than the references in [2] known?

[1] Almost tight upper bounds for lower envelopes in higher dimensions.

[2] <http://cs.smith.edu/~orourke/TOPP/P3.html>

**Tags:** co.combinatorics, computational-geometry, convex-geometry

---

## 2 answers

### Answer by username_1 on 2015-12-06. Score: 7

In 2010 [Hemmer et al.](http://link.springer.com/chapter/10.1007%2F978-3-642-15775-2_34) gave an exact algorithm for the Voronoi diagram of lines in $\mathbb{R}^3$. In their introduction, they state that the $\Omega(n^2)$ lower bound and $O(n^{3+\varepsilon})$ upper bound are still the best known on the combinatorial complexity of the resulting Voronoi diagram. Their algorithm runs in time $O(n^{3+\varepsilon})$, matching the upper bound on the combinatorial complexity.

As far as I know, theirs was the first (and still, only) exact algorithm for this problem, so I would guess that there haven't been any further improvements on the combinatorial complexity front either.


---

### Answer by username_2 on 2016-05-02. Score: 3

The problem is still open, although some progress was made on related problems (see <http://arxiv.org/abs/1312.2194>). It is known that if you are willing to use an approximate metric then the upper bound drops to near quadratic. See the work by Koltun and Sharir, I think.


---

