3D Delaunay Triangulation by 4D Paraboloids

Question

I'm working on a Delaunay triangulation algorithm (specifically, I care about triangulating points on any 2D subspace of (plane in) R3).

I understand how 2D triangulation can be achieved by computing the convex hull of a corresponding 3D paraboloid.

I am therefore attempting something similar with a 4D paraboloid to get 3D triangulation. I'm assuming a similar approach works (find the convex hull of a 4D paraboloid and the projection back to 3D gives the triangulation of my plane).

My question: does it? Can the convex hull of a corresponding 4D paraboloid be used to construct a Delaunay triangulation of 3D points lying in a 2D plane?


_{^{Yes, I already know that I can make the problem easier by transforming the 2D plane to R2, and then using the 3D paraboloid/2D plane.}}

Answer 1

I'm not quite sure whether you're asking whether the paraboloid approach works in higher dimensions, or whether you know that it does and are only asking whether it will work for your degenerate case of coplanar points.

Regarding the more general question, the first hit for a Google search for "delaunay paraboloid" is this excerpt from Geometric Methods and Applications by Jean H. Gallier, which asserts that the paraboloid approach works in any number of dimensions.

Regarding the specific question about coplanar points, I think you'll run into rounding problems. The convex hull algorithm would have to be able to find and represent the degenerate hull consisting of triangles instead of tetrahedra, and rounding would cause it to generate very thin tetrahedra instead. If you find a way to deal with this, the approach should work; the points will all lie on a three-dimensional sub-paraboloid of the four-dimensional paraboloid, and in the absence of rounding they will have a degenerate three-dimensional convex hull consisting of triangles. It might help to think of the case one dimension down, where you have colinear points in two dimensions that all get mapped to a parabola, so their convex hull is just a chain of lines, which rounding would turn into very thin triangles.

You might also want to take a look at this MO thread.