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

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