Muthuganapathy Ramanathan

This paper presents an algorithm for generating the Interior Medial Axis Transform (iMAT) of 3D objects with free-form boundaries. The algorithm proposed uses the exact representation of the part and generates an approximate rational spline description of the iMAT. The algorithm generates the iMAT by a tracing technique that marches along the object's boundary. The level of approximation is controlled by the choice of the step size in the tracing procedure. Criteria based on distance and local curvature of boundary entities are used to identify the junction points and the search for these junction points is done in an efficient way. The algorithm works for multiply-connected objects as well. Results of the implementation are provided. © 2010 Elsevier Ltd. All rights reserved.

Discretizing the input curves into points or lines is a way of constructing an approximate Voronoi diagram. Sampling the input curves into points requires a fine sample density to obtain a reasonable topological and geometrical accuracy of the Voronoi diagram. In this work, it is shown that an accurate computation of the Voronoi diagram for a set of circles employing a very coarse sample set is possible. The approach proposes the selection of varying number of sample points on each circle dynamically, using the Delaunay graph of center points of circles. We then show that this approach can be used to identify neighborhood information of the circles. The touching disc method is then used to construct the Voronoi diagram with an algorithmic complexity of O(nlogn). The work also demonstrates the robustness and theoretical correctness of the proposed algorithm by considering inputs in non-general position and for a large number of circles of the order of 105.

We present a parallel algorithm for computing the Voronoi diagram of a set of spheres, S in R3. The spheres have varying radii and do not intersect. We compute each Voronoi cell independently using a two-stage iterative procedure, assuming the input spheres are in general position. In the first stage, an initial Voronoi cell for a sphere si is computed using an iterative lower envelope approach restricted to a subset of spheres Li⊂S. This helps to avoid defining the bisectors between all pairs of input spheres and develop a distributed memory parallel algorithm. We use the Delaunay graph of sample points from the input spheres to select the subset Li for computing each Voronoi cell. In the second stage, Voronoi cells obtained from the first stage are matched for updating the subsets. If additional spheres are added to a subset Li, the correctness of the computed vertices is verified with the bisectors of spheres newly added to Li. Results and performance of the algorithm show robustness and speed of the algorithm in handling a large set of spheres.

This paper proposes a unified approach towards computing geometry structures viz. Voronoi diagram, medial axis, Delaunay graph and α-hull of planar closed curves. It initially presents an algorithm for computing the Voronoi diagram of a set of planar freeform closed curves without approximating the curves using points, lines or biarcs. The algorithm starts by computing the minimum antipodal discs (MADs) for all pairs of curves and these MADs are systematically processed to identify all branch points. The key feature of the algorithm is that it computes a branch point without computing any of the bisectors a priori. Local computations of Voronoi segments are then done using the identified pairs of the segments of curves. The theoretical foundation of the algorithm has been first laid for a set of convex curves and then extended to non-convex curves. It has also been shown that the developed algorithm for the Voronoi diagram can also be used to compute related structures such as medial axis, Delaunay graph and α-hull. They have also been addressed without computing Voronoi edges/segments. Results of the implementation have been provided along with a detailed discussion of the algorithm.

Voronoi diagram (VD) is an extensively studied geometric entity since it has applications in fields such as computer graphics, computer vision, geometric modeling etc. In this paper, an algorithm for computing the VD of a set of planar freeform closed convex curves has been developed, without approximating the curves using points or lines. Algorithms for VD predominantly lie on computing the bisectors, a geometrically complex and a high degree curve even for inputs of low degree. Hence, a lot of processing is required to compute bisector segments that contribute to VD as well as in the computation of branch points. In this paper, it has been shown that computation of a branch point is possible without first computing either the bisector or segments of it. The algorithm uses the minimum antipodal discs (MADs) for all pairs of curves. Three touch discs (TTD) (circles touching three curves) are computed only for a specific set of three curves. Decision criteria for a TTD to become a branch disc (BD, i.e. empty TTD) have been addressed without using explicit curve containment check. Local computations of Voronoi segments are then done. The algorithm gives all branch points via centers of the branch discs along with the segments of curves that will contribute to VD. Results of implementation are provided along with analysis of the algorithm. © 2013 IEEE.

In this paper, the computation of positive α-hull for a set of planar closed C1-continuous curves has been addressed without sampling the curves into point-sets or polylines. Positive α-hull, so far, has been computed only for a set of points, using the farthest Delaunay triangulation, a dual of farthest Voronoi diagram. However, Delaunay triangulation does not exist for a set of curved boundaries and the computation of Voronoi diagram for such a set is still a topic of active research. The key insight behind our algorithm is to merge adjacent pairs of curves on the convex hull into a set of triplets. Along with a directed-cyclic graph and a R-List (list of radii), α-neighbours are derived. Using the constraint equations, α-discs are then computed. The algorithm is first provided for convex non-intersecting closed curves, but later explained how it can be generalized for non-convex curves. We show that the algorithm has time complexity of O(n2) time where n is the number of curves, which leads to a practical implementation with a reasonable running time in seconds for a few dozen curves. By directly operating on the curves, our method is both robust and accurate thus avoiding the problems that arise on polyline/point-set approximations of the curve networks.