Computing the first Betti number of a semi-algebraic set. (English) Zbl 1142.14036
Summary: We describe a singly exponential algorithm for computing the first Betti number of a given semi-algebraic set. Singly exponential algorithms for computing the zeroth Betti number, and the Euler-Poincaré characteristic, were known before. No singly exponential algorithm was known for computing any of the individual Betti numbers other than the zeroth one. As a consequence we also obtain algorithms for computing semi-algebraic descriptions of the semi-algebraically connected components of any given real algebraic or semi-algebraic set in singly exponential time, which improves on the complexity of the previously published algorithms for this problem.
MSC:
| 14P10 | Semialgebraic sets and related spaces |
| 14P25 | Topology of real algebraic varieties |
| 14Q15 | Computational aspects of higher-dimensional varieties |
References:
| [1] | S. Basu, On bounding the Betti numbers and computing the Euler characteristics of semi-algebraic sets, Discrete Comput. Geom. 22 (1999), 1–18. · Zbl 0973.14033 · doi:10.1007/PL00009443 |
| [2] | S. Basu, On different bounds on different Betti numbers, Discrete Comput. Geom. 30(1) (2003), 65–85. · Zbl 1073.14556 |
| [3] | S. Basu, Computing the first few Betti numbers of semi-algebraic sets in singly exponential time, J. Symb. Comput. 41(10) (2006), 1125–1154. · Zbl 1126.14065 · doi:10.1016/j.jsc.2006.07.001 |
| [4] | S. Basu, R. Pollack, and M.-F. Roy, On the combinatorial and algebraic complexity of quantifier elimination, J. ACM 43 (1996), 1002–1045. · Zbl 0885.68070 · doi:10.1145/235809.235813 |
| [5] | S. Basu, R. Pollack, and M.-F. Roy, Computing roadmaps of semi-algebraic sets on a variety, J. Am. Math. Soc. 3(1) (1999), 55–82. · Zbl 0933.14037 |
| [6] | S. Basu, R. Pollack, and M.-F. Roy, Algorithms in Real Algebraic Geometry, Springer, New York, 2003. Updated version available electronically at: www.math.gatech.edu/ saugata/bpr-posted1.html. |
| [7] | S. Basu, R. Pollack, and M.-F. Roy, Betti number bounds, applications and algorithms, in: Current Trends in Combinatorial and Computational Geometry: Papers from the Special Program at MSRI, MSRI Publications, Vol. 52, pp. 87–97, Cambridge University Press, Cambridge, 2005. |
| [8] | J. Bochnak, M. Coste, and M.-F. Roy, Géométrie algébrique réelle, Springer, Paris, 1987. Real Algebraic Geometry, Springer, New York, 1998. |
| [9] | P. Burgisser and F. Cucker, Counting complexity classes for numeric computations II: Algebraic and semi-algebraic sets, J. Complex. 22(2) (2006), 147–191. · Zbl 1149.68029 · doi:10.1016/j.jco.2005.11.001 |
| [10] | J. Canny, Computing road maps in general semi-algebraic sets, Comput. J. 36 (1993), 504–514. · Zbl 0798.14031 · doi:10.1093/comjnl/36.5.504 |
| [11] | G. Collins, Quantifier elimination for real closed fields by cylindric algebraic decomposition, in: Second GI Conference on Automata Theory and Formal Languages, Lecture Notes in Computer Science, Vol. 33, pp. 134–183, Springer, Berlin, 1975. |
| [12] | A. Gabrielov and N. Vorobjov, Betti numbers of semialgebraic sets defined by quantifier-free formulae, Discrete Comput. Geom. 33 (2005), 395–401. · Zbl 1073.14072 · doi:10.1007/s00454-004-1105-7 |
| [13] | L. Gournay and J.J. Risler, Construction of roadmaps of semi-algebraic sets, Appl. Algebra Engrg. Comm. Comput. 4(4) (1993), 239–252. · Zbl 0807.14047 · doi:10.1007/BF01200148 |
| [14] | D. Grigor’ev and N. Vorobjov, Counting connected components of a semi-algebraic set in sub-exponential time, Comput. Complex. 2 (1992), 133–186. · Zbl 0900.68253 · doi:10.1007/BF01202001 |
| [15] | R.M. Hardt, Semi-algebraic local triviality in semi-algebraic mappings, Am. J. Math. 102 (1980), 291–302. · Zbl 0465.14012 · doi:10.2307/2374240 |
| [16] | J. Heintz, M.-F. Roy, and P. Solernò, Description of the connected components of a semi-algebraic set in single exponential time, Discrete Comput. Geom. 11 (1994), 121–140. · Zbl 0970.68201 · doi:10.1007/BF02573999 |
| [17] | J. McCleary, A User’s Guide to Spectral Sequences, 2nd ed., Cambridge Studies in Advanced Mathematics, Cambridge University Press, Cambridge, 2001. · Zbl 0959.55001 |
| [18] | J. Milnor, On the Betti numbers of real varieties, Proc. Am. Math. Soc. 15 (1964), 275–280. · Zbl 0123.38302 · doi:10.1090/S0002-9939-1964-0161339-9 |
| [19] | O.A. Oleinik, Estimates of the Betti numbers of real algebraic hypersurfaces, Mat. Sb. (N.S.) 28(70) (1951), 635–640 (in Russian). |
| [20] | O.A. Oleinik and I.B. Petrovskii, On the topology of real algebraic surfaces, Izv. Akad. Nauk SSSR 13 (1949), 389–402. |
| [21] | J. Renegar, On the computational complexity and geometry of the first-order theory of the reals, J. Symb. Comput. 13 (1992), 255–352. · Zbl 0763.68042 · doi:10.1016/S0747-7171(10)80003-3 |
| [22] | Rotman, J.J.: An Introduction to Algebraic Topology, Springer, New York, 1988. · Zbl 0661.55001 |
| [23] | R. Thom, Sur l’homologie des variétés algébriques réelles, in: Differential and Combinatorial Topology, pp. 255–265, Princeton University Press, Princeton, 1965. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
