Skip to Main content Skip to Navigation
Journal articles

Spatial reasoning about points in a multidimensional setting

Philippe Balbiani 1 Jean-François Condotta 1
1 IRIT-LILaC - Logique, Interaction, Langue et Calcul
IRIT - Institut de recherche en informatique de Toulouse
Abstract : For n ≥ 1, we consider the possible relations between two points of the Euclidean space of dimension n. We define the n-point algebra on the pattern of the point algebra and the cardinal algebra. Generalizing the concept of convexity just as the one of preconvexity, we prove that the consistency problem of convex n-point networks is polynomial for n ≥ 1, whereas the consistency problem of preconvex n-point networks is NP-complete for n ≥ 3. We characterize a subset of the set of all preconvex relations: the set of all strongly preconvex relations, which contains the set of all convex relations. We demonstrate that the consistency problem of strongly preconvex n-point networks can be decided in polynomial time by means of the weak path-consistency method for all n ≥ 1. For n = 3 the set of all strongly preconvex relations is a maximal tractable subclass of the set of all n-point relations. Finally, we prove that the concept of strong preconvexity corresponds to the one of ORD-Horn representability.
Document type :
Journal articles
Complete list of metadata

https://hal-univ-artois.archives-ouvertes.fr/hal-03300289
Contributor : Fabien Delorme <>
Submitted on : Tuesday, July 27, 2021 - 9:16:52 AM
Last modification on : Thursday, September 2, 2021 - 11:08:48 AM

Links full text

Identifiers

Citation

Philippe Balbiani, Jean-François Condotta. Spatial reasoning about points in a multidimensional setting. Applied Intelligence, Springer Verlag (Germany), 2002, 17, pp.221-238. ⟨10.1023/A:1020079114666⟩. ⟨hal-03300289⟩

Share

Metrics

Record views

22