Outer part of Voronoi diagram in 3D
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.