Siu-Wing Cheng
Yin-Feng Xu
- 1.O. AICHHOLZER, F. AURENHAMMER, M. TASCHWER, AND G. ROTE, Triangulations intersect nicely, in Proc. 11th Annual Symposium on Computational Geometry, 1995. Google Scholar
Digital Library
- 2.M. BERN, H. EDELSBRUNNER, D. EPPSTEIN, $. MITCHELL, AND T. TAN, Edge insertion for optimal triangulations, Discrete & Computational Geometry, 10 (1993), pp. 47-65.Google ScholarDigital Library
- 3.M. DICKEgSON, S. MCELFRESH, AND M. MON- TAGUE, New algorithms and empirical findings on minimum weight triangulation heuristics, in Proc. 11th ACM Symp. on Computational Geometry, 1995, pp. 238-247. Google ScholarDigital Library
- 4.R. DUPPE AND H. GOTTSCHALK, A uiomaiische interpolation yon isolinen bet willkurlichen stuizpunkien, Allgemeine Vermeasungsberichten, 77 (1970), pp. 423-426.Google Scholar
- 5.H. EDELSBRUNNER, Algorithms in Combinatorial Geometry, Springer-Verlag, 1987. Google ScholarDigital Library
- 6.P. GILBERT, New results on planar triangulations, master's thesis, University of Illinois, 1979. Report No. UILUENG 78 2243.Google Scholar
- 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.Google ScholarCross Ref
- 8.L. HEATH AND S. PEMMARAJU, New results for the minimum weight triangulation problem, Algorithmica, 12 (1994), pp. 533-552.Google ScholarDigital Library
- 9.M. KErn, Computing a subgraph of the minimum weight triangulation, Computational Geometry: Theory and Applications, 4 (1994), pp. 13-26. Google ScholarDigital Library
- 10.D. KIRKPATRICK AND J. RADKE, A framework jbr computational morphology, in Computational Geometry, G. Toussaint, ed., Elsevier, Amsterdam, 1985, pp. 217-248.Google ScholarCross Ref
- 11.C. LEVCOPOULOS AND D. KaZNAaW, Quasigreedy lriangulations approximating the minim~,m weight triangulation, in Proceedings of the Annum ACM-SIAM Symposium on Discrete Algorithms, 1996, pp. 392-401. Google ScholarDigital Library
- 12.A. LINGAS, A new heuristic for minimum weight triangulation, SiAM Journal on Algebraic and Discrete Methods, 8 (1987), pp. 646-658~ Google ScholarDigital Library
- 13.D. PLAiSTED AND J. HONG, A heuristic triangulation algorithm, Journal of Algorithms, 8 (1987), pp. 405-437. Google ScholarDigital Library
- 14.B. YANG, A better subgraph of the minimum weight triangulation, in Proceedings of International Conference on Computing and Combinatorics, 1995, pp. 452-455. Google ScholarDigital Library
- 15.B. YANG, Y. Xv, AND Z. You, A chain decomposition algorithm for the proof of a property on minimum weight triangulation, in Proceedings of International Symposium on Algorithms and Computation, 1994, pp. 423-427. Google ScholarDigital Library
- 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.Google Scholar
Index Terms
- Approaching the largest β-skeleton within a minimum weight triangulation
Recommendations
New results for the minimum weight triangulation problem
Given a finite set of points in a plane, a triangulation is a maximal set of nonintersecting line segments connecting the points. The weight of a triangulation is the sum of the Euclidean lengths of its line segments. No polynomial-time algorithm is ...
Minimum weight triangulation is NP-hard
SCG '06: Proceedings of the twenty-second annual symposium on Computational geometryA triangulation of a planar point set S is a maximal plane straight-line graph with vertex set S. In the minimum weight triangulation (MWT) problem, we are looking for a triangulation of a given point set that minimizes the sum of the edge lengths. We ...
An Ant Colony Algorithm for the Minimum Weight Triangulation
ICCSA '10: Proceedings of the 2010 International Conference on Computational Science and Its ApplicationsA triangulation of a planar set S is a maximal plane straight-line graph with the vertex set S. In the Minimum Weight Triangulation (MWT) problem, we want to draw a triangulation of a given point set that minimizes the sum of the edges length. Recently, ...
Comments