Triangulations intersect nicely

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Triangulations intersect nicely

Full text

Pdf (1.06 MB)

Source

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

Vancouver, British Columbia, Canada

Pages: 220 - 229

Year of Publication: 1995

ISBN:0-89791-724-3

Authors

Oswin Aichholzer	Institute for Theoretical Computer Science, Graz University of Technology, Klosterwiesgasse 32/2, A-8010 Graz, Austria
Günter Rote	Institut für Mathematik, Technische Universität Graz, Steyrergasse 30, A-8010 Graz, Austria

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): 2, Downloads (12 Months): 16, Citation Count: 4

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/220279.220303 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.

	B	B. Bollobls, Graph Theory. An Introductory Course, Springer Verlag, 1979.
	CX	Siu-Wing Cheng , Yin-Feng Xu, Constrained Independence System and Triangulations of Planar Point Sets, Proceedings of the First Annual International Conference on Computing and Combinatorics, p.41-50, August 24-26, 1995
	DFPN	L. de Floriani, B. Falcidieno, C. Pienovi, and G. Nagy, On sorting triangles in a Delaunay tessellation, Report, Ist. Mat. Appl., Consiglio Nazionale delle Ricerche, Genova, Italy, 1988.
	DDMW	Matthew T. Dickerson , Robert L. Scot Drysdale , Scott A. McElfresh , Emo Welzl, Fast greedy triangulation algorithms, Proceedings of the tenth annual symposium on Computational geometry, p.211-220, June 06-08, 1994, Stony Brook, New York, United States [doi>10.1145/177424.177649]
	DDS	M. Dickerson, R. L. Drysdale, and J.-R. Sack, Simple algorithms for enumerating interpoint distances and finding k nearest neighbors, Int. J. Computational Geometry & Appl. 3 (1992), 221-239.
	DRA	R. L. Drysdale, G. Rote, O. Aichholzer, A simple linear time greedy triangulation algorithm for uniformly distributed points, Manuscript, 1994.
	E	H. Edelsbrunner, An acyclicity theorem for cell complexes in d dimensions, Combinatorica 10 (1990), 252-260.
	G J	Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
	G	S. A. Goldman, A space efficient greedy triangulation algorithm, Information Processing Letters, v.31 n.4, p.191-196, May 22, 1989 [doi>10.1016/0020-0190(89)90122-1]
	HK	J. E. Hopcroft and R. Karp, An n{ algorithm for maximum matchings in bipartite graphs, SIAM J. Comput. 2 (1973), 225-231.
	K	J. Mark Keil, Computing a subgraph of the minimum weight triangulation, Computational Geometry: Theory and Applications, v.4 n.1, p.13-26, May 1994
	LL	Christos Levcopoulos , Andrzej Lingas, Fast algorithms for greedy triangulation, BIT, v.32 n.2, p.280-296, 1992 [doi>10.1007/BF01994882]
	Lam	Timothy David Lambert , Dereck Meek, Empty-shape triangulation algorithms, 1994
	La	E. Lawler, Combinatorial Optimization: Networks and Matroids, Holt, Rinehart, and Winston, New York, 1976.
	Law	C. L. Lawson, Software for C1 surface interpolation, In' Mathematical Software III, J. Rice (ed.), Academic Press, New York, 1977.
	T	Robert Endre Tarjan, Data structures and network algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983
	W	C. A. Wang, Etticiently updating constrained Delaunay triangulations, BIT 33 (1993), 238- 252.
	X	Y. Xu, Minimum weight triangulation problem of a planar point set, Ph.D. thesis, Institute of Applied Mathematics, Academia Sinica, Beijing, 1992.
	YXY	Bo-Ting Yang , Yin-Feng Xu , Zhao-yong You, A Chain Decomposition Algorithm for the Proof of a Property on Minimum Weight Triangulations, Proceedings of the 5th International Symposium on Algorithms and Computation, p.423-427, August 25-27, 1994

CITED BY 4

	Matthew T. Dickerson , Mark H. Montague, A (usually?) connected subgraph of the minimum weight triangulation, Proceedings of the twelfth annual symposium on Computational geometry, p.204-213, May 24-26, 1996, Philadelphia, Pennsylvania, United States
	Siu-Wing Cheng , Yin-Feng Xu, Approaching the largest &bgr;-skeleton within a minimum weight triangulation, Proceedings of the twelfth annual symposium on Computational geometry, p.196-203, May 24-26, 1996, Philadelphia, Pennsylvania, United States
	Joseph O'Rourke, Computational geometry column 27, ACM SIGACT News, v.26 n.4, p.19-21, Dec. 1995
	Cao An Wang , Yin-Feng Xu, Computing a Minimum Weight Triangulation of a Sparse Point Set, Journal of Global Optimization, v.15 n.1, p.73-83, July 1999