Nine-Intersection Model

Origin. Max Egenhofer and Robert Franzosa, "Point-set topological spatial relations" (International Journal of Geographical Information Systems 5(2), 1991), defined binary topological relations by the four intersections of two regions' interiors and boundaries; Egenhofer and John Herring, "Categorizing binary topological relations between regions, lines, and points in geographic databases" (technical report, University of Maine, 1991 — circulated from 1990 and cited inconsistently ever since), added the exteriors, giving the 9-intersection. Eliseo Clementini, Paolino Di Felice, and Peter van Oosterom ("A small set of formal topological relationships suitable for end-user interaction", SSD 1993) recorded the dimension of each intersection, and the resulting DE-9IM became the OGC and ISO standard predicate model. Egenhofer and Khaled Al-Taha ("Reasoning about gradual changes of topological relationships", 1992) built the conceptual neighborhood graph; Egenhofer ("Deriving the composition of binary topological relations", Journal of Visual Languages and Computing 5(2), 1994) derived the composition table.

Models. A topological relation between two point sets is read off from which of their parts meet: each object splits into interior, boundary, and exterior — mutually exclusive, jointly covering the space — and the relation is the 3×3 matrix recording which of the nine pairwise intersections are empty. The foundation is the opposite of the Region Connection Calculus's: RCC axiomatizes a connection primitive over regions as first-class individuals and asks which models satisfy a network, while the 9-intersection computes relations of subsets of a topological space, so boundaries and points are available from the start and realizability is a theorem about ℝ² rather than a model-existence question. For regions without holes in ℝ² exactly eight matrices are realizable, and they are RCC-8's eight relations under other names.

Formalism.

4-intersection (Egenhofer–Franzosa 1991): The 2×2 matrix of A° ∩ B°, A° ∩ ∂B, ∂A ∩ B°, ∂A ∩ ∂B, each marked empty or non-empty. 2⁴ = 16 candidates; 8 realizable between regions in ℝ². Sufficient for region–region; too coarse for lines — it distinguishes only 16 line–line and 11 region–line relations.

9-intersection (Egenhofer–Herring 1991):

R(A, B) = A° ∩ B° A° ∩ ∂B A° ∩ B⁻ ∂A ∩ B° ∂A ∩ ∂B ∂A ∩ B⁻ A⁻ ∩ B° A⁻ ∩ ∂B A⁻ ∩ B⁻

Each entry empty (∅) or non-empty (¬∅): 2⁹ = 512 candidate relations. Realizability in ℝ² is settled by eliminating matrices against topological conditions and exhibiting prototypes for the remainder.

The eight region–region relations: disjoint, meet, overlap, equal, inside, contains, covers, coveredBy. Jointly exhaustive and pairwise disjoint for simple regions in ℝ². RCC-8 correspondence: disjoint = DC, meet = EC, overlap = PO, equal = EQ, inside = NTPP, contains = NTPPi, coveredBy = TPP, covers = TPPi.

Realizable relations by object type (Egenhofer–Herring): Region–region: 8; 18 if regions may have holes (disconnected boundaries). Line–line: 33 for simple lines; 57 with complex lines. Region–line: 19 for simple lines; 20 with non-simple lines. Point–region and point–line: 3 each. Point–point: 2 — disjoint and equal. Regions are 2-complexes with connected non-empty interior; lines are non-looping, non-crossing 1-complexes.

DE-9IM (Clementini–Di Felice–van Oosterom 1993): Entries record the dimension of each intersection — F for empty, else 0, 1, or 2 — instead of bare emptiness. A predicate is a mask over the nine entries: T for non-empty, F for empty, a wildcard for either. OGC Simple Features / ISO SQL: equals, disjoint, intersects, touches, crosses, within, contains, overlaps; ST_Relate exposes the raw matrix (PostGIS, through GEOS).

Composition (Egenhofer 1994): 8 × 8 table; each entry a disjunction of possible relations. Constraint networks over disjunctive labels; path consistency as the propagation step — the machinery of the qualitative calculi.

Conceptual neighborhoods (Egenhofer–Al-Taha 1992): Two relations are neighbors when a continuous deformation passes from one to the other without visiting a third. Topological distance: the number of matrix entries on which two relations differ. The neighborhood graph is the path gradual change must walk.

Symbols.

Metatheory. Egenhofer and Herring's categorization is exhaustive by construction: topological conditions — the Jordan curve theorem, dimension and codimension of the parts — eliminate candidate matrices, and prototype configurations verify every survivor, so the counts (8 and 18 for regions, 33 and 57 for lines, 19 and 20 for region–line, 3 and 2 for the point cases) are theorems about ℝ² under the stated object definitions. For regions in ℝ² the 4-intersection and the 9-intersection distinguish the same eight relations — the exteriors add nothing at codimension 0 — while for lines the exteriors are what separate 33 relations from the 4-intersection's 16. The eight region relations correspond one-to-one with RCC-8's base relations, so the constraint language is shared: Egenhofer's 1994 composition table drives the same path-consistency propagation, and Renz and Nebel's complexity results — consistency of disjunctive networks NP-complete, three maximal tractable subclasses, recorded in the Region Connection Calculus entry — cover 9IM networks under the correspondence. The conceptual difference survives the coincidence: RCC proves a consistent network realizable in every ℝⁿ from first-order axioms about connection and cannot express whether a region is open or closed, while the 9-intersection fixes the space and the object class first, resolves open-versus-closed by fiat (cells contain their boundaries), and its relation sets move whenever the space or the object class moves.

Applies to. Spatial databases: the DE-9IM is the predicate model of the OGC Simple Features specification and the ISO SQL/MM spatial standard, implemented in PostGIS and GEOS as the named predicates and ST_Relate. GIS query languages. Qualitative spatial reasoning over topological constraint networks. Detecting qualitative change in spatio-temporal data, through topological distance and the neighborhood graph.

Limitations. The relation sets are indexed to the object class and the embedding space: holes move region–region from 8 relations to 18, non-simple lines move line–line from 33 to 57, and the report itself lists the embedding space among the sources of non-existence, so none of the counts transfer to other surfaces or dimensions without redoing the elimination. The content is emptiness (or dimension) of intersections and nothing else: size, shape, distance, and direction are invisible, configurations differing in every metric respect get the same matrix, and direction needs a separate calculus (Cardinal Direction Calculi). The model classifies rather than axiomatizes — there is no proof theory, composition entries are justified by prototypes and conditions, and consistency reasoning is borrowed constraint machinery that is NP-complete in general. And the matrices describe states only: motion and deformation enter through the conceptual neighborhood graph, which sits outside the model.

© 2026 Lingenic LLC