Two- versus three-dimensional connectivity testing of first-order queries to semi-algebraic sets

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

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.
corrected minor confusion in Proof of Theorem 1

Keywords

Logic in Computer Science, Computational Geometry, Databases, F.4.1; F.2.2; H.2.8

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/31733

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/cs/0308001
 http://arxiv.org/abs/cs/0308001
 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"
 doi:10.1007/s00236-005-0171-5

Collections

arXiv