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 3D point cloud, which I can reconstruct back the 3D surface easily by using any existing 3D interpolation algorithm.

The question now is, let's say I have only a small neighbourhood of the 3D point cloud, and I am required to reconstruct back the 3D surface for that particular neighbourhood, how influential is the 3D points not in the neighbourhood contribute to the 3D surface shape of that particular chosen neighbourhood?

Obviously, the answer would depend on how densely populated the 3D points are, and how big the neighbourhood is. But is it possible to quantify those?

My question is algorithm independent. I just want to know the general characteristics of the influence of points from afar on a neighbourhood .

I am aiming to compare the following interpolation method:

  1. Triangle-based linear interpolation
  2. Triangle-based cubic interpolation
  3. Nearest neighbor interpolation

Note: when I say 3D surface, I mean a 2-manifold embedded in 3D.

share|improve this question
Your question only makes sense in the context of a specific reconstruction algorithm...which you didn't specify. –  Darsh Ranjan Dec 10 '09 at 8:43
I think all such algorithms reconstruct the surface from local data. So the answer will most likely depend on what the boundary of your local point set looks like. –  davidk01 Dec 10 '09 at 9:26
Also, I think the underlying assumption is the data comes from some continuous model so point clouds close to corners will likely be very influenced by far off points. –  davidk01 Dec 10 '09 at 9:30
Shape of your surface depends on your interpolation methods! Do you use splines or polinomials or LPC or what else ? –  psihodelia Dec 10 '09 at 11:16
Your question is still very unclear. You will reconstruct a patch of surface from a neighborhood of points, and you ask how influential are "points not in that neighborhood." The only sensible way I can interpret that is to suppose the neighborhood were enlarged to include more points, and then ask how similar the new and old reconstructions are on the smaller neighborhood. That depends on how you do the reconstruction. Different methods will give you different reconstructions for the same point set and can behave very differently. –  Darsh Ranjan Dec 11 '09 at 8:42
show 1 more comment

1 Answer

While your question is still rather unspecified, and does seem to be linked to a specific algorithm, there are some general principles governing influence. Roughly speaking, there is a notion called the local feature size (the radius of a ball near a boundary point that is simultaneously tangent to two points on the boundary), and many (if not most) reconstruction algorithms express local density bounds in terms of this function.

More generally, this relates to the curvature at that point

share|improve this answer
Thanks, you have any papers on that? –  Graviton Dec 11 '09 at 2:44
Browsing papers by Nina Amenta (UC Davis) and Tamal Dey (OSU) should get you what you need. Specifically, look at power crust and COCONE. –  Suresh Venkat Dec 12 '09 at 6:36
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.