A LINEAR-TIME ALGORITHM FOR COMPUTING THE VORONOI DIAGRAM OF A CONVEX POLYGON

被引：165
作者：
AGGARWAL, A
GUIBAS, LJ
SAXE, J
SHOR, PW
机构：
[1] STANFORD UNIV, DEPT COMP SCI, STANFORD, CA 94305 USA
[2] DEC, SYST RES CTR, PALO ALTO, CA 94301 USA
[3] AT&T BELL LABS, MURRAY HILL, NJ 07974 USA
来源：
DISCRETE & COMPUTATIONAL GEOMETRY | 1989年 / 4卷 / 06期
关键词：
D O I：
10.1007/BF02187749
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
引用
收藏
页码：591 / 604
页数：14
相关论文
共 11 条
[1]  
CHEW LP, 1987, 3RD P ANN ACM S COMP, P223
[2]   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
[3]   OPTIMAL SEARCH IN PLANAR SUBDIVISIONS [J].
KIRKPATRICK, D .
SIAM JOURNAL ON COMPUTING, 1983, 12 (01) :28-35
[4]  
Kirkpatrick D. G., 1979, 20th Annual Symposium of Foundations of Computer Science, P18, DOI 10.1109/SFCS.1979.15
[5]   GENERALIZED DELAUNAY TRIANGULATION FOR PLANAR GRAPHS [J].
LEE, DT ;
LIN, AK .
DISCRETE & COMPUTATIONAL GEOMETRY, 1986, 1 (03) :201-217
[6]  
LEE DT, 1982, IEEE T COMPUT, V31, P478, DOI 10.1109/TC.1982.1676031
[7]   LINEAR ALGORITHM FOR FINDING THE CONVEX-HULL OF A SIMPLE POLYGON [J].
MCCALLUM, D ;
AVIS, D .
INFORMATION PROCESSING LETTERS, 1979, 9 (05) :201-206
[8]  
Preparata F. P., 2012, COMPUTATIONAL GEOMET
[9]  
PREPARATA FP, 1977, LECT NOTES COMPUTER, V53, P443
[10]  
Shamos MI, 1978, THESIS YALE U NEW HA
12