Construction of contour trees in 3D in O(n log n) steps

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Construction of contour trees in 3D in O(n log n) steps

Full text

Pdf (1.16 MB)

Source

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

Minneapolis, Minnesota, United States

Pages: 68 - 75

Year of Publication: 1998

ISBN:0-89791-973-4

Authors

Sergey P. Tarasov	Computing Center of RAS, Vavilova 40, 117967 Moscow GSP-1, Russia
Michael N. Vyalyi	Computing Center of RAS, Vavilova 40, 117967 Moscow GSP-1, Russia

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): 3, Downloads (12 Months): 32, Citation Count: 17

Additional Information:

references cited by index terms collaborative colleagues peer to peer

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/276884.276892 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	Marc van Kreveld , René van Oostrum , Chandrajit Bajaj , Valerio Pascucci , Dan Schikore, Contour trees and small seed sets for isosurface traversal, Proceedings of the thirteenth annual symposium on Computational geometry, p.212-220, June 04-06, 1997, Nice, France [doi>10.1145/262839.269238]
	2	Mark de Berg , Marc J. van Kreveld, Trekking in the Alps Without Freezing or Getting Tired, Proceedings of the First Annual European Symposium on Algorithms, p.121-132, September 30-October 02, 1993
	3	G. Reeb. Sur les point singuliers d'une forme de pfaff completement integrable ou d'une function numerique. Comptes Rendus Acad. Sciences Paris, 222, 1946, 847- 849.
	4	A. Hatcher and W. Thurston. A presentation for the mapping class group of a closed orientable surface, em Topology, 19, 1980, 221 - 237.
	5	Yoshihisa Shinagawa , Tosiyasu L. Kunii , Yannick L. Kergosien, Surface Coding Based on Morse Theory, IEEE Computer Graphics and Applications, v.11 n.5, p.66-78, September 1991 [doi>10.1109/38.90568]
	6	Sergey P. Tarasov , Michael N. Vyalyi, Some PL functions on surfaces are not height functions, Proceedings of the thirteenth annual symposium on Computational geometry, p.113-118, June 04-06, 1997, Nice, France [doi>10.1145/262839.262912]
	7	O. R. Musin. On some problems of computational geometry and topology. Lect. Notes in Math., 1520, 1992, 57 - 80.
	8	C. Rourke and B. Sanderson. Introduction to Piece#hse-Linear Topology. Spdnger-Verlag, NY, 1972.
	9	T. F. Banchoff. Critical points and curvature for embedded polyhedra, Z Diff. Geom. 1, 1967, 245 - 256.
	10	B. Dubrovin, S. Novikov, and A. Fomenko. Modem Geometry. Moscow, 1979.
	11	L Milnor. Morse Theory. Princeton, NJ, Princeton University Press, 1963.

CITED BY 17

	Hamish Carr , Jack Snoeyink , Ulrike Axen, Computing contour trees in all dimensions, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.918-926, January 09-11, 2000, San Francisco, California, United States
	Ulrike Axen, Computing Morse functions on triangulated manifolds, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.850-851, January 17-19, 1999, Baltimore, Maryland, United States
	V. Pascucci , K. Cole-McLaughlin, Efficient computation of the topology of level sets, Proceedings of the conference on Visualization '02, October 27-November 01, 2002, Boston, Massachusetts
	Herbert Edelsbrunner , John Harer , Vijay Natarajan , Valerio Pascucci, Morse-smale complexes for piecewise linear 3-manifolds, Proceedings of the nineteenth annual symposium on Computational geometry, June 08-10, 2003, San Diego, California, USA
	Guangfeng Ji , Han-Wei Shen , Rephael Wenger, Volume Tracking Using Higher Dimensional Isosurfacing, Proceedings of the 14th IEEE Visualization 2003 (VIS'03), p.28, October 22-24, 2003
	Hamish Carr , Jack Snoeyink , Michiel van de Panne, Simplifying Flexible Isosurfaces Using Local Geometric Measures, Proceedings of the conference on Visualization '04, p.497-504, October 10-15, 2004
	Hamish Carr , Jack Snoeyink , Ulrike Axen, Computing contour trees in all dimensions, Computational Geometry: Theory and Applications, v.24 n.2, p.75-94, February 2003
	Éric Colin De Verdière , Francis Lazarus, Optimal pants decompositions and shortest homotopic cycles on an orientable surface, Journal of the ACM (JACM), v.54 n.4, p.18-es, July 2007
	Pankaj K. Agarwal , Lars Arge , Ke Yi, I/O-efficient batched union-find and its applications to terrain analysis, Proceedings of the twenty-second annual symposium on Computational geometry, June 05-07, 2006, Sedona, Arizona, USA
	Shigeo Takahashi , Yuriko Takeshima , Issei Fujishiro, Topological volume skeletonization and its application to transfer function design, Graphical Models, v.66 n.1, p.24-49, January 2004
	Jim Cox , D. B. Karron , Nazma Ferdous, Topological Zone Organization of Scalar Volume Data, Journal of Mathematical Imaging and Vision, v.18 n.2, p.95-117, March 2003
	S. Biasotti , D. Giorgi , M. Spagnuolo , B. Falcidieno, Reeb graphs for shape analysis and applications, Theoretical Computer Science, v.392 n.1-3, p.5-22, February, 2008
	Masaki Hilaga , Yoshihisa Shinagawa , Taku Kohmura , Tosiyasu L. Kunii, Topology matching for fully automatic similarity estimation of 3D shapes, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.203-212, August 2001
	Andrzej Szymczak , James Vanderhyde, Extraction of Topologically Simple Isosurfaces from Volume Datasets, Proceedings of the 14th IEEE Visualization 2003 (VIS'03), p.10, October 22-24, 2003
	Yi-Jen Chiang , Tobias Lenz , Xiang Lu , Günter Rote, Simple and optimal output-sensitive construction of contour trees using monotone paths, Computational Geometry: Theory and Applications, v.30 n.2, p.165-195, February 2005
	Lutz Kettner , Jarek Rossignac , Jack Snoeyink, The safari interface for visualizing time-dependent volume data using iso-surfaces and contour spectra, Computational Geometry: Theory and Applications, v.25 n.1-2, p.97-116, May 2003
	S. Biasotti , L. De Floriani , B. Falcidieno , P. Frosini , D. Giorgi , C. Landi , L. Papaleo , M. Spagnuolo, Describing shapes by geometrical-topological properties of real functions, ACM Computing Surveys (CSUR), v.40 n.4, p.1-87, October 2008