Cubical complex

In mathematics, a cubical complex (also called cubical set and Cartesian complex^[1]) is a set composed of points, line segments, squares, cubes, and their n-dimensional counterparts. They are used analogously to simplicial complexes and CW complexes in the computation of the homology of topological spaces. Non-positively curved and CAT(0) cube complexes appear with increasing significance in geometric group theory.

All graphs are (homeomorphic to) 1-dimensional cubical complexes.

Definitions

With regular cubes

A unit cube (often just called a cube) of dimension ${\displaystyle n\geq 0}$ is the metric space obtained as the finite (${\displaystyle l^{2}}$) cartesian product ${\displaystyle C_{n}=I^{n}}$ of ${\displaystyle n}$ copies of the unit interval ${\displaystyle I=[0,1]}$.

A face of a unit cube is a subset ${\displaystyle F\subset {C_{n}}}$ of the form ${\displaystyle F=\prod _{i=1}^{n}J_{i}}$, where for all ${\displaystyle 1\leq i\leq n}$, ${\displaystyle J_{i}}$ is either ${\displaystyle \{0\}}$, ${\displaystyle \{1\}}$, or ${\displaystyle [0,1]}$. The dimension of the face ${\displaystyle F}$ is the number of indices ${\displaystyle i}$ such that ${\displaystyle J_{i}=[0,1]}$; a face of dimension ${\displaystyle k}$, or ${\displaystyle k}$-face, is itself naturally a unit elementary cube of dimension ${\displaystyle k}$, and is sometimes called a subcube of ${\displaystyle F}$. One can also regard ${\textstyle \emptyset }$ as a face of dimension ${\textstyle -1}$.

A cubed complex is a metric polyhedral complex all of whose cells are unit cubes, i.e. it is the quotient of a disjoint union of copies of unit cubes under an equivalence relation generated by a set of isometric identifications of faces. One often reserves the term cubical complex, or cube complex, for such cubed complexes where no two faces of a same cube are identified, i.e. where the boundary of each cube is embedded, and the intersection of two cubes is a face in each cube.^[2]

A cube complex is said to be finite-dimensional if the dimension of the cubical cells is bounded. It is locally finite if every cube is contained in only finitely many cubes.

With irregular cubes

An elementary interval is a subset ${\displaystyle I\subsetneq \mathbf {R} }$ of the form

${\displaystyle I=[l,l+1]\quad {\text{or}}\quad I=[l,l]}$

for some ${\displaystyle l\in \mathbf {Z} }$. An elementary cube ${\displaystyle Q}$ is the finite product of elementary intervals, i.e.

${\displaystyle Q=I_{1}\times I_{2}\times \cdots \times I_{d}\subsetneq \mathbf {R} ^{d}}$

where ${\displaystyle I_{1},I_{2},\ldots ,I_{d}}$ are elementary intervals. Equivalently, an elementary cube is any translate of a unit cube ${\displaystyle [0,1]^{n}}$ embedded in Euclidean space ${\displaystyle \mathbf {R} ^{d}}$ (for some ${\displaystyle n,d\in \mathbf {N} \cup \{0\}}$ with ${\displaystyle n\leq d}$).^[3] A set ${\displaystyle X\subseteq \mathbf {R} ^{d}}$ is a cubical complex (or cubical set) if it can be written as a union of elementary cubes (or possibly, is homeomorphic to such a set).^[4]

Related terminology

Elementary intervals of length 0 (containing a single point) are called degenerate, while those of length 1 are nondegenerate. The dimension of a cube is the number of nondegenerate intervals in ${\displaystyle Q}$, denoted ${\displaystyle \dim Q}$. The dimension of a cubical complex ${\displaystyle X}$ is the largest dimension of any cube in ${\displaystyle X}$.

If ${\displaystyle Q}$ and ${\displaystyle P}$ are elementary cubes and ${\displaystyle Q\subseteq P}$, then ${\displaystyle Q}$ is a face of ${\displaystyle P}$. If ${\displaystyle Q}$ is a face of ${\displaystyle P}$ and ${\displaystyle Q\neq P}$, then ${\displaystyle Q}$ is a proper face of ${\displaystyle P}$. If ${\displaystyle Q}$ is a face of ${\displaystyle P}$ and ${\displaystyle \dim Q=\dim P-1}$, then ${\displaystyle Q}$ is a facet or primary face of ${\displaystyle P}$.

In algebraic topology

In algebraic topology, cubical complexes are often useful for concrete calculations. In particular, there is a definition of homology for cubical complexes that coincides with the singular homology, but is computable.

In geometric group theory

Groups acting geometrically by isometries on CAT(0) cube complexes provide a wide class of examples of CAT(0) groups.

The Sageev construction can be understood as a higher-dimensional generalization of Bass-Serre theory, where the trees are replaced by CAT(0) cube complexes.^[5] Work by Daniel Wise has provided foundational examples of cubulated groups.^[6] Agol's theorem that cubulated hyperbolic groups are virtually special has settled the hyperbolic virtually Haken conjecture, which was the only case left of this conjecture after Thurston's geometrization conjecture was proved by Perelman.^[7]

CAT(0) cube complexes

See also: Median graph

Gromov's theorem

Hyperplanes

CAT(0) cube complexes and group actions

The Sageev construction

RAAGs and RACGs

Applications

Cubical complexes have a wide range of applications across mathematics, computer science, robotics, and artificial intelligence. Their combinatorial and geometric structures provide powerful ways to model discrete configuration spaces and to apply tools from geometric group theory to practical problems.

One of the most developed areas of application is in robotics and motion planning, where cubical complexes are used to represent the configuration spaces of reconfigurable systems. The state complexes introduced by Abrams, Ghrist, and Peterson model all admissible configurations of modular robots as non-positively curved cube complexes, allowing the use of CAT(0) geometry to compute shortest paths and optimise reconfiguration strategies.^[8][9] Similar methods have been applied to the coordination of multiple robotic agents, yielding efficient algorithms for collision-free navigation and self-reconfiguration.^[10]

Cubical complexes have also recently been applied in artificial intelligence safety. A notable example is the work of Burns and Tang.^[11] This study builds on the Abrams–Ghrist–Peterson framework of state complexes to analyse multi-agent gridworld environments, which are commonly used in reinforcement learning research. Burns and Tang introduce a modified state complex incorporating “dances”, higher-dimensional cubes that encode independent or braided agent movements. This modification enables the intrinsic geometry of the complex to encode safety-critical information: by testing for failures of Gromov’s Link Condition, which detects positive curvature in a cube complex,^[12] they show that potential agent collisions correspond precisely to local violations of non-positive curvature. This provides a purely geometric method for identifying dangerous or undesirable states without the need for training data. In particular, collision detection reduces to checking simple combinatorial patterns in the links of vertices, offering computational shortcuts for real-time planning in multi-agent systems.

Other applications of cubical complexes include topological data analysis, where they serve as alternatives to simplicial complexes in persistent homology; geometric group theory, where CAT(0) cube complexes provide spaces for group actions;^[13] and combinatorics, where hyperplane structures of cube complexes can encode binary classification problems.^[14]

See also

• Mathematics portal

• Simplicial complex
• Simplicial homology
• Abstract cell complex

References

1. Kovalevsky, Vladimir. "Introduction to Digital Topology Lecture Notes". Archived from the original on 2020-02-23. Retrieved November 30, 2021.
2. Bridson, Martin R.; Haefliger, André (1999), Bridson, Martin R.; Haefliger, André (eds.), "Mκ—Polyhedral Complexes", Metric Spaces of Non-Positive Curvature, Berlin, Heidelberg: Springer, p. 115, doi:10.1007/978-3-662-12494-9_7, ISBN 978-3-662-12494-9, retrieved 2024-11-19
3. Werman, Michael; Wright, Matthew L. (2016-07-01). "Intrinsic Volumes of Random Cubical Complexes". Discrete & Computational Geometry. 56 (1): 93–113. arXiv:1402.5367. doi:10.1007/s00454-016-9789-z. ISSN 0179-5376.
4. Kaczynski, Tomasz; Mischaikow, Konstantin; Mrozek, Marian (2004). Computational Homology. New York: Springer. ISBN 9780387215976. OCLC 55897585.
5. Sageev, Michah (1995). "Ends of Group Pairs and Non-Positively Curved Cube Complexes". Proceedings of the London Mathematical Society. s3-71 (3): 585–617. doi:10.1112/plms/s3-71.3.585.
6. Daniel T. Wise, The structure of groups with a quasiconvex hierarchy, https://docs.google.com/file/d/0B45cNx80t5-2NTU0ZTdhMmItZTIxOS00ZGUyLWE0YzItNTEyYWFiMjczZmIz/edit?pli=1
7. Agol, Ian (2013). "The virtual Haken Conjecture". Doc. Math. 18. With an appendix by Ian Agol, Daniel Groves, and Jason Manning: 1045–1087. doi:10.4171/dm/421. MR 3104553. S2CID 255586740.
8. Abrams, Aaron; Ghrist, Robert (2004). "State Complexes for Metamorphic Robots". The International Journal of Robotics Research. 23 (7–8): 811–826. doi:10.1177/0278364904045468.
9. Ghrist, Robert; Peterson, V (2007). "The geometry and topology of reconfiguration". Advances in Applied Mathematics. 38 (3): 302–323. doi:10.1016/j.aam.2005.08.009.
10. Ardila, Federico; Baker, Tia; Yatchak, Rika (2014). "Moving robots efficiently using the combinatorics of CAT(0) cubical complexes". SIAM Journal on Discrete Mathematics. 28 (2): 986–1007. doi:10.1137/120898115.
11. Burns, Thomas F.; Tang, Robert (2023). "Detecting danger in gridworlds using Gromov's Link Condition". Transactions on Machine Learning Research. 2023: 1–23.
12. Gromov, Mikhail (1987). "Hyperbolic groups". Essays in Group Theory: 75–263. doi:10.1007/978-1-4613-9586-7_3.
13. Sageev, Michah (1995). "Ends of Group Pairs and Non-Positively Curved Cube Complexes". Proceedings of the London Mathematical Society. s3-71 (3): 585–617. doi:10.1112/plms/s3-71.3.585.
14. Chatterji, Indira; Niblo, Graham (2005). "From wall spaces to CAT(0) cube complexes". International Journal of Algebra and Computation. 15 (05n06): 875–885. doi:10.1142/S0218196705002669.