Crust and anti-crust

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Crust and anti-crust: a one-step boundary and skeleton extraction algorithm

Full text

Pdf (928 KB)

Source

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

Miami Beach, Florida, United States

Pages: 189 - 196

Year of Publication: 1999

ISBN:1-58113-068-6

Author

Christopher Gold

Chair in Geomatics, Laval University, Quebec City, Quebec, Canada G1K 7P4

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): 6, Downloads (12 Months): 30, Citation Count: 12

Additional Information:

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/304893.304971 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	Helmut Alt , Otfried Schwarzkopf, The Voronoi diagram of curved objects, Proceedings of the eleventh annual symposium on Computational geometry, p.89-97, June 05-07, 1995, Vancouver, British Columbia, Canada [doi>10.1145/220279.220289]
	2	Nina Amenta , Marshall Bern, Surface reconstruction by Voronoi filtering, Proceedings of the fourteenth annual symposium on Computational geometry, p.39-48, June 07-10, 1998, Minneapolis, Minnesota, United States [doi>10.1145/276884.276889]
	3	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]
	4	Nina Amenta , Marshall Bern , Manolis Kamvysselis, A new Voronoi-based surface reconstruction algorithm, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p.415-421, July 1998 [doi>10.1145/280814.280947]
	5	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]
	6	M. Burge and G. Monagan. Using the Voronoi tessellation for grouping words and multi-pan symbols in documents. Proceedings, Vision Geometry IV, SPIE Vol. 2573, 1995, 116-123.
	7	Mark Burge , Gladys Monagan, Extracting Words and Multi-Part Symbols in Graphics Rich Documents, Proceedings of the 8th International Conference on Image Analysis and Processing, p.533-538, September 13-15, 1995
	8	Burrough, P.A. Principles of Geographical Information Systems for Land Resources Assessment. Oxford University Press, New York, 1986.
	9	Chrisman, N.R., J.R. Dougenik and D. White. Lessons for the design of polygon overlay processing from the Odyssey Whirlpool algorithm. Proceedings, 5t# International Symposium on Spatial Data Handling, 1992, 401-409.
	10	Frank, A. Overlay processing in spatial information systems. Proceedings, Auto-Carto 8, 1987, 16-31.
	11	Christopher M. Gold, The Meaning of ``Neighbour'', Proceedings of the International Conference GIS - From Space to Territory: Theories and Methods of Spatio-Temporal Reasoning on Theories and Methods of Spatio-Temporal Reasoning in Geographic Space, p.220-235, September 21-23, 1992
	12	Gold, C.M. Dynamic data structures: the interactive map. In: Molenaar, M. and de Hoop, S. (eds.), "Advanced Geographic Data Modelling - Spatial Data Modelling and Query Languages for 2D and 3D Applications", Netherlands Geodetic Commission Publications on Geodesy (New Series), 1994, 121-128.
	13	Gold, C.M. Three approaches to automated topology, and how computational geometry helps. Proceedings, Sixth International Symposium on Spatial Data Handling,.1994, 145-158.
	14	Gold, C.M. The Quad-Arc data structure. Proceedings, 8th International Symposium on Spatial Data Handling, 1998, 713- 724.
	15	Gold, C.M., J. Nantel and W. Yang. Outside-in: an alternative approach to forest map digitizing. International Journal of Geographical information Systems, 10, 1996, 29 I-310.
	16	Christopher M. Gold , Peter R. Remmele, Voronoi Methods in GIS, Algorithmic Foundations of Geographic Information Systems, this book originated from the CISM Advanced School on the Algorithmic Foundations of Geographic Information Systems, p.21-35, September 16-20, 1996
	17	D. Salesin , J Stolfi , L. Guibas, Epsilon geometry: building robust algorithms from imprecise computations, Proceedings of the fifth annual symposium on Computational geometry, p.208-217, June 05-07, 1989, Saarbruchen, West Germany [doi>10.1145/73833.73857]
	18	Leonidas Guibas , Jorge Stolfi, Primitives for the manipulation of general subdivisions and the computation of Voronoi, ACM Transactions on Graphics (TOG), v.4 n.2, p.74-123, April 1985 [doi>10.1145/282918.282923]
	19	Herring, J. A fully integrated geographical information system. Proceedings, Auto-Carto 9, 1989, 828-837.
	20	Nagy, G., M. Mukherjee and D. Embly. Making do with finite numerical precision in spatial data structures. Proceedings, 4'h International Symposium on Spatial Data Handling, 1990, 55- 65.
	21	Ogniewicz, R.L. Skeleton-space: amultiscale shape description combining region and boundary information. Proceedings of Computer Vision and Pattern Recognition, 1994, 746-751.
	22	Ogniewicz, R. and M. Ilg. Skeletons with Euclidean metric and correct topology and their application in object recognition and document analysis. Proceedings, 4th International Symposium on Spatial Data Handling, 1, 1990, 15-24.
	23	Atsuyuki Okabe , Barry Boots , Kokichi Sugihara, Spatial tessellations: concepts and applications of Voronoi diagrams, John Wiley & Sons, Inc., New York, NY, 1992
	24	Peucker, T.K. and N.R. Chrisman. Cartographic data structures. American Cartographer, 2, 1975, 55-69.
	25	David Victor Pullar, A tractable approach to map overlay, University of Maine Press, Orono, ME, 1994
	26	Glynn P. Robinson , Alan C. F. Colchester , Lewis D. Griffin , David J. Hawkes, Integrated Skeleton and Boundary Shape Representation for Medical Image Interpretation, Proceedings of the Second European Conference on Computer Vision, p.725-729, May 19-22, 1992
	27	Michael Worboys , Matt Duckham, GIS: A Computing Perspective, 2nd Edition, CRC Press, Inc., Boca Raton, FL, 2004

CITED BY 12

	N. Amenta , S. Choi , T. K. Dey , N. Leekha, A simple algorithm for homeomorphic surface reconstruction, Proceedings of the sixteenth annual symposium on Computational geometry, p.213-222, June 12-14, 2000, Clear Water Bay, Kowloon, Hong Kong
	Nina Amenta , Sunghee Choi , Ravi Krishna Kolluri, The power crust, Proceedings of the sixth ACM symposium on Solid modeling and applications, p.249-266, May 2001, Ann Arbor, Michigan, United States
	Ernst Althaus , Kurt Mehlhorn, TSP-based curve reconstruction in polynomial time, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.686-695, January 09-11, 2000, San Francisco, California, United States
	Jeff Erickson, Nice point sets can have nasty Delaunay triangulations, Proceedings of the seventeenth annual symposium on Computational geometry, p.96-105, June 2001, Medford, Massachusetts, United States
	Tamal K. Dey , Kurt Mehlhorn , Edgar A. Ramos, Curve reconstruction: connecting dots with good reason, Proceedings of the fifteenth annual symposium on Computational geometry, p.197-206, June 13-16, 1999, Miami Beach, Florida, United States
	Tamal K. Dey , Rephael Wenger, Reconstruction curves with sharp corners, Proceedings of the sixteenth annual symposium on Computational geometry, p.233-241, June 12-14, 2000, Clear Water Bay, Kowloon, Hong Kong
	Mir Abolfazl Mostafavi , Christopher Gold , Maciej Dakowicz, Delete and insert operations in Voronoi/Delaunay methods and applications, Computers & Geosciences, v.29 n.4, p.523-530, May 2003
	Michael B. Gousie , Wm. Randolph Franklin, Constructing a dem from grid-based data by computing intermediate contours, Proceedings of the 11th ACM international symposium on Advances in geographic information systems, p.71-77, November 07-08, 2003, New Orleans, Louisiana, USA
	Stefan Funke , Edgar A. Ramos, Reconstructing a collection of curves with corners and endpoints, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.344-353, January 07-09, 2001, Washington, D.C., United States
	Yong Zeng , Thanh An Nguyen , Baiquan Yan , Shuren Li, A distance-based parameter free algorithm for curve reconstruction, Computer-Aided Design, v.40 n.2, p.210-222, February, 2008
	David Thibault , Christopher M. Gold, Terrain Reconstruction from Contours by Skeleton Construction, Geoinformatica, v.4 n.4, p.349-373, December 2000
	Thanh An Nguyen , Yong Zeng, VICUR: A human-vision-based algorithm for curve reconstruction, Robotics and Computer-Integrated Manufacturing, v.24 n.6, p.824-834, December, 2008