Combinatorial complexity in O-minimal geometry
Author:
Open Access
- 11 June 2007
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 47-56
Abstract
In this paper we prove tight bounds on the combinatorial and topological complexity of sets dened in terms of n denable sets belonging to some fixed denable family of sets in an o-minimal structure. This generalizes the combinatorial parts of similar bounds known in the case of semi-algebraic and semi-Pfaffian sets, and as a result vastly increases the applicability of results on combinatorial and topological complexity of arrangements studied in discrete and computational geometry. As a sample application, we extend a Ramsey-type theorem due to Alon et al. [3], originally proved for semi-algebraic sets of fixed description complexity to this more general setting.Keywords
All Related Versions
This publication has 13 references indexed in Scilit:
- Crossing patterns of semi-algebraic setsJournal of Combinatorial Theory, Series A, 2005
- Betti Numbers of Semialgebraic Sets Defined by Quantifier-Free FormulaeDiscrete & Computational Geometry, 2004
- BETTI NUMBERS OF SEMIALGEBRAIC AND SUB-PFAFFIAN SETSJournal of the London Mathematical Society, 2004
- Different Bounds on the Different Betti Numbers of Semi-Algebraic SetsDiscrete & Computational Geometry, 2003
- The Combinatorial and Topological Complexity of a Single CellDiscrete & Computational Geometry, 2002
- Complexity of cylindrical decompositions of sub-Pfaffian setsJournal of Pure and Applied Algebra, 2001
- Real quantifier elimination is doubly exponentialJournal of Symbolic Computation, 1988
- Semi-Algebraic Local-Triviality in Semi-Algebraic MappingsAmerican Journal of Mathematics, 1980
- Sur L'Homologie des Varietes Algebriques Réelles1965
- On the Betti numbers of real varietiesProceedings of the American Mathematical Society, 1964