Distributed boundary tracking using alpha and Delaunay-Cech shapes

For a given point set S in a plane, we develop a distributed algorithm to compute the α-shape of S. α-shapes are well known geometric objects which generalize the idea of a convex hull, and provide a good definition for the shape of S. We assume that the distances between pairs of points which are closer than a certain distance r>0 are provided, and we show constructively that this information is sufficient to compute the alpha shapes for a range of parameters, where the range depends on r. Such distributed algorithms are very useful in domains such as sensor networks, where each point represents a sensing node, the location of which is not necessarily known. We also introduce a new geometric object called the Delaunay-vCech shape, which is geometrically more appropriate than an α-shape for some cases, and show that it is topologically equivalent to α-shapes.