CONSTRUCTION OF THE VORONOI DIAGRAM FOR ONE MILLION GENERATORS IN SINGLE-PRECISION ARITHMETIC

被引：84

作者：

SUGIHARA, K

IRI, M

机构：

[1] Department of Mathematical Engineering and Information Physics, Faculty of Engineering, University of Tokyo, Bunkyo-ku, Tokyo, 113

来源：

PROCEEDINGS OF THE IEEE | 1992年 / 80卷 / 09期

关键词：

D O I：

10.1109/5.163412

中图分类号：

TM [电工技术]; TN [电子技术、通信技术];

学科分类号：

0808 ; 0809 ;

摘要：

The paper presents a numerically stable algorithm for constructing Voronoi diagrams in the plane. In this algorithm higher priority is placed on the topological structure than on numerical values, so that, however large the numerical errors, the algorithm will never come across topological inconsistency and thus can always complete its task The behavior of the algorithm is shown with examples, including one for as many as 10(6) generators.

引用

页码：1471 / 1484

页数：14

共 23 条

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

AURENHAMMER, F .

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

[2] A PYRAMIDAL DATA STRUCTURE FOR TRIANGLE-BASED SURFACE DESCRIPTION [J].

DEFLORIANI, L .

IEEE COMPUTER GRAPHICS AND APPLICATIONS, 1989, 9 (02) :67-78

[3]

DOBKIN D, 1988, 4TH P ACM S COMP GEO, P93

[4]

EDELSBRUNNER H, 1987, ALGORITHMS COMB GEOM

[5] SEGMENTING DOT PATTERNS BY VORONOI DIAGRAM CONCAVITY [J].

FAIRFIELD, J .

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, 1983, 5 (01) :104-110

[6] A SWEEPLINE ALGORITHM FOR VORONOI DIAGRAMS [J].

FORTUNE, S .

ALGORITHMICA, 1987, 2 (02) :153-174

[7] THE PROBLEMS OF ACCURACY AND ROBUSTNESS IN GEOMETRIC COMPUTATION [J].

HOFFMANN, CM .

COMPUTER, 1989, 22 (03) :31-&

[8]

HORSPOOL RN, 1979, SOCS7912 MCGILL U SC

[9]

Iri M., 1986, Methods of Operations Research, V54, P17

[10]

IRI M, 1986, COMPUTATIONAL GEOMET

← 1 2 3 →