|
|||||
|
|
Computational complexity of spatial reasoning with directional relationship |
|
| Authors: | |
| Institution: | (1) School of Resource and Environment Science, Wuhan University, 129 Luoyu Road, 430079 Wuhan, China |
| Abstract: | The property of NPcompleteness 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 NPcomplete problem.The proof for the property of NPcompleteness 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 NPcompleteness in directional spatial reasoning has been proved with the help of the consistency of the constraints in the configuration. |
| Keywords: | computational complexity NPcompleteness directional reasoning |
| 本文献已被 CNKI 维普 万方数据 SpringerLink 等数据库收录！ | |