Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I have a data set that essentially looks like the picture below, i.e., it's given by sets of points in $\mathbb{R}^3$ that sample the cross-sections of a certain surface that in principle I do not know. In fact, I would like to recover this surface or, more precisely, a triangulation/mesh of it.

3-Dimensional Triangulation/Tesselation of Two PointClouds

In this particular example, it is not difficult to see that we have a section of a cone. In this sense, I do not want to compute the convex hull of these points, but instead I just want to find its boundary (if this makes any sense; I actually don't know whether it does), i.e., I want to find the surface that one could obtain by simply joining the "corresponding" points in both "slices". (I've put "corresponding [points]" in quotes because I believe it's not straightforward to perform this matching exercise, i.e., find the point on the adjacent slice that isn't necessarily the closest one in the $\mathbb{R}^3$ metric, but would correspond to the closest one if we projected one slice into another and considered only the $\mathbb{R}^2$ distance between them, as seen below.)

2-Dimensional Projection Along the Z-axis

share|improve this question
I'm not sure I understand what your question is, but the matching method you've described seems reasonable. If the cross sections are in parallel planes project one sample to the other sample's plane and pair each point in one sample to one of its nearest neighbors in the other sample. You can make triangles out of the triples of (1) a point from the first sample (2) one of its closest neighbors in the other sample (in the shared plane) and (3) one of its nearest neighbors in the same sample. –  Aaron Golden Feb 23 '13 at 0:15
@Aaron: this is precisely what i had in mind when i wrote the question last night — sorry if i wasn't clear enough (at that point of the day i couldn't think straight anymore :-P). And thank you for your time and attention, i really appreciate it: i've been working with this problem for a couple of months now, and progress has been à la "two steps forwards, one backwards". ;-) –  Daniel Feb 23 '13 at 18:47
add comment

1 Answer

up vote 2 down vote accepted

This is a problem that has been studied for a long time. I showed with my students Carol Gitlin and Vinita Subramanian, that there does not always exist a polyhedron that connects two arbitrary polygons in parallel slices. In other words, Daniel's hope to "simply [join] the 'corresponding' points in both 'slices' " cannot always be realized:

C. Gitlin, J. O'Rourke, V. Subramanian. "On reconstruction of polyhedra from parallel slices," International Journal of Computational Geometry & Applications, 6(1) 1996, 103-122.

These two polygons constitute a counterexample:

There is a very nice summary of the early work, and a practical algorithm, in:

Gill Barequet, Daniel Shapiro, Ayellet Tal. "History Consideration in Reconstructing Polyhedral Surfaces from Parallel Slices." Proceedings of IEEE Visualization, 1996. (CiteSeer link)

Maybe look at this more recent work?:

Samir Akkouche, Eric Galin. "Implicit surface reconstruction from contours." The Visual Computer. August 2004, Volume 20, Issue 6, pp 392-401. (Springer link)


share|improve this answer
@O'Rourke: Professor, thank you much for your help, and for the references as well — i really appreciate them, and i'm sure they'll lead me forward. As i mentioned above, i wasn't very clear-headed when i wrote up this question, but i believe that you capture the essence of my doubts (which i have a hard time putting in words, being fresh to this problem and field and all). In hindsight, i should've asked earlier… ;-) –  Daniel Feb 23 '13 at 18:58
@Daniel: I should have been clearer myself: "I want to find the surface that one could obtain by simply joining the 'corresponding' points in both 'slices.'" What my paper shows is that sometimes it is impossible to find such a correspondence. But this negative result is balance by many practical algorithms. –  Joseph O'Rourke Feb 23 '13 at 23:30
@O'Rourke: Professor, i haven't yet had a chance to check the references you posted, so maybe i'm asking something that you already answered, but there you go: Do you know where i can find out more about such algorithms you mentioned? (I'm fairly convinced that my problem will fall into this "impossible" category, given how feature-rich each slice is, but maybe i can work around it somehow…) –  Daniel Feb 24 '13 at 0:45
@Daniel: I would start with the Barequet et al. paper. It is a very good paper, very clear. And they were well aware of my negative result. (The link I provided leads to the conference version PDF, rather than the journal version.) –  Joseph O'Rourke Feb 24 '13 at 0:52
add comment

Your Answer


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.