Efficient algorithm for computing the Euler-Poincare characteristic of a semi-algebraic set defined by few quadratic inequalities

Saugata Basu
Computational Complexity
Issue Volume 15, Number 3 / October, 2006
Pages 236-251
http://dx.doi.org/10.1007/s00037-006-0214-5

d変数2次多項式が導く不等式が個あり、その論理結合として表される集合Xがあるとする。
このXのEuler-Poincare標数を計算するアルゴリズムを与えている。
計算量はである。