New algorithms and empirical findings on minimum weight triangulation heuristics (extended abstract)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

New algorithms and empirical findings on minimum weight triangulation heuristics (extended abstract)

Full text

Pdf (1.02 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: 238 - 247

Year of Publication: 1995

ISBN:0-89791-724-3

Authors

Matthew T. Dickerson	Middlebury College, Middlebury VT
Scott A. McElfresh	Dartmouth College, Hanover NH
Mark Montague	Middlebury College, Middlebury VT

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

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.220305 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	Gill Barequet , Micha Sharir, Piecewise-linear interpolation between polygonal slices, Proceedings of the tenth annual symposium on Computational geometry, p.93-102, June 06-08, 1994, Stony Brook, New York, United States [doi>10.1145/177424.177562]
	2	J. Bentley, D. Sanat and E. Williams Jr., "The complexity of finding fixed-radius near neighbors." Information Processing Letters 6 (1977) 209-213.
	3	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]
	4	M. Dickerson and M. Montague, "Fast new algorithms for locally minimal triangulations-and a platform for testing them." manuscript (1994).
	5	S. Drysdale, G. Rote, and O. Aichholzer, "A simple linear time greedy triangulation algorithm for uniformly distributed points." manuscript (1994).
	6	P. Gilbert, "New results in planar triangulations." MS Thesis, University of Illinois, Urbana, IL, 1979.
	7	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]
	8	Lenwood S. Heath , Sriram V. Pemmaraju, New Results for the Minimum Weight Triangulation Problem, Virginia Polytechnic Institute & State University, Blacksburg, VA, 1992
	9	G. Klincaek, "Minimal triangulations of polygonal domains." Ann. Discrete Math. 9 (1980) 121-123.
	10	Christos Levcopoulos , Andrzej Lingas, Fast algorithms for greedy triangulation, BIT, v.32 n.2, p.280-296, 1992 [doi>10.1007/BF01994882]
	11	A. Lingas, A new heuristic for minimum weight triangulation, SIAM Journal on Algebraic and Discrete Methods, v.8 n.4, p.646-658, Oct. 1987 [doi>10.1137/0608053]
	12	Andrzej Lingas, Greedy Triangulation acn be Efficiently Implemented in the Average Case (Extended Abstract), Proceedings of the 14th International Workshop on Graph-Theoretic Concepts in Computer Science, p.253-261, June 15-17, 1988
	13	E. Lloyd, "On triangulations of a set of points in the plane." Proceedings of the 18th FOCS (1977) 228-240.
	14	G. Manacher and A. Zobrist, "Neither the greedy nor the Delaunay triangulation of the planar set approximates the minimal triangulation." IP~ 9 (1979) 31-34.
	15	G. Manacher and A. Zobrist, "Probabilistic methods with heaps for fast-average-case greedy algorithms.' Advances in Computing Research vol. 1 (1983) 261-278.
	16	Joseph O'Rourke, Computational geometry in C, Cambridge University Press, New York, NY, 1994
	17	C. A. Wang, "Efficiently updating the constrained Delaunay triangulations." BiT 33 (1993) 238-252.
	18	C. A. Wang, "An optimal algorithm for greedy triangulation of a set of points" Proc. Sizth Canadian Conference of Computational Geomet~ (1994).
	19	Y F Wang , J K Aggarwal, Surface reconstruction and representation of 3-D scenes, Pattern Recognition, v.19 n.3, p.197-207, 1986 [doi>10.1016/0031-3203(86)90010-5]
	20	P. Yoeli, "Compilation of data for computerassisted relief cartography." In Display and Analysis of Spatial Data J.C.Davis and M.J. McCullagh, editors, John Wiley & Sons, NY (1975)o

CITED BY 5

	Kerry Capp , Bryant A. Julstrom, A weight-coded genetic algorithm for the minimum weight triangulation problem, Proceedings of the 1998 ACM symposium on Applied Computing, p.327-331, February 27-March 01, 1998, Atlanta, Georgia, United States
	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
	William Lenhart , Giuseppe Liotta, The drawability problem for minimum weight triangulations, Theoretical Computer Science, v.270 n.1-2, p.261-286, January
	Joseph S. B. Mitchell , Joseph O'Rourke, Computational geometry, ACM SIGACT News, v.32 n.3, p.63-72, 09/01/2001