1
$\begingroup$

Say I have N points sampled on a surface in 3 dimensions (ie. points on the surface of a sphere, 1-torus etc.). Is there an algorithm that would be able to count the number of holes in the surface formed by those point (ie. zero holes for the sphere, 1 hole for the 1-torus etc)?

Edit: As a constraint, the points that make up the surface are expected to have an equilibrium distance that is in general much smaller than the dimensions of the surface. For instance, if the points make up a sphere of radius 40, we can expect each point to have neighbours within a distance of 2 units from each other, although this equilibrium distance is noisy (ie. fluctuates randomly with 2 as mean and small std).

$\endgroup$
1
  • 1
    $\begingroup$ It is unsolvable in practice, because there are infinitely many squiggly surfaces that could be consistent with those $N$ points. You will need to provide some extra constraints. Do you know that the shape falls into one of a small list of possibilities? Do you have extra side information about the curvature of the shape, etc.? What is the context in which this question arose? What is the motivation? I encourage you to edit the question to elaborate. $\endgroup$
    – D.W.
    Commented Jan 11 at 22:04

1 Answer 1

1
$\begingroup$

You are looking for persistent homology, a branch of computational topology that studies precisely the question you asked.

Roughly, the idea is as follows. Pick a "resolution radius $r$", draw a ball of radius $r$ around each sample point, and compute the resulting homology, let's write it as $H_r$ (homology "counts holes" and gives you other information about the space). Depending on the chosen resolution, you get the relevant information. Persistent homology studies, among other things, how to efficiently compute the $H_r$'s, say as $r$ increases.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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