Incremental topological flipping works for regular triangulations

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Incremental topological flipping works for regular triangulations

Full text

Pdf (1.04 MB)

Source

Annual Symposium on Computational Geometry archive
Proceedings of the eighth annual symposium on Computational geometry table of contents

Berlin, Germany

Pages: 43 - 52

Year of Publication: 1992

ISBN:0-89791-517-8

Authors

H. Edelsbrunner
N. R. Shah

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 10, Downloads (12 Months): 89, Citation Count: 18

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	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/142675.142688 What is a DOI?

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	F Aurenhammer, Power diagrams: properties, algorithms and applications, SIAM Journal on Computing, v.16 n.1, p.78-96, Feb. 1987 [doi>10.1137/0216006]
	2	Franz Aurenhammer, Voronoi diagrams—a survey of a fundamental geometric data structure, ACM Computing Surveys (CSUR), v.23 n.3, p.345-405, Sept. 1991 [doi>10.1145/116873.116880]
	3	H. Bruggesser and P. Mani. Shellable decompositions of cells and spheres. Math. Scand. 29 (1971), 197-205.
	4	K. L. Clarkson , P. W. Shor, Applications of random sampling in computational geometry, II, Discrete & Computational Geometry, v.4 n.5, p.387-421, 1989
	5	B. N. Delaunay. Sur la sphere vide. Izv. Akad. Nauk SSSR, Otdelenie Matematicheskii i Estestvennyka Nauk 7 (1934), 793-800.
	6	Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
	7	H. Edelsbrunner. An acyclicity theorem for cell complexes in d dimensions. Combinatorica 10 (1990), 251- 260.
	8	H. Edelsbrunner, D. G. Kirkpatrick and R. Seidel. On the shape of a set of points in the plane. IEEE Trans. inform. Theory IT-29 (1983), 551-559.
	9	Herbert Edelsbrunner , Ernst Peter Mücke, Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms, ACM Transactions on Graphics (TOG), v.9 n.1, p.66-104, Jan. 1990 [doi>10.1145/77635.77639]
	10	H. Edelsbrunner and E. P. Miicke. Three-dimensional alpha shapes. Manuscript, Dept. Comput. Sci., Univ. Illinois at Urbana-Champaign, 1992.
	11	Leonidas J. Guibas , Donald E. Knuth , Micha Sharir, Randomized incremental construction of Delaunay and Voronoi diagrams, Proceedings of the seventeenth international colloquium on Automata, languages and programming, p.414-431, July 1990, Warwick University, England
	12	Barry Joe, Three-dimensional triangulations from local transformations, SIAM Journal on Scientific and Statistical Computing, v.10 n.4, p.718-741, July 1989 [doi>10.1137/0910044]
	13	Barry Joe, Construction of three-dimensional Delaunay triangulations using local transformations, Computer Aided Geometric Design, v.8 n.2, p.123-142, May 1991 [doi>10.1016/0167-8396(91)90038-D ]
	14	C. L. Lawson. Generation of a triangular gridwith applications to contour plotting. Memo 299, Jet Propulsion Laboratory, Pasadena, California, 1972.
	15	C. L. Lawson. Software for C1 surface interpolation. Mathematical Software III, edited by J. Rice, Academic Press, New York, 1977, 161-194.
	16	Charles L. Lawson, Properties of n-dimensional triangulations, Computer Aided Geometric Design, v.3 n.4, p.231-246, 1987 [doi>10.1016/0167-8396(86)90001-4]
	17	C. Lee. Regular triangulations of convex polytopes. Applied Geometry andDiscrete Mathematics: The Victor Klee Festschrift, edited by P. Gritzmann and B. Sturmfels, Amer. Math. Soc., Providence, RI, 1991, 443-456.
	18	Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
	19	J. Radon. Mengen konvexer KSrper, die einen gemeinsamen Punkt enthalten. Math. Ann. 83 (1921), 113- 115.
	20	V. T. Rajan, Optimality of the Delaunay triangulation in R^d, Proceedings of the seventh annual symposium on Computational geometry, p.357-363, June 10-12, 1991, North Conway, New Hampshire, United States [doi>10.1145/109648.109688]
	21	E. SchSnhardt./)ber die Zerlcgung yon Dreieckspolyedern in Tetraeder. Math. Ann. 98 (:1928), 309-312.
	22	R Seidel, Constructing higher-dimensional convex hulls at logarithmic cost per face, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.404-413, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12172]
	23	G. F. Voronoi. Nouvelles applications des param{tres continus h la thdorie des formes quadratiques. J. Reine Angew. Math. 133 (t907), 97-178.

CITED BY 18

	Suzana Djurcilov , Alex Pang, Visualizing Sparse Gridded Data Sets, IEEE Computer Graphics and Applications, v.20 n.5, p.52-57, September 2000
	Marek Teichmann , Michael Capps, Surface reconstruction with anisotropic density-scaled alpha shapes, Proceedings of the conference on Visualization '98, p.67-72, October 18-23, 1998, Research Triangle Park, North Carolina, United States
	Ángel Plaza , José P. Suárez , Graham F. Carey, A geometric diagram and hybrid scheme for triangle subdivision, Computer Aided Geometric Design, v.24 n.1, p.19-27, January, 2007
	Jing Hua , Ying He , Hong Qin, Multiresolution heterogeneous solid modeling and visualization using trivariate simplex splines, Proceedings of the ninth ACM symposium on Solid modeling and applications, June 09-11, 2004, Genoa, Italy
	Tomonari Masada , Hiroshi Imai , Keiko Imai, Enumeration of regular triangulations, Proceedings of the twelfth annual symposium on Computational geometry, p.224-233, May 24-26, 1996, Philadelphia, Pennsylvania, United States
	Ali Akgunduz , Dan Zetu , Pat Banerjee, Viewpoint-based shape recovery from multiple views, Artificial Intelligence for Engineering Design, Analysis and Manufacturing, v.14 n.5, p.359-372, November 2000
	Marc Vigo , Núria Pla , Josep Cotrina, Regular triangulations of dynamic sets of points, Computer Aided Geometric Design, v.19 n.2, p.127-149, February 2002
	Fausto Bernardini , Glauco Cenciotti , Alberto Paoluzzi, Transfinite interpolation of surfaces with integral constraints using a design language, From geometric modeling to shape modeling, Kluwer Academic Publishers, Norwell, MA, 2002
	Y. A. Teng , F. Sullivan , I. Beichl , E. Puppo, A data-parallel algorithm for three-dimensional Delaunay triangulation and its implementation, Proceedings of the 1993 ACM/IEEE conference on Supercomputing, p.112-121, December 1993, Portland, Oregon, United States
	Peter L. Williams, Visibility-ordering meshed polyhedra, ACM Transactions on Graphics (TOG), v.11 n.2, p.103-126, April 1992
	David Eppstein, Average case analysis of dynamic geometric optimization, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.77-86, January 23-25, 1994, Arlington, Virginia, United States
	Herbert Edelsbrunner , Ernst P. Mücke, Three-dimensional alpha shapes, Proceedings of the 1992 workshop on Volume visualization, p.75-82, October 19-20, 1992, Boston, Massachusetts, United States
	Nancy M. Amato , Edgar A. Ramos, On computing Voronoi diagrams by divide-prune-and-conquer, Proceedings of the twelfth annual symposium on Computational geometry, p.166-175, May 24-26, 1996, Philadelphia, Pennsylvania, United States
	Herbert Edelsbrunner , Ernst P. Mücke, Three-dimensional alpha shapes, ACM Transactions on Graphics (TOG), v.13 n.1, p.43-72, Jan. 1994
	Leonidas Guibas , Daniel Russel, An empirical comparison of techniques for updating Delaunay triangulations, Proceedings of the twentieth annual symposium on Computational geometry, June 08-11, 2004, Brooklyn, New York, USA
	Herbert Edelsbrunner, The union of balls and its dual shape, Proceedings of the ninth annual symposium on Computational geometry, p.218-231, May 18-21, 1993, San Diego, California, United States
	C. Bradford Barber , David P. Dobkin , Hannu Huhdanpaa, The quickhull algorithm for convex hulls, ACM Transactions on Mathematical Software (TOMS), v.22 n.4, p.469-483, Dec. 1996
	Chandrajit L. Bajaj , Fausto Bernardini , Guoliang Xu, Automatic reconstruction of surfaces and scalar fields from 3D scans, Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, p.109-118, September 1995