Which triangulations approximate the complete graph
作者： Gautam Das , Deborah Joseph
关键词:
摘要: Chew and Dobkin et. al. have shown that the Delaunay triangulation its variants are sparse approximations of complete graph, in shortest distance between two sites within is bounded by a constant multiple their Euclidean separation. In this paper, we show other classical algorithms, such as greedy triangulation, more notably, minimum weight also approximate graph sense. We design an algorithm for constructing extremely (nontriangular) planar graphs graph.
springer.com
sci-hub.st 参考文章(5)
G.T. Klincsek, Minimal Triangulations of Polygonal Domains Combinatorics 79. ,vol. 9, pp. 121- 123 ,(1980) , 10.1016/S0167-5060(08)70044-X
Glenn K. Manacher, Albert L. Zobrist, Neither the greedy nor the delaunay triangulation of a planar point set approximates the optimal triangulation Information Processing Letters. ,vol. 9, pp. 31- 34 ,(1979) , 10.1016/0020-0190(79)90104-2
P Chew, There is a planar graph almost as good as the complete graph Proceedings of the second annual symposium on Computational geometry - SCG '86. pp. 169- 177 ,(1986) , 10.1145/10515.10534
A Lingas, On approximation behavior and implementation of the greedy triangulation for convex planar point sets Proceedings of the second annual symposium on Computational geometry - SCG '86. pp. 72- 79 ,(1986) , 10.1145/10515.10523
David P. Dobkin, Steven J. Friedman, Kenneth J. Supowit, Delaunay graphs are almost as good as complete graphs 28th Annual Symposium on Foundations of Computer Science (sfcs 1987). pp. 20- 26 ,(1987) , 10.1109/SFCS.1987.18