A NEW DUALITY RESULT CONCERNING VORONOI DIAGRAMS

被引：18

作者：

AURENHAMMER, F ^{[1
]}

机构：

[1] AUSTRIAN COMP SOC,INST INFORMAT PROC,A-8010 GRAZ,AUSTRIA

来源：

DISCRETE & COMPUTATIONAL GEOMETRY | 1990年 / 5卷 / 03期

关键词：

D O I：

10.1007/BF02187788

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

A new duality between order-k Voronoi diagrams in Ed and convex hulls in Ed+1 is established. It implies a reasonably simple algorithm for computing the order-k diagram for n points in the plane in O(k2n log n) time and optimal O(k(n-k)) space. © 1990 Springer-Verlag New York Inc.

引用

页码：243 / 254

页数：12

共 11 条

[1] POWER DIAGRAMS - PROPERTIES, ALGORITHMS AND APPLICATIONS [J].

AURENHAMMER, F .

SIAM JOURNAL ON COMPUTING, 1987, 16 (01) :78-96

[2] A CRITERION FOR THE AFFINE EQUIVALENCE OF CELL COMPLEXES IN RD AND CONVEX POLYHEDRA IN RD+1 [J].

AURENHAMMER, F .

DISCRETE & COMPUTATIONAL GEOMETRY, 1987, 2 (01) :49-64

[3] VORONOI DIAGRAMS FROM CONVEX HULLS [J].

BROWN, KQ .

INFORMATION PROCESSING LETTERS, 1979, 9 (05) :223-228

[4] AN IMPROVED ALGORITHM FOR CONSTRUCTING KTH-ORDER VORONOI DIAGRAMS [J].

CHAZELLE, B ;

EDELSBRUNNER, H .

IEEE TRANSACTIONS ON COMPUTERS, 1987, 36 (11) :1349-1354

[5] Edge-Skeletons in Arrangements with Applications [J].

Edelsbrunner, H. .

ALGORITHMICA, 1986, 1 (1-4) :93-109

[6] CONSTRUCTING ARRANGEMENTS OF LINES AND HYPERPLANES WITH APPLICATIONS [J].

EDELSBRUNNER, H ;

OROURKE, J ;

SEIDEL, R .

SIAM JOURNAL ON COMPUTING, 1986, 15 (02) :341-363

[7]

LEE DT, 1982, IEEE T COMPUT, V31, P478, DOI 10.1109/TC.1982.1676031

[8] CONVEX HULLS OF FINITE SETS OF POINTS IN 2 AND 3 DIMENSIONS [J].

PREPARATA, FP ;

HONG, SJ .

COMMUNICATIONS OF THE ACM, 1977, 20 (02) :87-93

[9]

SEIDEL R, 1981, 8114 U BRIT COL DEP

[10]

SEIDEL R, 1986, 18TH P ACM S THEOR C, P404

← 1 2 →