Tri-partitions and Bases of an Ordered Complex
- PDF / 712,473 Bytes
- 17 Pages / 439.37 x 666.142 pts Page_size
- 8 Downloads / 150 Views
Tri-partitions and Bases of an Ordered Complex Herbert Edelsbrunner1 · Katharina Ölsböck1 Received: 4 March 2019 / Revised: 10 December 2019 / Accepted: 17 February 2020 © The Author(s) 2020
Abstract Generalizing the decomposition of a connected planar graph into a tree and a dual tree, we prove a combinatorial analog of the classic Helmholtz–Hodge decomposition of a smooth vector field. Specifically, we show that for every polyhedral complex, K , and every dimension, p, there is a partition of the set of p-cells into a maximal p-tree, a maximal p-cotree, and a collection of p-cells whose cardinality is the p-th reduced Betti number of K . Given an ordering of the p-cells, this tri-partition is unique, and it can be computed by a matrix reduction algorithm that also constructs canonical bases of cycle and boundary groups. Keywords Polyhedral complexes · Homology and cohomology · Trees and cotrees · Matrix reduction · Tri-partitions · Bases
1 Introduction Given a connected graph embedded on the sphere, it is well known that we can split the graph into a spanning tree and a dual tree whose nodes are the faces. This is best visualized by rotating each edge that is not in the spanning tree, thus connecting the two points chosen to represent the incident faces. This split is similar in spirit to the Helmholtz decomposition of a smooth vector field on the sphere into a rotation-
Dedicated to the memory of Ricky Pollack. Editor in Charge: János Pach This project has received funding from the European Research Council under the European Union’s Horizon 2020 research and innovation programme (Grant Agreement No. 78818 Alpha). It is also partially supported by the DFG Collaborative Research Center TRR 109, ‘Discretization in Geometry and Dynamics’, through Grant No. I02979-N35 of the Austrian Science Fund (FWF). Herbert Edelsbrunner [email protected] Katharina Ölsböck [email protected] 1
IST Austria (Institute of Science and Technology Austria), Klosterneuburg, Austria
123
Discrete & Computational Geometry
free component and a divergence-free component [12]. If the graph is embedded on a surface with non-zero genus, then the split does not exhaust all edges and the unused ones correspond to the third, harmonic component of the Helmholtz–Hodge decomposition on this surface [13]. Thinking of this split as a theorem about the edges of a connected planar graph, we are interested in its generalization to complexes and to cells of any dimension. Such a generalization promises a geometric interpretation of algebraic concepts in homology and their relations. Beyond this theoretical interest in the structure of complexes, we are motivated by geometric modeling tasks in which holes are of central importance. An example are cell membrane proteins with functional channels for ion transport. We believe that our structural results can be helpful in discovering and manipulating hole systems, but this is the topic of future work. 1.1 Two Examples Our results are combinatorial and algorithmic. To get a first impression, con
Data Loading...
