文章基本信息

标题：Computational complexity of spatial reasoning with directional relationship
本地全文：下载
作者：Mao Jianhua ; Guo Qingsheng ; Wang Tao 等
期刊名称：Geo-spatial Information Science
印刷版ISSN：1009-5020
电子版ISSN：1993-5153
出版年度：2002
卷号：5
期号：3
页码：53-57
DOI：10.1007/BF02826389
出版社：Taylor and Francis Ltd
摘要：The property of NP-completeness of topologic spatial reasoning problem has been proved. According to the similarity of uncertainty with topologic spatial reasoning, the problem of directional spatial reasoning should be also an NP-complete problem. The proof for the property of NP-completeness in directional spatial reasoning problem is based on two important transformations. After these transformations, a spatial configuration has been constructed based on directional constraints, and the property of NP-completeness in directional spatial reasoning has been proved with the help of the consistency of the constraints in the configuration.
关键词：computational complexity; NP-completeness; directional reasoning