DYNAMIC ALGORITHMS IN COMPUTATIONAL GEOMETRY

被引：70
作者：
CHIANG, YJ
TAMASSIA, R
机构：
[1] Department of Computer Science, Brown University, Providence
来源：
PROCEEDINGS OF THE IEEE | 1992年 / 80卷 / 09期
基金：
美国国家科学基金会;
关键词：
D O I：
10.1109/5.163409
中图分类号：
TM [电工技术]; TN [电子技术、通信技术];
学科分类号：
0808 ; 0809 ;
摘要：
Research on dynamic algorithms for geometric problems has received increasing attention in recent years, and is motivated by many important applications in circuit layout, computer graphics, and computer-aided design. In this paper we survey dynamic algorithms and data structures in the area of computational geometry. Our work has a twofold purpose: it introduces the area to the nonspecialist and reviews the state of the art for the specialist.
引用
收藏
页码：1412 / 1434
页数：23
相关论文
共 175 条
[41]   A LOWER BOUND ON THE COMPLEXITY OF ORTHOGONAL RANGE QUERIES [J].
FREDMAN, ML .
JOURNAL OF THE ACM, 1981, 28 (04) :696-705
[42]  
FREDMAN ML, 1990, PROCEEDINGS OF THE TWENTY SECOND ANNUAL ACM SYMPOSIUM ON THEORY OF COMPUTING, P1, DOI 10.1145/100216.100217
[43]  
GOODRICH MT, 1990, PROCEEDINGS OF THE FIRST ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P118
[44]  
GOODRICH MT, 1991, 23RD P ANN ACM STOC, P523
[45]   DYNAMIC VORONOI DIAGRAMS [J].
GOWDA, IG ;
KIRKPATRICK, DG ;
LEE, DT ;
NAAMAD, A .
IEEE TRANSACTIONS ON INFORMATION THEORY, 1983, 29 (05) :724-731
[46]   PRIMITIVES FOR THE MANIPULATION OF GENERAL SUBDIVISIONS AND THE COMPUTATION OF VORONOI DIAGRAMS [J].
GUIBAS, L ;
STOLFI, J .
ACM TRANSACTIONS ON GRAPHICS, 1985, 4 (02) :74-123
[47]  
Guibas L.J., 1978, 19TH P ANN IEEE S F, P8
[48]  
GUIBAS LJ, 1990, LECT NOTES COMPUT SC, V443, P414, DOI 10.1007/BFb0032048
[49]  
HERSHBERGER J, 1991, PROCEEDINGS OF THE SECOND ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P32
[50]  
HERSHBERGER J, 1990, LECT NOTES COMPUT SC, V447, P380
12345678910