On the number of cells defined by a family of polynomials on a variety

被引:30
作者
Basu, S [1 ]
Pollack, R [1 ]
Roy, MF [1 ]
机构
[1] UNIV RENNES 1, IRMAR, URA CNRS 305, F-35042 RENNES, FRANCE
关键词
D O I
10.1112/S0025579300011621
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
Let R be a real closed field and V a variety of real dimension k' which is the zero set of a polynomial Q is an element of R[X(1),...,X(k)] of degree at most d. Given a family of s polynomials P = {P-1,..., P-s} subset of R[X(1),...,X(k)] where each polynomial in P has degree at most d, we prove that the number of cells defined by P over V is ((K)'(s))(O(d))(k). Note that the combinatorial part of the bound depends on the dimension of the variety rather than on the dimension of the ambient space.
引用
收藏
页码:120 / 126
页数:7
相关论文
共 16 条
[1]  
BASU S, 1994, AN S FDN CO, P632
[2]  
Bochnak J., 1987, Geometrie Algebrique Reelle
[3]   COMPUTING ROADMAPS OF GENERAL SEMI-ALGEBRAIC SETS [J].
CANNY, J .
COMPUTER JOURNAL, 1993, 36 (05) :504-514
[4]   IMPROVED ALGORITHMS FOR SIGN DETERMINATION AND EXISTENTIAL QUANTIFIER ELIMINATION [J].
CANNY, J .
COMPUTER JOURNAL, 1993, 36 (05) :409-418
[5]  
Edelsbrunner H., 1987, ALGORITHMS COMBINATO
[6]  
Goodman J. E., 1994, Proceedings of the Tenth Annual Symposium on Computational Geometry, P192, DOI 10.1145/177424.177624
[7]  
HEINTZ J, 1989, P IFIP, P293
[8]  
Milnor J., 1964, Proc. Am. Math. Soc, V15, P275, DOI DOI 10.1090/S0002-9939-1964-0161339-9
[9]  
OLEINIK OA, 1951, MAT SBORNIK, V28, P635
[10]  
POLLACK R, 1993, CR ACAD SCI I-MATH, V316, P573