Paper detail

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-Čech shape, which is geometrically more appropriate than an $α-$shape for some cases, and show that it is topologically equivalent to $α-$shapes.