Qualitative Spatial Logic over 2D Euclidean Spaces Is Not Finitely Axiomatisable

Heshan Du, Natasha AlechinaAAAI 2019 · DOI

Abstract

Qualitative spatial logics such as LNF, LNFS, and LBPT are essential for reasoning about proximity in geospatial datasets. While these logics are well-understood in the context of general metric spaces, their application to 2D Euclidean space—the standard model for maps—presents unique challenges. This paper demonstrates that the rigid geometric constraints of the 2D plane prevent these logics from being captured by any finite set of axioms. We prove that an infinite number of independent axioms are required to fully characterize 2D spatial relationships, although the satisfiability problem for LNF remains decidable in PSPACE.

Introduction

In the field of geospatial information systems (GIS), merging disparate datasets often leads to logical inconsistencies. Qualitative spatial logics provide a formal framework to identify these errors by reasoning about "nearness" and "farness." For instance, if one dataset places two landmarks within a specific distance threshold (NEAR) and another places them beyond it (FAR), a contradiction is flagged.

Previous research successfully established sound and complete axiomatisations for these logics over general metric spaces. However, most practical applications occur within 2D Euclidean space. The transition from abstract metric spaces to the 2D plane introduces significant geometric restrictions that the existing logical rules do not account for. This research investigates whether a finite set of additional rules can bridge this gap.

The Euclidean Gap: The Kissing Number Problem

The fundamental difficulty in axiomatising 2D space lies in its inherent "packing" limits. In a general metric space, one can theoretically place an arbitrary number of points equidistant from a central point such that they are all "FAR" from each other. In 2D Euclidean space, this is physically impossible.

A classic example is the "kissing number": in two dimensions, you can only fit exactly six non-overlapping circles of the same radius around a central circle of that same radius. If a logical statement describes a central point "NEAR" to seven other points, where those seven are all "FAR" from each other, that statement is logically consistent in a general metric space but impossible to realize on a 2D map.

Methodology: Unit Disk Graphs and Infinite Forbidden Subgraphs

To prove that no finite set of axioms can capture these 2D constraints, the authors utilize a combination of geometry and graph theory.

Unit Disk Graphs (UDGs)

The researchers draw a parallel between spatial logic and Unit Disk Graphs. A UDG is a graph where an edge exists between two vertices if and only if the distance between them is less than or equal to a fixed threshold. The problem of determining if a set of spatial constraints is "realizable" in 2D is essentially the problem of determining if a graph can be represented as a UDG.

Independence Proofs

By leveraging recent mathematical findings regarding UDGs, the authors show that there are an infinite number of "minimal forbidden subgraphs"—configurations that cannot exist in 2D. Because these forbidden configurations can be arbitrarily large and complex, no finite list of rules can ever exclude all of them. For any integer $k$, the authors demonstrate a unique geometric constraint (Axiom $A_k$) that is independent of all other axioms, proving that the logic requires an infinite chain of requirements for completeness.

Computational Complexity and Decidability

Despite the impossibility of a finite axiomatisation, the logic is not computationally hopeless. The authors reduced the satisfiability problem of LNF in 2D Euclidean space to the existential theory of the reals.

  1. Decidability: The problem is proven to be decidable in PSPACE. This means that while we cannot list all the rules, we can still compute whether a specific set of spatial statements is possible in 2D.
  2. Practical Performance: To test the real-world utility of this decidability, the authors employed general-purpose algebraic solvers like Redlog and QEPCAD B. The results were sobering: even simple formulas involving only three named entities could take upwards of ten minutes to resolve. This suggests a significant "practicality gap" between theoretical decidability and actual geospatial debugging.

Conclusion and Future Work

This research establishes a definitive theoretical boundary: qualitative spatial logics over 2D Euclidean spaces are not finitely axiomatisable. The infinite complexity of 2D geometric packing means that our logical systems must either remain incomplete or rely on computational methods rather than fixed rule sets.

Future work will focus on improving the efficiency of these reasoning mechanisms. The authors suggest that specialized geometric algorithms may outperform general algebraic solvers. Additionally, there are plans to extend the logic to include directional primitives (e.g., "North of," "Left of"), which would further enhance the utility of these frameworks for practical geospatial applications.

Summary updated

BibTeX
@inproceedings{du2019qualitative,
  author = {Heshan Du and Natasha Alechina},
  title = {{Qualitative Spatial Logic over 2D Euclidean Spaces Is Not Finitely Axiomatisable}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.1609/aaai.v33i01.33012776},
}
Figure