On Point-Based Temporal Disjointness

We address the problems of determining consistency and of findinga solution for sets of 3-point relations expressing exclusion of a pointfrom an interval, and for sets of 4-point relations expressing interval disjointness.Availability of these relations is an important requirement fordealing with the sorts of temporal constraints encountered in many AIapplications such as plan reasoning. We prove that consistency testingis NP-complete