Muthuganapathy Ramanathan

Given a planar point set sampled from a curve, the curve reconstruction problem computes a polygonal approximation of the curve. In this paper, we propose a Delaunay triangulation-based algorithm for curve reconstruction, which removes the longest edge of each triangle to result in a graph. Further, each vertex of the graph is checked for a degree constraint to compute simple closed/open curves. Assuming ϵ-sampling, we provide theoretical guarantee which ensures that a simple closed/open curve is a piecewise linear approximation of the original curve. Input point sets with outliers are handled as part of the algorithm, without pre-processing. We also propose strategies to identify the presence of noise and simplify a noisy point set, identify self-intersections and enhance our algorithm to reconstruct such point sets. Perhaps, this is the first algorithm to identify the presence of noise in a point set. Our algorithm is able to detect closed/open curves, disconnected components, multiple holes and sharp corners. The algorithm is simple to implement, independent of the type of input, non-feature specific and hence it is a generalized one. We have performed extensive comparative studies to demonstrate that our method is comparable or better than other existing methods. Limitations of our approach have also been discussed.

We propose an algorithm to compute and maintain the spatial proximities of planar points continuously moving along predefined linear trajectories. The proximity information of moving points is captured and maintained via the well known Gabriel graph adapted for the kinetic setting, called kinetic Gabriel graph (KGG). Kinetic Gabriel Graph is built on top of the kinetic framework of Delaunay graph. Leveraging the positioning of the Delaunay circumcenters relative to the corresponding Delaunay triangles, we formulate `Gabriel certificates' that determine whether or not an edge of a Delaunay triangle is Gabriel. Then we employ an edge tagging algorithm to maintain the set of all Gabriel edges from the Delaunay graph as the points move. The proposed algorithm has been evaluated using numerous test data, and various computational implications with respect to the topological events occurring in the data structure during the points' movement have been discussed. We also provide a conceptual demonstration of the practical potentials of the proposed algorithm in video based monitoring systems.

Reconstruction problem in R2 computes a polygon which best approximates the geometric shape induced by a given point set, S. In R2, the input point set can either be a boundary sample or a dot pattern. We present a Delaunay-based, unified method for reconstruction irrespective of the type of the input point set. From the Delaunay Triangulation (DT) of S, exterior edges are successively removed subject to circle and regularity constraints to compute a resultant boundary which is termed as ec-shape and has been shown to be homeomorphic to a simple closed curve. Theoretical guarantee of the reconstruction has been provided using r-sampling. In practice, our algorithm has been shown to perform well independent of sampling models and this has been illustrated through an extensive comparative study with existing methods for inputs having varying point densities and distributions. The time and space complexities of the algorithm have been shown to be O(nlogn) and O(n) respectively, where n is the number of points in S.

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.

Given a finite set of points P ? R3, sampled from a surface S, surface reconstruction problem computes a model of S from P, typically in the form of a triangle mesh. The problem is ill-posed as various models can be reconstructed from a given point set. In this paper, curve reconstruction in R2, is initially looked at using the Delaunay triangulation (DT) of a point set. The key idea is that the edges in the DT are prioritized and the interior or exterior edges of the DT are removed as long as it has at least one adjacent triangle. Theoretically, it is shown that the reconstruction is homeomorphic to a simple closed curve. Extending this to 3D, an approach based on ‘retaining solitary triangles’ and ‘removing triangles anywhere’ has been proposed. An additional constraint based on the circumradius of a triangle has been employed. Results on public and real-world scanned data, and qualitative/quantitative comparisons with existing methods show that our approach handles diverse features, outliers and noise better or comparable with other methods.