Implementations of the LMT heuristic for minimum weight triangulation

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Implementations of the LMT heuristic for minimum weight triangulation

Full text

Pdf (1.18 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: 96 - 105

Year of Publication: 1998

ISBN:0-89791-973-4

Authors

Ronald Beirouti	Dept. of Computer Science, University of British Columbia
Jack Snoeyink	Dept. of Computer Science, University of British Columbia

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): 5, Downloads (12 Months): 26, 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/276884.276895 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	O. Aichholzer, F. Aurenhammer, S.-W. Chen, N. Katoh, hi. Taschwer, G. Rote, and Y.-F. Xu. Triangulations intersect nicely. Discrete Comput. Geom., 16:339-359, 1996.
	2	O. Aichholzer, F. Aurenhammer, G. Rote, and Y.-F. Xu. Constant-level greedy triangulations approximate the MWT well. In D.-Z. Du, X.- S. Zhang, and K. Cheng, editors, Proc. Second Internat. Syrup. Operations Research and it:# Applications, Guilin, China, December 11#-13, 1996, volume 2 of Lecture Notes in Operation.._, Research, pages 309-318, Beijing, 1996. World Publishing Corp.
	3	Efthymios Anagnostou , Derek Corneil, Polynomial-time instances of the minimum weight triangulation problem, Computational Geometry: Theory and Applications, v.3 n.5, p.247-259, Nov. 1993 [doi>10.1016/0925-7721(93)90016-Y]
	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	Johannes Blömer, Computing sums of radicals in polynomial time, Proceedings of the 32nd annual symposium on Foundations of computer science, p.670-677, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185434]
	6	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
	7	S. W. Cheng, M. J. Colin, and J. C. F. Tsang. Expected case analysis of fl-skeletons with applications to the construction of minimumweight triangulations. In Proc. 7th Canad. Conf. Comput. Geom., pages 279-284, 1995.
	8	Siu-Wing Cheng , Naoki Katoh , Manabu Sugai, A Study of the LMT-Skeleton, Proceedings of the 7th International Symposium on Algorithms and Computation, p.256-265, December 16-18, 1996
	9	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 [doi>10.1145/237218.237360]
	10	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
	11	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]
	12	M. T. Dickerson, J. M. Keil, and M. H. Montague. A large subgTaph of the minimum weight triangulation. Disc. Comp. Geom., 18(3):289-304, 1997.
	13	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 [doi>10.1145/237218.237364]
	14	R. L. S. Drysdale, S. McElfresh, and J. S. Snoeyink. Aa improved diamond property for minimum-weight triangulations. Preliminary version at CG'98, 14th Euro. Workshop on Comp. Geom., 1998.
	15	R, L. S. Drysdale, G. Rote, and O. Aichholzer. A simple linear time greedy triangulation algorithm for uniformly distributed points. Technical Report IIG-408, Institutes for Information Processing, Technische Universit#it Graz, Feb. 1995.
	16	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
	17	P. D. Gilbert. New results in planar triangulations. Report R-850, Coordinated Sci. Lab., Univ. Illinois, Urbana, IL, 1979.
	18	It. Hainz, O. Aichholzer, and F. Aurenhammer. New results on minimum weight triangulations and the LMT-skeleton (extended abstract). In CG'9713th Euro. Workshop on Comp. Geom., Wiirzburg Germany, 1997.
	19	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
	20	D, G. Kirkpatrick. A note on Delaunay and optimal triangulations. Inform. Process. Leg., 10:127-128# 1980.
	21	G. T. Klincsek. Minimal triangulations of polygonal domains. Discrete Math., 9:121-123, 1980.
	22	Y. Kyoda. A study of generating minimum weight triangulation within practical time. Master's thesis, Grad. School Info. Sci,, Univ. Tokyo, Feb. 1996. http:/ /naomi. is. e. u-tokyo, ac. jp/papers/ THES IS/HASTER/kyoda. ps. gz.
	23	Christos Levcopoulos, An &OHgr;(:.PC9 :3WzLn) lower bound for the nonoptimality of the greedy triangulation, Information Processing Letters, v.25 n.4, p.247-251, June 17, 1987 [doi>10.1016/0020-0190(87)90170-0]
	24	Christos Levcopoulos , Drago Krznaric, Quasi-greedy triangulations approximating the minimum weight triangulation, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.392-401, January 28-30, 1996, Atlanta, Georgia, United States
	25	C. Levcopoulos and D. Krznaric. A nearoptimal heuristic for the minimum weight triangulation of convex polygons, unpublished, 1997.
	26	Christos Levcopoulos , Andrzej Lingas , Jög-R. Sack, Heuristics for optimum binary search trees and minimum weight triangulation problems, Theoretical Computer Science, v.66 n.2, p.181-203, 20 Aug. 1989 [doi>10.1016/0304-3975(89)90134-5]
	27	A. Lingas. A linear-time heuristic for minimum weight triangulation of convex polygons. In Proc. 23rd Allerton Conf. Commun. Control Comput, 1985.
	28	E. L. Lloyd. On triangulations of a set of points in the plane. In Proc. 18th Annu. IEEE Sympos. Found. Gomput Sci., pages 228-240, 1977.
	29	Atsuyuki Okabe , Barry Boots , Kokichi Sugihara, Spatial tessellations: concepts and applications of Voronoi diagrams, John Wiley & Sons, Inc., New York, NY, 1992
	30	David A. Plaisted , Jiarong Hong, A heuristic triangulation algorithm, Journal of Algorithms, v.8 n.5, p.405-437, Sept. 1987 [doi>10.1016/0196-6774(87)90020-4]
	31	Otfried Schwarzkopf, The extensible drawing editor Ipe, Proceedings of the eleventh annual symposium on Computational geometry, p.410-411, June 05-07, 1995, Vancouver, British Columbia, Canada [doi>10.1145/220279.220326]
	32	Cao An Wang , Francis Y. Chin , Yin-Feng Xu, A New Subgraph of Minimum Weight Triangulations, Proceedings of the 7th International Symposium on Algorithms and Computation, p.266-274, December 16-18, 1996
	33	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

	Oswin Aichholzer, The path of a triangulation, Proceedings of the fifteenth annual symposium on Computational geometry, p.14-23, June 13-16, 1999, Miami Beach, Florida, United States
	Ferran Hurtado , Giuseppe Liotta , Henk Meijer, Optimal and suboptimal robust algorithms for proximity graphs, Computational Geometry: Theory and Applications, v.25 n.1-2, p.35-49, May 2003
	Wolfgang Mulzer , Günter Rote, Minimum-weight triangulation is NP-hard, Journal of the ACM (JACM), v.55 n.2, p.1-29, May 2008
	Minimum weight triangulation is NP-hard, Proceedings of the twenty-second annual symposium on Computational geometry, June 05-07, 2006, Sedona, Arizona, USA