Two- versus three-dimensional connectivity testing of first-order queries to semi-algebraic sets
<|reference_start|>Two- versus three-dimensional connectivity testing of first-order queries to semi-algebraic sets: This paper addresses the question whether one can determine the connectivity of a semi-algebraic set in three dimensions by testing the connectivity of a finite number of two-dimensional ``samples'' of the set, where these samples are defined by first-order queries. The question is answered negatively for two classes of first-order queries: cartesian-product-free, and positive one-pass.<|reference_end|>
@article{geerts2003two-,
    title={Two- versus three-dimensional connectivity testing of first-order
  queries to semi-algebraic sets},
    author={Floris Geerts, Lieven Smits, Jan Van den Bussche},
    journal={A revised version has been published online (21 July 2005) in Acta
  Informatica under the title "N- versus (N-1)-dimensional connectivity testing
  of first-order queries to semi-algebraic sets"},
    year={2003},
    doi={10.1007/s00236-005-0171-5},
    archivePrefix={arXiv},
    eprint={cs/0308001},
    primaryClass={cs.LO cs.CG cs.DB}
}