A New Tractable Subclass of the Rectangle Algebra

Philippe Balbiani, Jean-François Condotta, Luis Fariñas del CerroIJCAI 1999

Abstract

Spatial reasoning in the Rectangle Algebra (RA) is generally NP-complete, posing a challenge for efficient computation in large-scale applications. This paper identifies a new, broader tractable subclass of spatial relations termed strongly-preconvex relations. By leveraging the properties of Allen’s Interval Algebra (IA) and defining convexity within an interval lattice, the authors demonstrate that the consistency of constraint networks within this subclass can be determined in polynomial time using the standard path-consistency algorithm. This work expands the known "safe zone" for efficient spatial reasoning in two dimensions.

Introduction: The Challenge of Spatial Reasoning

In Artificial Intelligence, spatial reasoning involves determining the physical possibility of a set of constraints between objects. For instance, if Rectangle A is to the left of B, and B overlaps C, can A also overlap C? While intuitive for humans, this becomes a complex Constraint Satisfaction Problem (CSP) as the number of objects and relation types increases.

For the Rectangle Algebra (RA)—which models 2D rectangles with axis-parallel sides—determining consistency is generally NP-complete. This exponential growth in computation time limits the practicality of RA in fields like Geographic Information Systems (GIS), CAD, and natural language understanding. To address this, researchers seek "tractable subclasses": subsets of relations where consistency can be solved in polynomial time.

Illustration of 2D rectangles X and Y in the Rectangle Algebra.

Methodology: Building on Interval Foundations

The authors base their approach on Allen’s Interval Algebra (IA), which describes relations between 1D time intervals. A 2D rectangle in RA is defined as the Cartesian product of two 1D intervals (one on the x-axis and one on the y-axis). Consequently, any RA relation is a pair of IA relations.

The thirteen basic relations of Allen's Interval Algebra.

The research follows several key steps:

  1. Defining Convexity: The authors utilize an "interval lattice" to define convex relations within the RA framework.
  2. Weak vs. Strong Preconvexity: They introduce "weakly-preconvex" relations based on the dimension of a relation's topological closure. They then define the "strongly-preconvex" class: a relation is strongly-preconvex if its intersection with any convex relation remains weakly-preconvex.
  3. Algorithmic Analysis: The study focuses on the path-consistency algorithm, a standard method for pruning impossible relations between triplets of objects. While typically a heuristic, the authors prove it is a definitive decision procedure for this new subclass.

Key Insights: Stability and Projections

A primary insight of this work is that a convex relation in 2D RA is simply the Cartesian product of two convex relations in 1D IA. This allows the authors to extend existing 1D proofs to the 2D domain.

Furthermore, the authors identified that "weakly-preconvex" relations, while stable under composition and inversion, lack stability under intersection. This instability typically breaks tractability. By defining "strongly-preconvex" relations to be stable when intersected with convex ones, the authors "patched" this logical gap, ensuring the path-consistency algorithm remains complete—meaning it will always find a solution if one exists.

This establishes a hierarchy: Saturated-Preconvex $\subset$ Strongly-Preconvex $\subset$ Weakly-Preconvex. By proving the tractability of the middle tier, the authors significantly expanded the known efficient subset of RA.

Results and Implications

The primary result is the characterization of the strongly-preconvex relations as a new tractable set in RA. Key findings include:

  • Algorithm Completeness: For spatial networks using only strongly-preconvex relations, the path-consistency algorithm is a complete decision method.
  • Expressiveness: This subclass includes all 169 atomic (basic) relations of the rectangle algebra, making it highly applicable for real-world modeling.
  • Efficiency: Reasoning within this subclass is computationally efficient, as the path-consistency algorithm runs in polynomial time ($O(n^3)$).

Limitations and Future Directions

While this is the largest known tractable subclass containing all atomic relations, it remains an open question whether it is the maximal possible subclass. Additionally, the current framework is limited to 2D axis-parallel rectangles. Future work may involve extending these concepts to $n$-dimensional hyper-rectangles or developing frameworks for rotated objects, which would require moving beyond the standard Rectangle Algebra.

Summary updated

BibTeX
@inproceedings{balbiani1999new,
  author = {Philippe Balbiani and Jean-François Condotta and Luis Fariñas del Cerro},
  title = {{A New Tractable Subclass of the Rectangle Algebra}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1999},
}
Figure