Abstract
We consider the expressive power of the first-order structure 〈Ω,C 〉 where Ω is either of two of different domains of extended regions in Euclidean space, and C(x,y) is the topological relation 'Region x is in contact with region y.' We prove two main theorems: Let P[+] be the domain of bounded, non-empty, rational polyhedra in two- or three-dimensional Euclidean space. A relation Γ over P[+] is definable in the structure 〈P[+], C〉 if and only if Γ is arithmetic and invariant under rational PL-homeomorphisms of the space to itself. We also extend this result to a number of other domains, including the domain of all polyhedra and the domain of semi-algebraic regions.Let R be the space of bounded, non-empty, closed regular regions in n-dimensional Euclidean space. Any analytical relation over lower dimensional (i.e. empty interior) compact point sets that is invariant under homeomorphism is implicitly definable in the structure 〈R,C〉.
Original language | English (US) |
---|---|
Pages (from-to) | 1107-1141 |
Number of pages | 35 |
Journal | Journal of Logic and Computation |
Volume | 23 |
Issue number | 5 |
DOIs | |
State | Published - Oct 2013 |
Keywords
- First-order language
- expressivity
- qualitative spatial reasoning
- topological language
ASJC Scopus subject areas
- Software
- Theoretical Computer Science
- Logic
- Arts and Humanities (miscellaneous)
- Hardware and Architecture