caa a22 4500 46790961X CHVBK 20180406152845.0 cr unu---uuuuu 170328e20061001xx s 000 0 eng 10.1007/s00037-006-0214-5 doi (NATIONALLICENCE)springer-10.1007/s00037-006-0214-5 Basu Saugata School of Mathematics, Georgia Institute of Technology, 30332, Atlanta, GA, U.S.A aut Efficient algorithm for computing the Euler-Poincaré characteristic of a semi-algebraic set defined by few quadratic inequalities [Elektronische Daten] [Saugata Basu] Abstract.: We present an algorithm which takes as input a closed semi-algebraic set, S⊂ Rk, defined by $$ P_{1} \leq 0, \ldots ,P_{\ell} \leq 0,\quad P_{i} \in \hbox{R}[X_{1} , \ldots ,X_{k} ],\quad \deg (P_{i} ) \leq 2, $$ and computes the Euler-Poincaré characteristic of S. The complexity of the algorithm is kO(ℓ). Birkhäuser Verlag, Basel, 2006 Semi-algebraic sets nationallicence Euler-Poincaré characteristic nationallicence 14P10 nationallicence 14P25 nationallicence computational complexity Birkhäuser-Verlag; www.birkhäuser.ch 15/3(2006-10-01), 236-251 1016-3328 15:3<236 2006 15 37 https://doi.org/10.1007/s00037-006-0214-5 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00037-006-0214-5 text/html Onlinezugriff via DOI NATIONALLICENCE 100 1- Basu Saugata School of Mathematics, Georgia Institute of Technology, 30332, Atlanta, GA, U.S.A aut NATIONALLICENCE 773 0- computational complexity Birkhäuser-Verlag; www.birkhäuser.ch 15/3(2006-10-01), 236-251 1016-3328 15:3<236 2006 15 37 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer