Evaluating signs of determinants using single-precision arithmetic

被引：28

作者：

Avnaim, F

Boissonnat, JD

Devillers, O

Preparata, FP

Yvinec, M

机构：

[1] BROWN UNIV,DEPT COMP SCI,PROVIDENCE,RI 02912

[2] INST NATL RECH INFORMAT & AUTOMAT,F-06560 VALBONNE,FRANCE

[3] CNRS URA 1376,F-06560 VALBONNE,FRANCE

来源：

ALGORITHMICA | 1997年 / 17卷 / 02期

关键词：

computational geometry; exact arithmetic; precision; robust algorithms;

D O I：

10.1007/BF02522822

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 [计算机软件与理论]; 0835 [软件工程];

摘要：

We propose a method of evaluating signs of 2 x 2 and 3 x 3 determinants with b-bit integer entries using only b and (b + 1)-bit arithmetic, respectively. This algorithm has numerous applications in geometric computation and provides a general and practical approach to robustness. The algorithm has been implemented and compared with, other exact computation methods.

引用

页码：111 / 132

页数：22

共 17 条

[1]

Benouamer M. O., 1993, CCCG. Proceedings of the Fifth Canadian Conference on Computational Geometry, P73

[2]

Clarkson K. L., 1992, Proceedings 33rd Annual Symposium on Foundations of Computer Science (Cat. No.92CH3188-0), P387, DOI 10.1109/SFCS.1992.267751

[3]

Fortune S., 1992, Proceedings of the Eighth Annual Symposium on Computational Geometry, P83, DOI 10.1145/142675.142695

[4]

FORTUNE S, 1989, 30 ANN S FDN COMP SC, P494

[5]

FORTUNE S, 1991, P 7 ANN ACM S COMP G, P334

[6]

FORTUNE S, 1993, P 9 ANN ACM S COMP G, P163

[7]

FORTUNE S, 1994, USER MANUAL

[8]

Greene D. H., 1986, 27th Annual Symposium on Foundations of Computer Science (Cat. No.86CH2354-9), P143, DOI 10.1109/SFCS.1986.19

[9]

ROBUST SET OPERATIONS ON POLYHEDRAL SOLIDS [J].

HOFFMANN, CM ;

HOPCROFT, JE ;

KARASICK, MS .

IEEE COMPUTER GRAPHICS AND APPLICATIONS, 1989, 9 (06) :50-59

[10]

EFFICIENT DELAUNAY TRIANGULATION USING RATIONAL ARITHMETIC [J].

KARASICK, M ;

LIEBER, D ;

NACKMAN, LR .

ACM TRANSACTIONS ON GRAPHICS, 1991, 10 (01) :71-91

← 1 2 →