The path of a triangulation

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

The path of a triangulation

Full text

Pdf (911 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: 14 - 23

Year of Publication: 1999

ISBN:1-58113-068-6

Author

Oswin Aichholzer

Institute for Theoretical Computer Science, Graz University of Technology, Klosterwiesgasse 32/1, 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): 6, Downloads (12 Months): 40, Citation Count: 6

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.304896 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, Y.-F. Xu, Optimal Triangulations, Encyclopedia of Optimization, Kluwer Acad. Publ., to appear.
	2	David Avis , Komei Fukuda, Reverse search for enumeration, Discrete Applied Mathematics, v.65 n.1-3, p.21-46, March 7, 1996 [doi>10.1016/0166-218X(95)00026-N]
	3	Ronald Beirouti , Jack Snoeyink, Implementations of the LMT heuristic for minimum weight triangulation, Proceedings of the fourteenth annual symposium on Computational geometry, p.96-105, June 07-10, 1998, Minneapolis, Minnesota, United States [doi>10.1145/276884.276895]
	4	Patrice Belleville , Mark Keil , Michael McAllister , Jack Snoeyink, On computing edges that are in all minimum-weight triangulations, Proceedings of the twelfth annual symposium on Computational geometry, p.507-508, May 24-26, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237218.237425]
	5	Prosenjit Bose , Luc Devroye , William S. Evans, Diamonds Are Not a Minimum Weight Triangulation's Best Friend, Proceedings of the 8th Canadian Conference on Computational Geometry, p.68-73, August 12-15, 1996
	6	S.-W. Cheng, M.J. Golin, J.C.F. Tsang, Expected-case analysis of f3-skeletons with applications to the construction of minimumweight triangulations, Proc. 7th Canadian Conf. on Computational Geometry, 1995, 279-283
	7	G. Das , D. Joseph, Which triangulations approximate the complete graph?, Proceedings of the international symposium on Optimal algorithms, p.168-192, November 1989, Varna, Bulgaria
	8	M. Denny, C. Sohler, Encoding a triangulation as a permutation of its point set, Proc. 9th Canadian Conf. on Computational Geometry, 1997, 39-43
	9	M.T. Dickerson, J.M. Keil, M.H. Montague, A large subgraph of the minimum weight triangulation, Discrete & Computational Geometry 18, 1997, 289-304.
	10	Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
	11	B. Erkinger, Struktureigenschaften yon Triangulierungen, Master Thesis, TU-Graz, 1998.
	12	Philippe Flajolet , Marc Noy, Analytic combinatorics of non-crossing configurations, Discrete Mathematics, v.204 n.1-3, p.203-229, June 6, 1999 [doi>10.1016/S0012-365X(98)00372-0]
	13	A. Garcia,. M. Noy, J. Tejel, Lower Bounds for the number of crossing-free subgraphs of K,#, Proc. 7th Canadian Conf. on Computational Geometry, 1995, 97-102.
	14	P.D. Gilbert, New results in planar triangulation, M.S. thesis, Coordinated Science Laboratory, University of Illinois, Urbana, 1979.
	15	F. Hurtado, M. Noy, Counting triangulations of almost-convex polygons, Ars Combinatoria 45, 1997, 169-179.
	16	F. Hurtado , M. Noy, Ears of triangulations and Catalan numbers, Discrete Mathematics, v.149 n.1-3, p.319-324, Feb. 22, 1996 [doi>10.1016/0012-365X(94)00331-C]
	17	F. Hurtado , M. Noy, Triangulations, visibility graph and reflex vertices of a simple polygon, Computational Geometry: Theory and Applications, v.6 n.6, p.355-369, Nov. 1996 [doi>10.1016/0925-7721(95)00027-5]
	18	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
	19	D.G. Kirkpatrick, J.D. Radke, A framework .for computational morphology, G.T.Toussaint (ed.), Computational Geometry, Elsevier, Amsterdam, 1985, 217-248.
	20	G.T. Klincsek, Minimal triangulations of polygonal domains, Annals of Discrete Mathematics 9, 1980, 127-128.

CITED BY 6

	Oswin Aichholzer , Franz Aurenhammer , Hannes Krasser, Enumerating order types for small sets with applications, Proceedings of the seventeenth annual symposium on Computational geometry, p.11-18, June 2001, Medford, Massachusetts, United States
	Sergei Bespamyatnikh, An efficient algorithm for enumeration of triangulations, Computational Geometry: Theory and Applications, v.23 n.3, p.271-279, November 2002
	Oswin Aichholzer , Ferran Hurtado , Marc Noy, A lower bound on the number of triangulations of planar point sets, Computational Geometry: Theory and Applications, v.29 n.2, p.135-145, October 2004
	Michael Hoffmann , Yoshio Okamoto, The minimum weight triangulation problem with few inner points, Computational Geometry: Theory and Applications, v.34 n.3, p.149-158, July 2006
	Micha Sharir , Emo Welzl, Random triangulations of planar point sets, Proceedings of the twenty-second annual symposium on Computational geometry, June 05-07, 2006, Sedona, Arizona, USA
	Oswin Aichholzer , Hannes Krasser, Abstract order type extension and new results on the rectilinear crossing number, Computational Geometry: Theory and Applications, v.36 n.1, p.2-15, January 2007