1亿文档 免费下载

免费下载此文档# Computing roadmaps of semi-algebraic sets on a variety

### Word文档免费下载：Computing roadmaps of semi-algebraic sets on a variety

（下载1-28页，共28页）

*Let R be a real closed field, Z(Q) a real algebraic variety defined as the zero set of a polynomial Q 2 R[X 1; : : : ; X k] and S a semi-algebraic subset of Z(Q), defined*

JOURNAL OF THE AMERICAN MATHEMATICAL SOCIETY Volume 13, Number 1, Pages 55{82 S 0894-0347(99)00311-2 Article electronically published on July 20, 1999

COMPUTING ROADMAPS OF SEMI-ALGEBRAIC SETS ON A VARIETY SAUGATA BASU, RICHARD POLLACK, AND MARIE-FRANCOISE ROY

1. Introduction Let R be a real closed eld, Z(Q) a real algebraic variety de ned as the zero set of a polynomial Q 2 R X1;:::; Xk] and S a semi-algebraic subset of Z(Q), de ned by a Boolean formula with atoms of the form P< 0; P> 0; P= 0 with P 2 P, where P is a nite subset of R X1;:::; Xk]. A semi-algebraic set C is semi-algebraically connected if it is non-empty and is not the union of two non-empty disjoint semi-algebraic sets which are closed and open in C. A semi-algebraically connected component of S is a semi-algebraic subset of S which is semi-algebraically connected, and closed and open in S . Semi-algebraic sets have a nite number of semi-algebraically connected components ( 5], page 34). A roadmap of S, which we denote R(S); is a semi-algebraic set of dimension at most one contained in S which satis es the roadmap conditions: RM1 For every semi-algebraically connected component C of S, C\ R(S) is semialgebraically connected. RM2 For every x 2 R; and for every semi-algebraically connected component C 0 of Sx, C 0\ R(S) 6=;: Here, and everywhere else in this paper, is the projection on the rst coordinate and for X R, SX is S\?1 (X): We also use the abbreviations Sx, S<c, and S c for Sfxg, S(?1;c), and S(?1;c] respectively. Algorithms for the construction of roadmaps are described in terms of the parameters k; k0; s; d where k is the dimension of the ambient space, k0 is the dimension of Z(Q), s is the number of polynomials in P and d is a bound on the degrees of the polynomials in P and the polynomial Q. Given a roadmap R(S) and a point p 2 S the connecting subroutine outputs a semi-algebraic continuous path in S (p) connecting p to R(S). The connecting subroutine is described in terms of the parameters k; k0; s; d as before and which is a bound on the degrees of the polynomials de ning p (see section 4 for a discussion of how points are described by polynomials). Received by the editors November 25, 1997 and, in revised form, April 14, 1999. 1991 Mathematics Subject Classi cation. Primary 14P10, 68Q25; Secondary 68Q40. Key words and phrases. Roadmaps, semi-algebraic sets, variety. The rst author was supported in part by NSF Grants CCR-9402640 and CCR-9424398. The second author was supported in part by NSF Grants CCR-9402640, CCR-9424398, DMS9400293, CCR-9711240 and CCR-9732101. The third author was supported in part by the project ESPRIT-LTR 21024 FRISCO and by European Community contract CHRX-CT94-0506. 55 c 1999 American Mathematical Society

## 我要评论