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?