---
_id: '7666'
abstract:
- lang: eng
  text: 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.
acknowledgement: 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).
article_processing_charge: Yes (via OA deal)
article_type: original
author:
- first_name: Herbert
  full_name: Edelsbrunner, Herbert
  id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
  last_name: Edelsbrunner
  orcid: 0000-0002-9823-6833
- first_name: Katharina
  full_name: Ölsböck, Katharina
  id: 4D4AA390-F248-11E8-B48F-1D18A9856A87
  last_name: Ölsböck
  orcid: 0000-0002-4672-8297
citation:
  ama: Edelsbrunner H, Ölsböck K. Tri-partitions and bases of an ordered complex.
    <i>Discrete and Computational Geometry</i>. 2020;64:759-775. doi:<a href="https://doi.org/10.1007/s00454-020-00188-x">10.1007/s00454-020-00188-x</a>
  apa: Edelsbrunner, H., &#38; Ölsböck, K. (2020). Tri-partitions and bases of an
    ordered complex. <i>Discrete and Computational Geometry</i>. Springer Nature.
    <a href="https://doi.org/10.1007/s00454-020-00188-x">https://doi.org/10.1007/s00454-020-00188-x</a>
  chicago: Edelsbrunner, Herbert, and Katharina Ölsböck. “Tri-Partitions and Bases
    of an Ordered Complex.” <i>Discrete and Computational Geometry</i>. Springer Nature,
    2020. <a href="https://doi.org/10.1007/s00454-020-00188-x">https://doi.org/10.1007/s00454-020-00188-x</a>.
  ieee: H. Edelsbrunner and K. Ölsböck, “Tri-partitions and bases of an ordered complex,”
    <i>Discrete and Computational Geometry</i>, vol. 64. Springer Nature, pp. 759–775,
    2020.
  ista: Edelsbrunner H, Ölsböck K. 2020. Tri-partitions and bases of an ordered complex.
    Discrete and Computational Geometry. 64, 759–775.
  mla: Edelsbrunner, Herbert, and Katharina Ölsböck. “Tri-Partitions and Bases of
    an Ordered Complex.” <i>Discrete and Computational Geometry</i>, vol. 64, Springer
    Nature, 2020, pp. 759–75, doi:<a href="https://doi.org/10.1007/s00454-020-00188-x">10.1007/s00454-020-00188-x</a>.
  short: H. Edelsbrunner, K. Ölsböck, Discrete and Computational Geometry 64 (2020)
    759–775.
corr_author: '1'
date_created: 2020-04-19T22:00:56Z
date_published: 2020-03-20T00:00:00Z
date_updated: 2025-04-14T07:48:36Z
day: '20'
ddc:
- '510'
department:
- _id: HeEd
doi: 10.1007/s00454-020-00188-x
ec_funded: 1
external_id:
  isi:
  - '000520918800001'
file:
- access_level: open_access
  checksum: f8cc96e497f00c38340b5dafe0cb91d7
  content_type: application/pdf
  creator: dernst
  date_created: 2020-11-20T13:22:21Z
  date_updated: 2020-11-20T13:22:21Z
  file_id: '8786'
  file_name: 2020_DiscreteCompGeo_Edelsbrunner.pdf
  file_size: 701673
  relation: main_file
  success: 1
file_date_updated: 2020-11-20T13:22:21Z
has_accepted_license: '1'
intvolume: '        64'
isi: 1
language:
- iso: eng
license: https://creativecommons.org/licenses/by/4.0/
month: '03'
oa: 1
oa_version: Published Version
page: 759-775
project:
- _id: B67AFEDC-15C9-11EA-A837-991A96BB2854
  name: IST Austria Open Access Fund
- _id: 266A2E9E-B435-11E9-9278-68D0E5697425
  call_identifier: H2020
  grant_number: '788183'
  name: Alpha Shape Theory Extended
- _id: 2561EBF4-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: I02979-N35
  name: Persistence and stability of geometric complexes
publication: Discrete and Computational Geometry
publication_identifier:
  eissn:
  - '14320444'
  issn:
  - '01795376'
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Tri-partitions and bases of an ordered complex
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 64
year: '2020'
...