A simple and efficient algorithm for dot patterns reconstruction

The problem of reconstructing the shape of dot patterns (sampled planar connected regions) is extensively studied in the literature. Up till now, the existing works do not provide guarantee for the correctness of the obtained solution, usually the results was validated empirically according to human perception. In this article, we present a new algorithm that guarantees reconstruction of the shape for a set of points satisfying some density conditions. Many experimental results show that the algorithm usually gives an adequate reconstruction for non-uniformly and weakly-sampled patterns. An advantage of the algorithm is its simplicity. Once the Delaunay triangulation of the input data is computed, simple rules are applied to the Delaunay edges in order to select those belonging to the reconstruction graph.