Silver exudation

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Silver exudation

Full text

Pdf (192 KB)

Source

Journal of the ACM (JACM) archive
Volume 47 , Issue 5 (September 2000) table of contents

Pages: 883 - 904

Year of Publication: 2000

ISSN:0004-5411

Authors

Siu-Wing Cheng	Hong Kong Univ. of Science and Technology, Hong Kong, China
Tamal K. Dey	Ohio State Univ., Columbus
Herbert Edelsbrunner	Duke Univ., Durham, NC
Michael A. Facello	Raindrop Geomagic, Research Triangle Park, NC
Shang-Hua Teng	Univ. of Illinois at Urbana-Champaign, Urbanna

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 8, Downloads (12 Months): 65, Citation Count: 22

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/355483.355487 What is a DOI?

ABSTRACT

A silver is a tetrahedon whose four vertices lie close to a plane and whose orthogonal projection to that plane is a convex quadrilateral with no short edge. Silvers are notoriously common in 3-dimensional Delaunay triangulations even for well-spaced point sets. We show that, if the Delaunay triangulation has the ratio property introduced in Miller et al. [1995], then there is an assignment of weights so the weighted Delaunay traingulation contains no silvers. We also give an algorithm to compute such a weight assignment.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Marshall Bern , Paul Chew , David Eppstein , Jim Ruppert, Dihedral bounds for mesh generation in high dimensions, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.189-196, January 22-24, 1995, San Francisco, California, United States
	2	Marshall Bern , David Eppstein , John Gilbert, Provably good mesh generation, Journal of Computer and System Sciences, v.48 n.3, p.384-409, June 1994 [doi>10.1016/S0022-0000(05)80059-5]
	3	BILLERA, L. J., FILLIMAN, P., AND STURMFELS, B. 1990. Construction and complexity of secondary polytopes. Adv. Math. 83, 155-179.
	4	CAVENDISH, J. C., FIELD, D. A., AND FREY, W. H. 1985. An approach to automatic three-dimensional finite element mesh generation. Internat. J. Numer. Methods Engrg. 21, 329-347.
	5	L. Paul Chew, Guaranteed-quality Delaunay meshing in 3D (short version), Proceedings of the thirteenth annual symposium on Computational geometry, p.391-393, June 04-06, 1997, Nice, France [doi>10.1145/262839.263018]
	6	Philippe G. Ciarlet, Finite Element Method for Elliptic Problems, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2002
	7	DELAUNAY, B. 1934. Sur la sphe`re vide. Izv. Akad. Nauk SSSR, Otdelenie Matematicheskii i Estestvennyka Nauk 7, 793-800.
	8	DEY, T. K., BAJAJ, C., AND SUGIHARA, K. 1992. On good triangulations in three dimensions. Internat. J. Comput. Geom. Appl. 2, 75-95.
	9	EDELSBRUNNER, H., AND SHAH, N. R. 1996. Incremental topological flipping works for regular triangulations. Algorithmica 15, 223-241.
	10	EDELSBRUNNER, H., AND TAN, T. S. 1993. An upper bound for conforming Delaunay triangulations. Disc. Comput. Geom. 10, 197-213.
	11	Alan M. Frieze , Gary L. Miller , Shang-Hua Teng, Separator based parallel divide and conquer in computational geometry, Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.420-429, June 29-July 01, 1992, San Diego, California, United States [doi>10.1145/140901.141934]
	12	GELFAND, I. M., KAPRANOV, M. M., AND ZELEVINSKY, A. V. 1994. Discriminants, Resultants and Multidimensional Determinants. Birkha~user, Boston, Mass.
	13	JOE, B. 1991. Delaunay versus min-max solid angle triangulations for three-dimensional mesh generation. Int. J. Numer. Methods Eng. 31, 987-997.
	14	LIU, A., AND JOE, B. 1994. Relationship between tetrahedron shape measures. BIT 34, 268-287.
	15	Gary L. Miller , Dafna Talmor , Shang-Hua Teng , Noel Walkington, A Delaunay based numerical method for three dimensions: generation, formulation, and partition, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.683-692, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225286]
	16	Scott A. Mitchell , Stephen A. Vavasis, Quality mesh generation in three dimensions, Proceedings of the eighth annual symposium on Computational geometry, p.212-221, June 10-12, 1992, Berlin, Germany [doi>10.1145/142675.142720]
	17	RAJAN, V. T. 1994. Optimality of the Delaunay triangulation in Rd. Discrete Comput. Geom. 12, 189-202.
	18	Jim Ruppert, A Delaunay refinement algorithm for quality 2-dimensional mesh generation, Journal of Algorithms, v.18 n.3, p.548-585, May 1995
	19	Jonathan Richard Shewchuk, Tetrahedral mesh generation by Delaunay refinement, Proceedings of the fourteenth annual symposium on Computational geometry, p.86-95, June 07-10, 1998, Minneapolis, Minnesota, United States [doi>10.1145/276884.276894]
	20	STRANG, G., AND FIX, G. J. 1973. An Analysis of the Finite Element Method. Prentice-Hall, Englewood Cliffs, N.J.
	21	TALMOR, D. 1997. Well-spaced points for numerical methods. Report CMU-CS-97-164, Dept. Comput. Sci., Carnegie-Mellon Univ., Pittsburgh, Pa.
	22	VORONOI, G. 1907/1908. Nouvelles applications des parame`tres continus `a la the~orie des formes quadratiques. J. Reine Angew. Math. 133, 1907, 97-178, and 134, 1908, 198-287.

CITED BY 22

	Siu-Wing Cheng , Sheung-Hung Poon, Graded conforming Delaunay tetrahedralization with bounded radius-edge ratio, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
	Yongjie Zhang , Chandrajit Bajaj , Bong-Soo Sohn, Adaptive and quality 3D meshing from imaging data, Proceedings of the eighth ACM symposium on Solid modeling and applications, June 16-20, 2003, Seattle, Washington, USA
	Siu-Wing Cheng , Tamal K. Dey, Quality meshing with weighted Delaunay refinement, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.137-146, January 06-08, 2002, San Francisco, California
	Herbert Edelsbrunner , Xiang-Yang Li , Gary Miller , Andreas Stathopoulos , Dafna Talmor , Shang-Hua Teng , Alper Üngör , Noel Walkington, Smoothing and cleaning up slivers, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.273-277, May 21-23, 2000, Portland, Oregon, United States
	Jonathan Richard Shewchuk, Updating and constructing constrained delaunay and constrained regular triangulations by flips, Proceedings of the nineteenth annual symposium on Computational geometry, June 08-10, 2003, San Diego, California, USA
	Siu-Wing Cheng , Tamal K. Dey , Edgar A. Ramos , Tathagata Ray, Quality meshing for polyhedra with small angles, Proceedings of the twentieth annual symposium on Computational geometry, June 08-11, 2004, Brooklyn, New York, USA
	Richard Shewchuk, Star splaying: an algorithm for repairing delaunay triangulations and convex hulls, Proceedings of the twenty-first annual symposium on Computational geometry, June 06-08, 2005, Pisa, Italy
	Siu-Wing Cheng , Tamal K. Dey , Edgar A. Ramos, Manifold reconstruction from point samples, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	Siu-Wing Cheng, On the sizes of Delaunay meshes, Computational Geometry: Theory and Applications, v.33 n.3, p.130-138, February 2006
	François Labelle, Sliver removal by lattice refinement, Proceedings of the twenty-second annual symposium on Computational geometry, June 05-07, 2006, Sedona, Arizona, USA
	Yongjie Zhang , Guoliang Xu , Chandrajit Bajaj, Quality meshing of implicit solvation models of biomolecular structures, Computer Aided Geometric Design, v.23 n.6, p.510-530, August 2006
	Sergey Bereg , Minghui Jiang , Binhai Zhu, Contour interpolation with bounded dihedral angles, Proceedings of the ninth ACM symposium on Solid modeling and applications, June 09-11, 2004, Genoa, Italy
	Kokichi Sugihara, Sliver-free perturbation for the Delaunay tetrahedrization, Computer-Aided Design, v.39 n.2, p.87-94, February, 2007
	Benoît Hudson , Gary L. Miller , Todd Phillips , Don Sheehy, Size complexity of volume meshes vs. surface meshes, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.1041-1047, January 04-06, 2009, New York, New York
	Dominique Attali , Herbert Edelsbrunner , Yuriy Mileyko, Weak witnesses for Delaunay triangulations of submanifolds, Proceedings of the 2007 ACM symposium on Solid and physical modeling, June 04-06, 2007, Beijing, China
	Jean-Daniel Boissonnat , Leonidas J. Guibas , Steve Y. Oudot, Manifold reconstruction in arbitrary dimensions using witness complexes, Proceedings of the twenty-third annual symposium on Computational geometry, June 06-08, 2007, Gyeongju, South Korea
	Siu-Wing Cheng , Man-Kwun Chiu, Dimension detection via slivers, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.1001-1010, January 04-06, 2009, New York, New York
	C. S. Chong , A. Senthil Kumar , H. P. Lee, Automatic mesh-healing technique for model repair and finite element model generation, Finite Elements in Analysis and Design, v.43 n.15, p.1109-1119, November, 2007
	Frédéric Chazal , Steve Yann Oudot, Towards persistence-based reconstruction in euclidean spaces, Proceedings of the twenty-fourth annual symposium on Computational geometry, June 09-11, 2008, College Park, MD, USA
	François Labelle , Jonathan Richard Shewchuk, Isosurface stuffing: fast tetrahedral meshes with good dihedral angles, ACM Transactions on Graphics (TOG), v.26 n.3, July 2007
	Laurent Rineau , Mariette Yvinec, A generic software design for Delaunay refinement meshing, Computational Geometry: Theory and Applications, v.38 n.1-2, p.100-110, September, 2007
	Jane Tournois , Camille Wormser , Pierre Alliez , Mathieu Desbrun, Interleaving Delaunay refinement and optimization for practical isotropic tetrahedron mesh generation, ACM Transactions on Graphics (TOG), v.28 n.3, August 2009