Approaching the largest &bgr;-skeleton within a minimum weight triangulation

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Approaching the largest &bgr;-skeleton within a minimum weight triangulation

Full text

Pdf (653 KB)

Source

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

Philadelphia, Pennsylvania, United States

Pages: 196 - 203

Year of Publication: 1996

ISBN:0-89791-804-5

Authors

Siu-Wing Cheng	Department of Computer Science, HKUST, Clear Water Bay, Hong Kong
Yin-Feng Xu	School of Management, Xi'an Jiaotong University, Xi'an, Shaanxi, PRC

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

Additional Information:

references cited by index terms collaborative colleagues peer to peer

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/237218.237360 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	Oswin Aichholzer , Günter Rote, Triangulations intersect nicely, Proceedings of the eleventh annual symposium on Computational geometry, p.220-229, June 05-07, 1995, Vancouver, British Columbia, Canada [doi>10.1145/220279.220303]
	2	M. BERN, H. EDELSBRUNNER, D. EPPSTEIN, $. MITCHELL, AND T. TAN, Edge insertion for optimal triangulations, Discrete & Computational Geometry, 10 (1993), pp. 47-65.
	3	Matthew T. Dickerson , Scott A. McElfresh , Mark Montague, New algorithms and empirical findings on minimum weight triangulation heuristics (extended abstract), Proceedings of the eleventh annual symposium on Computational geometry, p.238-247, June 05-07, 1995, Vancouver, British Columbia, Canada [doi>10.1145/220279.220305]
	4	R. DUPPE AND H. GOTTSCHALK, A uiomaiische interpolation yon isolinen bet willkurlichen stuizpunkien, Allgemeine Vermeasungsberichten, 77 (1970), pp. 423-426.
	5	Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
	6	P. GILBERT, New results on planar triangulations, master's thesis, University of Illinois, 1979. Report No. UILUENG 78 2243.
	7	L. GRAY, L. MARTHA, Am) A. INORAFFEA, Hypersingular intergrals in boundary element fracture analysis, Internat. J. Number. Methods Engrg., 20 (1990), pp. 1135-1158.
	8	L. HEATH AND S. PEMMARAJU, New results for the minimum weight triangulation problem, Algorithmica, 12 (1994), pp. 533-552.
	9	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
	10	D. KIRKPATRICK AND J. RADKE, A framework jbr computational morphology, in Computational Geometry, G. Toussaint, ed., Elsevier, Amsterdam, 1985, pp. 217-248.
	11	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
	12	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]
	13	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]
	14	Bo-Ting Yang, A Better Subgraph of the Minimum Weight Triangulation, Proceedings of the First Annual International Conference on Computing and Combinatorics, p.452-455, August 24-26, 1995
	15	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
	16	P. YOELI, Compilation of data for computerassisted relief cartography, in Display and Analysis of Spatial Data, j. Davis and M. McCullagh, eds., Wiley, New York, 1975.

CITED BY 7

	David Eppstein, Beta-skeletons have unbounded dilation, Computational Geometry: Theory and Applications, v.23 n.1, p.43-52, July 2002
	William Lenhart , Giuseppe Liotta, The drawability problem for minimum weight triangulations, Theoretical Computer Science, v.270 n.1-2, p.261-286, January
	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
	Minimum weight triangulation is NP-hard, Proceedings of the twenty-second annual symposium on Computational geometry, June 05-07, 2006, Sedona, Arizona, USA
	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
	Jan Remy , Angelika Steger, A quasi-polynomial time approximation scheme for minimum weight triangulation, Journal of the ACM (JACM), v.56 n.3, p.1-47, May 2009
	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