Abstract | ||
---|---|---|
For a given point set $S$ in a plane, we develop a distributed algorithm to compute the $\alpha-$shape of $S$. $\alpha-$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-\v{C}ech shape, which is geometrically more appropriate than an $\alpha-$shape for some cases, and show that it is topologically equivalent to $\alpha-$shapes. |
Year | Venue | Field |
---|---|---|
2013 | CoRR | Discrete mathematics,Combinatorics,Alpha shape,Convex hull,Distributed algorithm,Topological conjugacy,Point set,Wireless sensor network,Mathematics,Delaunay triangulation |
DocType | Volume | Issue |
Journal | abs/1302.3982 | 6 |
Citations | PageRank | References |
1 | 0.38 | 7 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Harish Chintakunta | 1 | 36 | 6.05 |
Hamid Krim | 2 | 520 | 59.69 |