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

被引：162

作者：

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

来源：

关键词：

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
GUIBAS, L
STOLFI, J
[J]. ACM TRANSACTIONS ON GRAPHICS, 1985, 4 (02): : 74 - 123
[3] OPTIMAL SEARCH IN PLANAR SUBDIVISIONS
KIRKPATRICK, D
[J]. 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
LEE, DT
LIN, AK
[J]. 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
MCCALLUM, D
AVIS, D
[J]. 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