Hole detection in a planar point set: An empty disk approach

Given a planar point set S, outer boundary detection (shape reconstruction) is an extensively studied problem whereas, inner boundary (hole) detection is not a well researched one, probably because detecting the presence of a hole itself is a difficult task. Nevertheless, hole detection has wide applications in areas such as face recognition, model retrieval and pattern recognition. We present a Delaunay triangulation based strategy to detect the presence of holes and an algorithm to reconstruct them. Our algorithm is a unified one which reconstructs holes, both for a boundary sample (points sampled only from the boundary of the object) as well as for a dot pattern (points sampled from the entire object). Our method is a non-parametric one which detects holes irrespective of its shape. Assuming a sampling model, we provide theoretical analysis of the proposed algorithm, which ensures the correctness of the reconstructed holes, for specific structures. We conduct both qualitative and quantitative comparisons with existing methods and demonstrate that our method is better or comparable with them. Experiments with varying point densities and distributions demonstrate that the algorithm is independent of sampling. We also discuss the limitations of the algorithm.