Delaunay triangulations approximate anchor hulls

ABSTRACT

Recent results establish that a subset of the Voronoi diagram of a point set that is sampled from the smooth boundary of a shape approximates the medial axis. The corresponding question for the dual Delaunay triangulation is not addressed in the literature. We show that, for two dimensional shapes, the Delaunay triangulation approximates a specific structure which we call anchor hulls. As an application we demonstrate that our approximation result is useful for the problem of shape matching.

REFERENCES

• 1: H. Alt and L. J. Guibas. Discrete geometric shapes: matching, interpolation, and approximation: a survey. Tech. report B 96-11, EVL-1996-142, Institute of Computer Science, Freie Universität Berlin, 1996.
• 2: Nina Amenta , Marshall Bern , David Eppstein, The crust and the &Bgr;-Skeleton: combinatorial curve reconstruction, Graphical Models and Image Processing, v.60 n.2, p.125-135, March 1, 1998 [doi>10.1006/gmip.1998.0465 ]
• 3: N. Amenta and M. Bern. Surface reconstruction by Voronoi filtering. Discr. Comput. Geom.22 (1999), 481--504.
• 4: N. Amenta, S. Choi and R. Kolluri. The power crust, union of balls, and the medial axis transform. Comput. Geom. Theory Appl.19 (2001), 127--153.
• 5: Esther M. Arkin , L. Paul Chew , Daniel P. Huttenlocher , Klara Kedem , Joseph S. B. Mitchell, An Efficiently Computable Metric for Comparing Polygonal Shapes, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.13 n.3, p.209-216, March 1991 [doi>10.1109/34.75509 ]
• 6: Dominique Attali , Jean-Daniel Boissonnat , André Lieutier, Complexity of the delaunay triangulation of points on surfaces the smooth case, Proceedings of the nineteenth annual symposium on Computational geometry, June 08-10, 2003, San Diego, California, USA [doi>10.1145/777792.777823]
• 7: J.-D. Boissonnat and F. Cazals. Natural neighbor coordinates of points on a surface. Comput. Geom. Theory Appl.19 (2001), 87--120.
• 8: Jonathan W. Brandt , V. Ralph Algazi, Continuous skeleton computation by Voronoi diagram, CVGIP: Image Understanding, v.55 n.3, p.329-338, May 1992 [doi>10.1016/1049-9660(92)90030-7]
• 9: H. I. Choi, S. W. Choi and H. P. Moon. Mathematical theory of medial axis transform. Pacific J. Mathematics181 (1997), 57--88.
• 10: T. K. Dey. Curve and surface reconstruction. Chapter in Handbook on Discrete and Computational Geometry, J. Goodman and J. O'Rourke eds. CRC press, 2nd edition, (2004), 677--692.
• 11: T. K. Dey, Sample based geometric modeling. AMS/DIMACS volume on Computer-aided Design and Manufacturing, D. Dutta, M. Smid and R. Janardan eds., to appear.
• 12: T. K. Dey, J. Giesen and S. Goswami. Shape segmentation and matching with flow discretization. Proc. Workshop Algorithms Data Structures (WADS03) (2003), LNCS 2748, F. Dehne, J.-R. Sack and M. Smid eds., 25--36.
• 13: Tamal K. Dey , Wulue Zhao, Approximating the Medial Axis from the Voronoi Diagram with a Convergence Guarantee, Algorithmica, v.38 n.1, p.179-200, October 2003 [doi>10.1007/s00453-003-1049-y]
• 14: J. Erickson. Uniform samples of generic surfaces have nice Delaunay triangulations (2003), Manuscript.
• 15: P. M. Gruber. Aspects of approximation of convex bodies. Handbook of Convex Geometry, P. M. Gruber and J. M. Wills eds., North Holland, Amsterdam (2003), 319--345.
• 16: Robert Osada , Thomas Funkhouser , Bernard Chazelle , David Dobkin, Matching 3D Models with Shape Distributions, Proceedings of the International Conference on Shape Modeling & Applications, p.154, May 07-11, 2001
• 17: Mirela Tanase , Remco C. Veltkamp, Polygon decomposition based on the straight line skeleton, Proceedings of the nineteenth annual symposium on Computational geometry, June 08-10, 2003, San Diego, California, USA [doi>10.1145/777792.777802]