Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
If you want an implementation, see qhull. –  lhf Sep 22 '12 at 1:45
add comment

1 Answer

up vote 1 down vote accepted

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.

share|improve this answer
    
I was asking whether it would work in higher dimensions and whether there are any special considerations concerning coplanar points. Thanks for the useful resources and explanation! –  Ian Mallett Sep 24 '12 at 20:32
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.