Spatially Constrained Partitioning for Contiguous Regions

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 2118 papers169 conceptsfrozen 2026-10-04

In many data science problems, we want to group similar items together. Standard clustering algorithms like K-means or Spectral Clustering excel at this by minimizing the distance between points in a feature space. However, when these algorithms are applied to physical data—such as geographic regions, brain voxels, or image pixels—they often produce "islands." These are clusters of points that are mathematically similar but physically scattered across a map.

In the real world, an "island" is often a failure. A police beat that consists of three disconnected neighborhoods is impossible to patrol; a school district with a detached enclave is a logistical nightmare; and a functional "region" of the brain that is scattered across non-adjacent neurons contradicts our understanding of biological organization.

To solve this, researchers have developed a suite of techniques for spatially constrained partitioning. The goal is to ensure that every cluster is not just similar, but contiguous—forming a single, unbroken shape.

The Problem of Fragmentation

Traditional clustering treats data points as independent entities in a vacuum. If two points have similar attributes, they belong together. But as Philip J. Cowans and Martin Szummer argue in A Graphical Model for Simultaneous Partitioning and Labeling, many real-world structures require grouped elements to be internally connected. Without enforcing this "contiguity constraint," models produce physically impossible groupings.

This "fragment problem" appears across disciplines:

Mechanism 1: Graph-Based Connectivity

The most common way to enforce contiguity is to treat the spatial area as a graph. Each unit (a census tract, a pixel, or a brain voxel) is a node, and edges exist only between adjacent units.

In this framing, a "contiguous cluster" is defined as a connected subgraph. During the optimization process, the algorithm is forbidden from moving a node to a cluster if that move would break the cluster's connectivity. Subhodip Biswas implements this in GeoKmeans by performing graph-based connectivity checks during every iterative reassignment. If a proposed change creates a "disconnected island," the move is rejected.

Mechanism 2: Flow-Based Constraints

For more complex optimization problems, such as designing police beats or school districts, researchers use flow-based formulations. Imagine each cluster has a "source" (like a police station or a school). To ensure the entire district is contiguous, the model requires that every unit in the district must be able to "send a flow" back to that source through other units in the same district.

Shixiang Zhu and Yao Xie used this approach in Data-Driven Optimization for Police Beat Design to ensure beats were operationally practical. Similarly, Hitoshi Shimizu applied flow constraints in School Families to ensure that elementary school districts were neatly and contiguously nested within junior high districts.

Mechanism 3: Distance-Dependent Priors

In probabilistic modeling, contiguity can be baked into the "prior" of the model. Instead of a standard clustering process where any point can join any group, researchers like Diane M. Beck and Gal Varoquaux use a distance-dependent Chinese Restaurant Process (dd-CRP).

In a dd-CRP, each data point "links" to a nearby neighbor. The clusters are then defined as the connected components formed by these links. Because links are only allowed between neighbors, the resulting partitions are spatially contiguous by construction. This approach is particularly effective for brain parcellation, where it identifies biologically plausible modules that respect the brain's physical layout.

Why Connectivity Helps Optimization

While adding constraints usually makes a problem harder to solve, connectivity can actually be a "powerful tool for pruning search trees," according to Christopher Hojny and Martin Schmidt.

In Mixed-integer programming techniques for the connected max-k-cut problem, they show that the requirement for connectivity allows an optimizer to immediately discard vast regions of the search space. If a partial solution is already disconnected, any further additions to it will also be invalid. By treating connectivity as a hard structural requirement rather than a "nuisance" to be fixed later, these algorithms can solve massive spatial problems—like defining electricity price zones or urban road sub-regions—with provable optimality.

The Balancing Act

The core challenge in this field remains the trade-off between homogeneity (how similar the points in a cluster are) and contiguity (how well-shaped the cluster is).

As Yunlei Liang and Song Gao demonstrate with Region2Vec, the most effective modern approaches use a "double-enforcement" strategy. They incorporate spatial information during the representation learning phase (ensuring the "features" themselves know about their neighbors) and again during the clustering phase (ensuring the final boundaries are unbroken). This ensures that the resulting regions are not just mathematically convenient, but geographically and operationally sensible.

Papers in this version

Showing 60 of 118 papers.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 103 papers
  2. Version 1 · 2026-10-04 · 118 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_spatial_connectivity_constraints_topolog_4c1c2805,
  title = {spatial connectivity constraints (topology-constrained clustering)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/spatial-connectivity-constraints-topology-constrained-clustering/rdr_4c1c28058da947e4af4013bb13442333},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_spatially_constrained_partitioning_for_c_4c1c2805_v1,
  title = {Spatially Constrained Partitioning for Contiguous Regions},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/spatially-constrained-partitioning-for-contiguous-regions/rdr_4c1c28058da947e4af4013bb13442333/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}