APPROXIMATING THE MINIMUM WEIGHT STEINER TRIANGULATION

被引：27
作者：
EPPSTEIN, D
机构：
[1] Department of Information and Computer Science, University of California, Irvine, 92717, CA
来源：
DISCRETE & COMPUTATIONAL GEOMETRY | 1994年 / 11卷 / 02期
关键词：
D O I：
10.1007/BF02574002
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
We show that the length of the minimum weight Steiner triangulation (MWST) of a point set can be approximated within a constant factor by a triangulation algorithm based on quadtrees. In O(n log n) time we can compute a triangulation with O(n) new points, and no obtuse triangles, that approximates the MWST. We can also approximate the MWST with triangulations having no sharp angles. We generalize some of our results to higher-dimensional triangulation problems. No previous polynomial-time triangulation algorithm was known to approximate the MWST within a factor better than O(log n).
引用
收藏
页码：163 / 191
页数：29
相关论文
共 27 条
[1]  
BERN M, IN PRESS J COMPUT SY
[2]  
BERN M, 1990, 31 ANN S FDN COMP SC, P231
[3]  
CLARKSON K, 1991, 2ND P ANN ACM SIAM S, P17
[4]   ON OPTIMAL INTERPOLATION TRIANGLE INCIDENCES [J].
DAZEVEDO, EF ;
SIMPSON, RB .
SIAM JOURNAL ON SCIENTIFIC AND STATISTICAL COMPUTING, 1989, 10 (06) :1063-1075
[5]  
DU DZ, 1990, 31ST P ANN S F COMP, P76
[6]  
EDELSBRUNNER H, 1991, 32ND P IEEE S F COMP, P414
[7]  
EDELSBRUNNER H, 1990, 6TH P ANN S COMP GEO, P44
[8]  
Eppstein D., 1992, Computational Geometry: Theory and Applications, V1, P143, DOI 10.1016/0925-7721(92)90013-I
[9]  
EPPSTEIN D, 1992, 2ND P ACM SIAM S DIS, P48
[10]  
Garey M.R., 1979, COMPUTERS INTRACTABI, V174
123