Topological Graph Representations of Indoor Spaces

12 concepts11 papers1 proposal

In outdoor navigation, spatial data management is largely a solved problem. Continuous coordinate systems, driven by GPS, allow us to calculate distances, track movements, and find optimal paths using simple Euclidean geometry. However, once we step inside a building, this geometric paradigm breaks down.

Indoors, physical barriers like walls, doors, and multi-level floors dictate human experience and movement. Two points separated by a single brick wall might be mere centimeters apart in Euclidean space, yet walking from one to the other could require traversing an entire hallway, passing through multiple doors, and walking dozens of meters.

To capture the reality of indoor environments, researchers have shifted away from continuous geometric coordinates toward topological graph representations. By modeling indoor spaces as graphs—where nodes represent discrete spatial zones and edges represent physical connections—algorithms can reason about reachability, proximity, and architectural intent far more effectively than they could with raw coordinates alone.


The Core Abstraction: From Coordinates to Connectivity

The fundamental insight behind this research direction is that indoor space is inherently discrete and bounded. Instead of defining a location as a latitude and longitude, a topological model defines it symbolically: a person is in "Room 302" or "Hallway B."

Continuous Geometry (Euclidean)       Topological Graph (Symbolic)
       ┌───────────────┐                     ┌────────┐        ┌────────┐
       │    Room A     │                     │ Room A │────────│ Room B │
       │       • (x1,y1)                      └────────┘        └────────┘
       ├─────── ───────┤                                    │
       │       • (x2,y2)                                    │
       │    Room B     │                                ┌────────┐
       └───────────────┘                                │ Hallway│
                                                        └────────┘

In its simplest form, this graph structure maps the architectural layout directly:

  • Vertices ($V$): Represent discrete, convex subareas, rooms, or functional zones.
  • Edges ($E$): Represent traversable thresholds, such as doorways, stairs, or open boundaries.

As Christian S. Jensen argues in a foundational piece, this transition to symbolic, graph-based models is essential because indoor movement is fundamentally constrained by architectural boundaries. Treating indoor space as a network of connected cells ensures that computational models respect physical realities.


Why It Works: The Power of Topological Priors

Representing indoor spaces as graphs provides two major advantages: it acts as a powerful constraint for filtering noisy real-world data, and it provides a flexible framework for structural pattern matching.

1. Constraining Movement and Cleaning Noisy Data

Indoor positioning technologies (such as WiFi fingerprinting, Bluetooth beacons, or RFID) are notoriously noisy and uncertain. If a system relies purely on geometric coordinates, a fluctuating signal might make it appear as though a user is teleporting through a solid wall.

By overlaying trajectories onto a topological graph, the system gains an architectural "prior." As Jensen et al. demonstrate, when movement is constrained to valid edges within a graph, spatial queries like $k$-nearest neighbor searches reflect actual walking distances rather than straight-line paths.

This constraint is particularly valuable when dealing with highly uncertain data. For instance, Li et al. show that treating building context (walls and doors) as prior knowledge allows systems to clean up positioning errors and fill in gaps left by low-frequency sensors.

When applied to contact tracing, this model prevents false positives. In two closely related works, Liu et al. (2023) and Liu et al. (2024) utilize an indoor-aware graph model where each vertex maintains an intra-partition distance matrix and a time-bucketed table. Because the graph explicitly accounts for physical partitions, the system can immediately rule out prolonged contact between individuals who are close in straight-line distance but separated by an impenetrable wall.

   Person X (Room A)  ───[ Wall ]───  Person Y (Room B)

   Euclidean Distance: 1.5 meters  -> High Risk? (False Positive)
   Topological Distance: 24 meters -> Safe (Correct)

Furthermore, this structural mapping simplifies the localization problem itself. Instead of calculating exact coordinates, Chen et al. introduce a "zero-configuration" localization system called GraphLoc. By converting both the physical floor plan and crowdsourced WiFi signal traces into graphs, they transform the task of subarea localization into a graph isomorphism problem, matching signal topologies to spatial topologies without requiring labor-intensive manual site surveys.

2. Abstracting Design Intent from Geometry

The utility of topological graphs extends beyond tracking moving objects; it also transforms how we analyze and generate architectural designs. When an architect designs a building, they rarely start with precise millimeter measurements. Instead, they begin with functional relationships: the kitchen should be adjacent to the dining room; the master bedroom needs direct access to a bathroom.

Topological graphs capture this underlying design logic independently of final geometric dimensions. This abstraction enables advanced architectural search engines. Langenhan et al. (2011) and Weber et al. developed systems that convert complex Building Information Models (BIM) and rough hand-drawn sketches into hierarchical ontological graphs, or "semantic fingerprints."

Architect's Sketch ──> Graph Abstraction ──> Graph Matching ──> Database Retrieval
 [Bed]─[Bath]          (Node: Bed)          (Sub-graph          (Finds matching
   │                    └──Edge──>(Bath)     Isomorphism)        past floorplans)
 [Living]

Because these fingerprints organize spatial units into hierarchies of rooms, zones, and units, users can retrieve past design precedents simply by sketching a rough layout on a digital interface. The system matches the topology of the sketch against a repository, finding structurally similar designs even if their exact dimensions differ.

This graph-based abstraction also powers modern generative design and evaluation tools:

  • Interactive Generation: Hu et al. developed Graph2Plan, a deep learning framework that takes user-defined layout graphs (specifying room counts and adjacencies) and automatically generates vectorized floorplans. This turns automated layout generation into an interactive process where the user controls the topology while the machine optimizes the geometry.
  • Predictive AI Assistance: Langenhan et al. (2023) scale this concept to knowledge graphs, enabling an "auto-complete" functionality for architectural design. By training AI models on topological connectivity, the system can suggest design solutions and predict spatial relationships during the early stages of a project when data is still incomplete.
  • Evaluating Subjective Quality: Beyond generation, graphs help evaluate how a space feels. Yamasaki demonstrates that combining topological graph features (representing room transitions) with raw visual data allows machine learning models to quantify subjective human impressions, such as the comfort or functionality of a floor plan layout.

Conclusion

Whether the goal is to track an individual's path through a crowded shopping mall or to synthesize a brand-new apartment layout, topological graph representations offer a unified solution to the challenges of indoor spatial data. By discarding absolute Euclidean coordinates in favor of relational, symbolic connectivity, these models align computational logic with the physical and functional boundaries that define how humans actually navigate and design the built world.

Key Foundational Work

Indoor - A New Data Management Frontier (2010) — contributed 2 concept elements to this direction.
The Great Indoors: A Data Management Frontier (2010) — contributed 2 concept elements to this direction.
Investigating research strategies for accessing knowledge stored in semantic models (2011) — contributed 2 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_topological_indoor_representation_84164b29,
  title = {topological indoor representation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/topological-indoor-representation/rdr_84164b299c84499290c5b6c28a79a264},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_topological_indoor_representation_84164b29_v1,
  title = {topological indoor representation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/topological-indoor-representation/rdr_84164b299c84499290c5b6c28a79a264/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake