Computational complexity of spatial reasoning with directional relationship |
| |
| Authors: | Mao Jianhua Guo Qingsheng Wang Tao |
| |
| Institution: | School of Resource and Environment Science , Wuhan University , Wuhan , China |
| |
| Abstract: | 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. |
| |
| Keywords: | computational complexity NP-completeness directional reasoning |
|
|
