This section covers how to obtain a sub-sampled set of points for extraction of local neighborhoods of the point clouds. The idea behind using local neighborhoods is that some information is best not calculated for every point in a point cloud, but rather at a subset of points, called central points. Usually the information will require computations with a small region around each central point. Once computed for the small region, there is no need to compute it at points in the small region that differ from the chosen central point.

Below are a few ways to obtain these local neighborhoods. They are not all the same. Some allow for the neighborhood regions to overlap, some may not. all involve specifying how big the neighborhood should be. Usually that is done through a radius specification $\bar \rho$.

The connectivity matrix approach requires one to select a radius $\rho$, then generate a connectivity matrix with that radius. Given a central point, all points that are connected to it form the neighborhood. That's easy to find. The goal then is to come up with a set of central points. One basic procedure is as follows:

1. First define an inPlay array consisting of all point in the point cloud. False if the point has been taken and is not available for use. True if it is still in play. Mark all entries as true.
2. Pick a point that has not been taken and mark it as taken.
3. Find the connected neighbors of the point. That is its neighborhood. Here, it doesn't matter if they are taken or not.
4. Mark them as taken also.
5. While there is still a point in play, repeat.

The trick of the approach is to be able to pick an inPlay point. The easiest is to simply find the first non-zero entry and use that as the new central point. Mind you, the above says how to do the picking and neighborhood selection. The procedure is missing the storing of that center point and the local neighborhood into some data structure for later use. The easiest structure to use would be a Matlab cell array that contains lists of indices of all points each the neighborhood. The first index in the list should be the central point, while the 2:end-1 indices are the neighbors. Processing the data for some computation will then use a for loop through the cell array and use of the index array at each cell location.

Note: The reason that a cell array is needed is that the set of neighbors will change from central point to central point. A cell array can store lists that have different lengths.

Note: Some local neighborhoods will not have enough points to compute anything useful (imagine a lone point far away from all the others). In that case, it is up to your processing algorithm to detect that and return some sensible default value.