.png){kind=icon}
返回
Spatial reasoning about points in a multidimensional setting
.png){kind=icon}
PRE
AI
DOI：10.1023/A:1020079114666.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
For n greater than or equal to 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 greater than or equal to 1, whereas the consistency problem of preconvex n-point networks is NP-complete for n greater than or equal to 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 greater than or equal to 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.
Keyword:
spatial reasoning
constraint satisfaction problems
tractability
preconvexity
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
