3D geo-graphs: Efficient flip verification for the spherical zoning problem

The Spherical Zoning Problem (SZP) seeks to partition a finite 3D volume comprised of convex polytope cells, or units, into k zones such that each zone's surface is spherical (i.e., homeomorphic to a sphere). A special case of the classical Connected Graph Partition Problem, SZP is motivated by applications in 3D geospatial partitioning such as airspace sectorization and oceanographic clustering. For general graph partitioning problems, local search optimization often considers the flip operation, which transfers one cell from its current zone, or part, to a neighboring zone in each iteration. Applying local search optimization to SZP requires new computational methods to assess flip feasibility; methods tailored to planar graph partitioning (e.g., for geographic districting) break down when faced with the spherical zones constraint due to inherent complexities when extending from 2D to 3D environments. This paper introduces the 3D geo-graph, a model for enforcing zone sphericity during a local search flip for solving SZP. The time complexity of SZP flip verification with the 3D geo-graph is, in the worst case, linear in the number of cells sharing some boundary with the flipped cell and linearithmic in the number of faces, edges, and vertices on the cell's surface. Computational experiments on space-filling honeycombs demonstrate that the 3D geo-graph enables efficient flip verification for large-scale SZP instances.