A GEOMETRIC CONSISTENCY THEOREM FOR A SYMBOLIC PERTURBATION SCHEME

被引：36

作者：

YAP, CK

机构：

[1] Courant Institute of Mathematical Sciences, New York University, New York, NY

来源：

JOURNAL OF COMPUTER AND SYSTEM SCIENCES | 1990年 / 40卷 / 01期

基金：

美国国家科学基金会;

关键词：

D O I：

10.1016/0022-0000(90)90016-E

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

In a previous paper, we introduced a generic solution to the problem of data degeneracy in geometric algorithms. The scheme is simple to use: algorithms qualifying under our requirements just have to use a prescribed blackbox for polynomial evaluation in order to achieve a symbolic perturbation of data. In this paper, we introduce the concept of an infinitesimal perturbation and show that our method is consistent relative to such perturbations. © 1990.

引用

页码：2 / 18

页数：17

共 14 条

[1] BUCHBERGER B, 1985, RECENT TRENDS MULTID
[2] OPTIMALITY AND DEGENERACY IN LINEAR PROGRAMMING
Charnes, A.
[J]. ECONOMETRICA, 1952, 20 (02) : 160 - 170
[3] Chvatal V, 1983, LINEAR PROGRAMMING
[4] DUBE T, 1986, NYU88 COUR ROB LAB R
[5] COMPUTING A HAM-SANDWICH CUT IN 2 DIMENSIONS
EDELSBRUNNER, H
WAUPOTITSCH, R
[J]. JOURNAL OF SYMBOLIC COMPUTATION, 1986, 2 (02) : 171 - 178
[6] Edge-Skeletons in Arrangements with Applications
Edelsbrunner, H.
[J]. ALGORITHMICA, 1986, 1 (1-4) : 93 - 109
[7] EDELSBRUNNER H, 1988, 4TH P ACM S COMP GEO, P118
[8] MISHRA B, 1986, IN PRESS J INFORM SC
[9] Papadimitriou C. H., 1998, COMBINATORIAL OPTIMI
[10] ROBBIANO L, 1985, LECT NOTES COMPUT SC, V204, P513

← 1 2 →