I am looking to polyhedronize an arbitrary set of points, $S \subset \mathbb{R}^3$. That is to say, I want to construct a polyhedron whose set of vertices is exactly $S$.
I was reading the following paper:
http://cgm.cs.mcgill.ca/~godfried/publications/bbdlink.pdf
On page 10 it states the following:
Theorem:
A set of points $S$ in space admits a monotonic polyhedronization that be obtained in $O(n \text{log} n)$ time.
In the paper, the set of points in $S$ is also assumed to be in general position.
The paper then goes on to give the proof.
Proof:
First compute the convex hull $CH(S)$ of $S$. If no points of $S$ lie inside the convex hull we are done because the polyhedron $CH(S)$ is a monotonic polyhedron. Otherwise, the shadow boundary of the convex hull of $S$, in other words the set of edges common to $CH_{L}(S)$ and $CH_{U}(S)$. Let $S_{U}$ be the subset of points in $S$ which are not vertices of $CH_{L}(S)$. Triangulate in any way the projection of the set $S_{U} \cup B$ on the $xy$-plane, and lift each triangle to the points that projected onto its vertices. By gluing along $B$ this terrain with $CH_{L}(S)$ we obtain the desired monotonic polyhedron. Computing the convex hull and constructing a triangulation of the projected points can be done in time $O(n \text{log} n)$, which is the overall running time as the lifting step only requires $O(n)$ times.
My first question is can we still achieve $O(n \text{log} n)$ time if we do not require that the points of $S$ be in general position? If we can then can we use the same construction for the polyhedron?