# Distributed boundary tracking using alpha and Delaunay-Cech shapes

arXiv: https://arxiv.org/abs/1302.3982 · HTML: https://mlsanity.com/paper/1302.3982/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Feb 2013.

## Built on by (most cited first, 1 of 1)

- [Boundary Detection Algorithm Inspired by Locally Linear Embedding](https://mlsanity.com/paper/2406.18456/) (2024)

## Abstract (arXiv)

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.