Publication Date:
2013-09-26
Description:
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 $$\mathcal{P}$$ [Q] be the domain of bounded, non-empty, rational polyhedra in two- or three-dimensional Euclidean space. A relation over $$\mathcal{P}$$ [Q] is definable in the structure 〈 $$\mathcal{P}$$ [Q], 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 $$\mathcal{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 〈 $$\mathcal{R}$$ , C 〉.
Print ISSN:
0955-792X
Electronic ISSN:
1465-363X
Topics:
Computer Science
,
Mathematics
Permalink
