Abstract

This work introduces a novel model for representing polygons in a discrete space utilizing compact data structures. This representation facilitates the computation of topological relationships as defined by the 9-Intersection Model (9IM), encompassing relations such as overlap, touches, and equals.Within our proposed framework, a polygon is represented by its boundary, specifically by the set of discrete cells intersected by its edges, its interior and its exterior. To efficiently store those sets, we designed and implemented a compact data structure. This structure is an extension of the k2-tree compact data structure, upon which the topological relationship computations are performed.To evaluate the performance of our framework, we conducted a series of experiments comparing it against the computational geometry library GEOS. These experiments utilized polygons representing the territorial organization of Chile (regions and communes). Preliminary results indicate that our proposed approach is efficient in speed compared to the GEOS implementation. © 2025 IEEE.