Voronoi Diagram of Lines
In 2010 Hemmer et al. 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.