# Why is my lower convex hull extraction algorithm not working?

Recently, I wrote an algorithm to obtain a delaunay triangulation of a random point set in $I=[-10,10]$x$[-10,10] \subset R^2$ by projecting these points onto the 3 dimensional paraboloid $z=x^2+y^2$, computing the convex hull, and then projecting the lower hull back onto $R^2$. I have verified that my convex hull algorithm is producing the correct result. Thus, I'm sure the problem is with my approach to obtaining the lower hull.

My lower hull extraction algorithm is similar to the incremental construction algorithm for generating convex hulls. That is, if we chose a point at negative infinity and shined a light from this point up toward the hull, we should be able to see the entire lower hull and be able to extract it completely. Computationally, of course, we cannot really use negative infinity as a number. But there must be some optimal point under the hull where the entire lower hull should be visible. (note: visibility here is determined by the signed orientation).

In my problem, since the point set is close to the origin (x,y)=(0,0), I chose to look for an optimal viewpoint along the negative z-axis. I figured that since the points on the lower hull are on the paraboloid $z=x^2 + y^2$, we can exploit the fact that the paraboloid is monotonically increasing as the (x,y) input coordinate moves in the radial direction away from the origin (0,0). Thus, the point in the point set whose x,y coordinate is furthest from the origin (0,0) will not only have the highest z-coordinate on the paraboloid, but also have the steepest tangent plane. Furthermore, where this tangent plane intersects the negative z-axis should be the optimal point which can see the entire lower hull.

When I experimented with this algorithm, it doesn't seem to work perfectly. That is, it is able to extract almost all the facets of the lower hull. It only seems to run into problems extracting facets whose projected delaunay triangles (onto $R^2$) are extremely thin and located on the 2D hull (that is, the outer boundary triangles). In these cases, i have had to lower my initial viewpoint by as much as $10^5$ or more, depending on the thinness of the triangle on the outer boundary of the delaunay triangulation in 2D.

I know that there are other approaches to obtaining the lower hull, but I'm really more interested in understanding where the flaw is in my original algorithm. Since the paraboloid is monotonically concave up, shouldn't the optimal viewpoint be located at a point on the z-axis where the tangent plane from $(x^*,y^*,z^*)$ hits the z-axis, where $(x^*,y^*,z^*)$ is the point projected from the given point set (in $R^2$) onto the paraboloid (in $R^3$ whose (x,y) coordinate is furthest from the origin?

• I don't do any work with Delaunay triangulation, but I do work with the concept of projection a lot, and I don't understand the issue with the "view point". If you pick any point on the $z$-axis below the plane $z = 0$, the projection should have nullspace $(0,0,1)$ (you're projecting along the $z$-axis). I'm assuming that you want the range of the projection to span $\{(1,0,0), (0,1,0)\}$ to recover the points in $\mathbb{R}^{2}$ that you had mapped to $\mathbb{R}^{3}$ (i.e., just keep the first two coordinates). Why wouldn't keeping the first two coordinates of every point suffice? – Geoff Oxberry Mar 5 '12 at 9:30
• The key is not just to obtain the points in the triangulation, but the triplets that form each triangle in the triangulation. It may not be immediately obvious which triplets are specifically on the lower part of the hull. – Paul Mar 5 '12 at 14:09
• There's nothing wrong with your method in particular: it sounds like you're just getting into precision issues at the boundary. In general, any point below the xy plane suffices for a "viewpoint". – Suresh Mar 5 '12 at 23:25
• @Suresh: That's not quite true... If a point is too close to the hull, some facets on the hull will not be visible (in the sense of orientation) from the point. – Paul Mar 5 '12 at 23:34
• Ah, but "visibility" is parallel visibility here, not point visibility. That's the sense in which the lower CH is visible. that is to say, any vertical ray stabs a facet of the DT first. – Suresh Mar 6 '12 at 0:25