A fast heuristic for approximating the minimum weight triangulation

1. G. Das and D. Joseph. Which triangulations approximate the complete graph. In Proc. Inter. Symp. on Optimal Algorithms, LNCS 401 (Springer, 1989) 168–183.

   Google Scholar 

2. M. T. Dickerson, R. L. S. Drysdale, S. A. McElfresh, and E. Welzl. Fast greedy triangulation algorithms. Proc. 10th ACM Symp. on Comp. Geom. (1994) 211–220.

   Google Scholar 

3. D. Eppstein. Approximating the minimum weight triangulation. Disc, and Comp. Geom. 11 (1994) 163–191.

   Google Scholar 

4. P. D. Gilbert. New results in planar triangulations. Master's thesis, Univ. of Illinois, Urbana, 1979.

   Google Scholar 

5. S. Goldman. A space efficient greedy triangulation algorithm. Infor. Proc. Lett. 31 (1989) 191–196.

   Google Scholar 

6. L. Heath and S. Pemmaraju. New results for the minimum weight triangulation problem. Algorithmica 12 (1994) 533–552.

   Google Scholar 

7. J. M. Keil. Decomposing a Polygon into Simpler Components. PhD thesis, Univ. of Toronto, Canada, 1983.

   Google Scholar 

8. J. M. Keil. Computing a subgraph of the minimum weight triangulation. Comp. Geom.: Theory & Appl. 4 (1994) 13–26.

   Google Scholar 

9. D. G. Kirkpatrick. A note on Delaunay and optimal triangulations. Infor. Proc. Lett. 10 (1980) 127–128.

   Google Scholar 

10. D. Krznaric and C. Levcopoulos. Computing a threaded quadtree from the Delaunay triangulation in linear time. In Proc. 7th CCCG (1995) 187–192.

    Google Scholar 

11. D. Krznaric and C. Levcopoulos. Computing hierarchies of clusters from the EMST in linear time. In Proc. 15th FST&TCS, LNCS 1026 (Springer, 1995) 443–455.

    Google Scholar 

12. C. Levcopoulos and D. Krznaric. The greedy triangulation can be computed from the Delaunay in linear time. Tech. Rep. LU-CS-TR:94-136, Lund Univ., 1994.

    Google Scholar 

13. C. Levcopoulos and D. Krznaric. Quasi-greedy triangulations approximating the minimum weight triangulation. In Proc. 7th SODA (1995) 392–401.

    Google Scholar 

14. C. Levcopoulos and D. Krznaric. Tight lower bounds for minimum weight triangulation heuristics. Infor. Proc. Lett. 57 (1996) 129–135.

    Google Scholar 

15. C. Levcopoulos and A. Lingas. Fast algorithms for greedy triangulation. BIT 32 (1992) 280–296.

    Google Scholar 

16. C. Levcopoulos and A. Lingas. The greedy triangulation approximates the MWT and can be computed in linear time in the average case. In Proc. ICCI, LNCS 497 (Springer, 1991).

    Google Scholar 

17. A. Lingas. Advances in minimum weight triangulation. PhD thesis, Linköping Univ., Sweden, 1983.

    Google Scholar 

18. F. P. Preparata and M. I. Shamos. Computational Geometry: An Introduction (Springer, 1985).

    Google Scholar 

19. D. A. Plaisted and J. Hong. A heuristic triangulation algorithm. J. of Algorithms 8 (1987) 405–437.

    Google Scholar 

20. W. D. Smith. Studies in Computational Geometry Motivated by Mesh Generation. PhD thesis, Princeton Univ., 1989.

    Google Scholar 

21. C. A. Wang. An optimal algorithm for greedy triangulation of a set of points. In Proc. 6th CCCG (1994) 332–338.

    Google Scholar 

22. C. A. Wang and F. Chin. Finding the constrained Delaunay triangulation and constrained Voronoi diagram of a simple polygon in linear-time. In Proc. 3rd ESA, LNCS 979 (Springer, 1995) 280–294.

    Google Scholar 

23. P. Yoeli. Compilation of data for computer-assisted relief cartography. In J. C. Davis and M. J. McCullagh, eds., Display and Analysis of Spatial Data (Wiley, 1975).

    Google Scholar 

Download references