Computational Properties of Qualitative Spatial and Temporal Calculi
From QUAIL
[edit]
Table
This is a list of spatial and temporal calculi in alphabetical order:
| Name | Domain | No. of Base Relations | NP-Hard | a-closure decide consistency for atomic networks | Extensional | Tractable Subsets |
|---|---|---|---|---|---|---|
| Allens Interval | 1D Line Segments | 13 | yes | yes | yes | ORDHorn |
| rectangle calculus | rectangles | 169 | ||||
| Closed Disk Algebra | 2D Closed Disks | 8 | yes | no | yes | |
| LR Calculus | Points | 9 | yes | no | ||
| Dipole Calculus DRAc | Directions from Line Segments | 24 | ||||
| Dipole Calculus DRAf | Directions from Line Segments | 72 | ||||
| Dipole Calculus DRAfp | Directions from Line Segments | 80 | ||||
| OPRA1 | Oriented Points | 20 | ||||
| OPRAm | Oriented Points | 4m*(4m+1) | ||||
| Single Cross Calculus | Points | 8 | ||||
| Double Cross Calculus | Points | 15 | ||||
| Nine-Intersection Model | Simple 2D Regions | 8 | no | yes | ||
| Point Algebra | Points along a line | 3 | yes | yes | yes | all |
| RCC5 | General 2D Regions | 5 | yes | yes | no | n.a. |
| RCC8 | General 2D Regions | 8 | yes [1] | yes [2] | No | H^8, C8, Q8 |
| RCC23 | General 2D Concave Regions | 23 | ||||
| Star Algebra | Directions from a point | |||||
| INDU | 1D-Line Segments + Size | 25 | ||||
| Cardinal direction calculus | Directions | |||||
| Qualitative trajectory calculus QTC-B11 | Moving Point Objects in 1D | 9 | ||||
| Qualitative trajectory calculus QTC-B21 | Moving Point Objects in 2D | 9 | ||||
| Qualitative trajectory calculus QTC-B12 | Moving Point Objects in 1D | 17 | ||||
| Qualitative trajectory calculus QTC-B22 | Moving Point Objects in 2D | 27 | ||||
| Qualitative trajectory calculus QTC-C21 | Moving Point Objects in 2D | 81 | ||||
| Qualitative trajectory calculus QTC-C22 | Moving Point Objects in 2D | 305 | ||||
| Qualitative trajectory calculus QTC-N | Moving Point Objects in a network | 17 | ||||
| TPCC | Points | 25 | ||||
| CYC-t | oriented lines | 24 | yes |
[edit]
References
- ↑ "J. Renz and B. Nebel." On the complexity of qualitative spatial reasoning: A maximal tractable fragment of the Region Connection Calculus. AIJ, 108:69–123, 1999.
- ↑ "B. Nebel and H-J. Burckert ."Reasoning about temporal relations: a maximal tractable subset of Allen’s interval algebra. J. ACM, 42(1):43-66, 1995.
