---
_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
fulldoi: https://doi.org/10.1007/s00454-020-00188-x
has_accepted_license: '1'
intvolume: '        64'
isi: 1
language:
- iso: eng
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'
...
---
_id: '7960'
abstract:
- lang: eng
  text: Let A={A1,…,An} be a family of sets in the plane. For 0≤i<n, denote by fi
    the number of subsets σ of {1,…,n} of cardinality i+1 that satisfy ⋂i∈σAi≠∅. Let
    k≥2 be an integer. We prove that if each k-wise and (k+1)-wise intersection of
    sets from A is empty, or a single point, or both open and path-connected, then
    fk+1=0 implies fk≤cfk−1 for some positive constant c depending only on k. Similarly,
    let b≥2, k>2b be integers. We prove that if each k-wise or (k+1)-wise intersection
    of sets from A has at most b path-connected components, which all are open, then
    fk+1=0 implies fk≤cfk−1 for some positive constant c depending only on b and k.
    These results also extend to two-dimensional compact surfaces.
acknowledgement: "We are very grateful to Pavel Paták for many helpful discussions
  and remarks. We also thank the referees for helpful comments, which greatly improved
  the presentation.\r\nThe project was supported by ERC Advanced Grant 320924. GK
  was also partially supported by NSF grant DMS1300120. The research stay of ZP at
  IST Austria is funded by the project CZ.02.2.69/0.0/0.0/17_050/0008466 Improvement
  of internationalization in the field of research and development at Charles University,
  through the support of quality projects MSCA-IF."
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Gil
  full_name: Kalai, Gil
  last_name: Kalai
- first_name: Zuzana
  full_name: Patakova, Zuzana
  id: 48B57058-F248-11E8-B48F-1D18A9856A87
  last_name: Patakova
  orcid: 0000-0002-3975-1683
citation:
  ama: Kalai G, Patakova Z. Intersection patterns of planar sets. <i>Discrete and
    Computational Geometry</i>. 2020;64:304-323. doi:<a href="https://doi.org/10.1007/s00454-020-00205-z">10.1007/s00454-020-00205-z</a>
  apa: Kalai, G., &#38; Patakova, Z. (2020). Intersection patterns of planar sets.
    <i>Discrete and Computational Geometry</i>. Springer Nature. <a href="https://doi.org/10.1007/s00454-020-00205-z">https://doi.org/10.1007/s00454-020-00205-z</a>
  chicago: Kalai, Gil, and Zuzana Patakova. “Intersection Patterns of Planar Sets.”
    <i>Discrete and Computational Geometry</i>. Springer Nature, 2020. <a href="https://doi.org/10.1007/s00454-020-00205-z">https://doi.org/10.1007/s00454-020-00205-z</a>.
  ieee: G. Kalai and Z. Patakova, “Intersection patterns of planar sets,” <i>Discrete
    and Computational Geometry</i>, vol. 64. Springer Nature, pp. 304–323, 2020.
  ista: Kalai G, Patakova Z. 2020. Intersection patterns of planar sets. Discrete
    and Computational Geometry. 64, 304–323.
  mla: Kalai, Gil, and Zuzana Patakova. “Intersection Patterns of Planar Sets.” <i>Discrete
    and Computational Geometry</i>, vol. 64, Springer Nature, 2020, pp. 304–23, doi:<a
    href="https://doi.org/10.1007/s00454-020-00205-z">10.1007/s00454-020-00205-z</a>.
  short: G. Kalai, Z. Patakova, Discrete and Computational Geometry 64 (2020) 304–323.
date_created: 2020-06-14T22:00:50Z
date_published: 2020-09-01T00:00:00Z
date_updated: 2023-08-21T08:26:34Z
day: '01'
department:
- _id: UlWa
doi: 10.1007/s00454-020-00205-z
external_id:
  arxiv:
  - '1907.00885'
  isi:
  - '000537329400001'
fulldoi: https://doi.org/10.1007/s00454-020-00205-z
intvolume: '        64'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1907.00885
month: '09'
oa: 1
oa_version: Preprint
page: 304-323
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: Intersection patterns of planar sets
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 64
year: '2020'
...
---
_id: '7962'
abstract:
- lang: eng
  text: 'A string graph is the intersection graph of a family of continuous arcs in
    the plane. The intersection graph of a family of plane convex sets is a string
    graph, but not all string graphs can be obtained in this way. We prove the following
    structure theorem conjectured by Janson and Uzzell: The vertex set of almost all
    string graphs on n vertices can be partitioned into five cliques such that some
    pair of them is not connected by any edge (n→∞). We also show that every graph
    with the above property is an intersection graph of plane convex sets. As a corollary,
    we obtain that almost all string graphs on n vertices are intersection graphs
    of plane convex sets.'
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: János
  full_name: Pach, János
  id: E62E3130-B088-11EA-B919-BF823C25FEA4
  last_name: Pach
- first_name: Bruce
  full_name: Reed, Bruce
  last_name: Reed
- first_name: Yelena
  full_name: Yuditsky, Yelena
  last_name: Yuditsky
citation:
  ama: Pach J, Reed B, Yuditsky Y. Almost all string graphs are intersection graphs
    of plane convex sets. <i>Discrete and Computational Geometry</i>. 2020;63(4):888-917.
    doi:<a href="https://doi.org/10.1007/s00454-020-00213-z">10.1007/s00454-020-00213-z</a>
  apa: Pach, J., Reed, B., &#38; Yuditsky, Y. (2020). Almost all string graphs are
    intersection graphs of plane convex sets. <i>Discrete and Computational Geometry</i>.
    Springer Nature. <a href="https://doi.org/10.1007/s00454-020-00213-z">https://doi.org/10.1007/s00454-020-00213-z</a>
  chicago: Pach, János, Bruce Reed, and Yelena Yuditsky. “Almost All String Graphs
    Are Intersection Graphs of Plane Convex Sets.” <i>Discrete and Computational Geometry</i>.
    Springer Nature, 2020. <a href="https://doi.org/10.1007/s00454-020-00213-z">https://doi.org/10.1007/s00454-020-00213-z</a>.
  ieee: J. Pach, B. Reed, and Y. Yuditsky, “Almost all string graphs are intersection
    graphs of plane convex sets,” <i>Discrete and Computational Geometry</i>, vol.
    63, no. 4. Springer Nature, pp. 888–917, 2020.
  ista: Pach J, Reed B, Yuditsky Y. 2020. Almost all string graphs are intersection
    graphs of plane convex sets. Discrete and Computational Geometry. 63(4), 888–917.
  mla: Pach, János, et al. “Almost All String Graphs Are Intersection Graphs of Plane
    Convex Sets.” <i>Discrete and Computational Geometry</i>, vol. 63, no. 4, Springer
    Nature, 2020, pp. 888–917, doi:<a href="https://doi.org/10.1007/s00454-020-00213-z">10.1007/s00454-020-00213-z</a>.
  short: J. Pach, B. Reed, Y. Yuditsky, Discrete and Computational Geometry 63 (2020)
    888–917.
date_created: 2020-06-14T22:00:51Z
date_published: 2020-06-05T00:00:00Z
date_updated: 2025-04-15T07:16:56Z
day: '05'
department:
- _id: HeEd
doi: 10.1007/s00454-020-00213-z
external_id:
  arxiv:
  - '1803.06710'
  isi:
  - '000538229000001'
fulldoi: https://doi.org/10.1007/s00454-020-00213-z
intvolume: '        63'
isi: 1
issue: '4'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1803.06710
month: '06'
oa: 1
oa_version: Preprint
page: 888-917
project:
- _id: 268116B8-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: Z00342
  name: Mathematics, Computer Science
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: Almost all string graphs are intersection graphs of plane convex sets
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 63
year: '2020'
...
---
_id: '8323'
article_processing_charge: No
article_type: letter_note
author:
- first_name: János
  full_name: Pach, János
  id: E62E3130-B088-11EA-B919-BF823C25FEA4
  last_name: Pach
citation:
  ama: Pach J. A farewell to Ricky Pollack. <i>Discrete and Computational Geometry</i>.
    2020;64:571-574. doi:<a href="https://doi.org/10.1007/s00454-020-00237-5">10.1007/s00454-020-00237-5</a>
  apa: Pach, J. (2020). A farewell to Ricky Pollack. <i>Discrete and Computational
    Geometry</i>. Springer Nature. <a href="https://doi.org/10.1007/s00454-020-00237-5">https://doi.org/10.1007/s00454-020-00237-5</a>
  chicago: Pach, János. “A Farewell to Ricky Pollack.” <i>Discrete and Computational
    Geometry</i>. Springer Nature, 2020. <a href="https://doi.org/10.1007/s00454-020-00237-5">https://doi.org/10.1007/s00454-020-00237-5</a>.
  ieee: J. Pach, “A farewell to Ricky Pollack,” <i>Discrete and Computational Geometry</i>,
    vol. 64. Springer Nature, pp. 571–574, 2020.
  ista: Pach J. 2020. A farewell to Ricky Pollack. Discrete and Computational Geometry.
    64, 571–574.
  mla: Pach, János. “A Farewell to Ricky Pollack.” <i>Discrete and Computational Geometry</i>,
    vol. 64, Springer Nature, 2020, pp. 571–74, doi:<a href="https://doi.org/10.1007/s00454-020-00237-5">10.1007/s00454-020-00237-5</a>.
  short: J. Pach, Discrete and Computational Geometry 64 (2020) 571–574.
corr_author: '1'
date_created: 2020-08-30T22:01:12Z
date_published: 2020-10-01T00:00:00Z
date_updated: 2024-10-09T20:59:55Z
day: '01'
department:
- _id: HeEd
doi: 10.1007/s00454-020-00237-5
external_id:
  isi:
  - '000561483500001'
fulldoi: https://doi.org/10.1007/s00454-020-00237-5
intvolume: '        64'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.1007/s00454-020-00237-5
month: '10'
oa: 1
oa_version: None
page: 571-574
publication: Discrete and Computational Geometry
publication_identifier:
  eissn:
  - '14320444'
  issn:
  - '01795376'
publication_status: published
publisher: Springer Nature
scopus_import: '1'
status: public
title: A farewell to Ricky Pollack
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 64
year: '2020'
...
---
OA_place: publisher
OA_type: hybrid
_id: '5678'
abstract:
- lang: eng
  text: "The order-k Voronoi tessellation of a locally finite set \U0001D44B⊆ℝ\U0001D45B
    decomposes ℝ\U0001D45B into convex domains whose points have the same k nearest
    neighbors in X. Assuming X is a stationary Poisson point process, we give explicit
    formulas for the expected number and total area of faces of a given dimension
    per unit volume of space. We also develop a relaxed version of discrete Morse
    theory and generalize by counting only faces, for which the k nearest points in
    X are within a given distance threshold."
acknowledgement: "Open access funding provided by Institute of Science and Technology
  (IST Austria). This project has received funding from the European Research Council
  (ERC) 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).\r\n\r\n"
article_processing_charge: Yes (via OA deal)
article_type: original
arxiv: 1
author:
- first_name: Herbert
  full_name: Edelsbrunner, Herbert
  id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
  last_name: Edelsbrunner
  orcid: 0000-0002-9823-6833
- first_name: Anton
  full_name: Nikitenko, Anton
  id: 3E4FF1BA-F248-11E8-B48F-1D18A9856A87
  last_name: Nikitenko
  orcid: 0000-0002-0659-3201
citation:
  ama: Edelsbrunner H, Nikitenko A. Poisson–Delaunay Mosaics of Order k. <i>Discrete
    and Computational Geometry</i>. 2019;62(4):865–878. doi:<a href="https://doi.org/10.1007/s00454-018-0049-2">10.1007/s00454-018-0049-2</a>
  apa: Edelsbrunner, H., &#38; Nikitenko, A. (2019). Poisson–Delaunay Mosaics of Order
    k. <i>Discrete and Computational Geometry</i>. Springer. <a href="https://doi.org/10.1007/s00454-018-0049-2">https://doi.org/10.1007/s00454-018-0049-2</a>
  chicago: Edelsbrunner, Herbert, and Anton Nikitenko. “Poisson–Delaunay Mosaics of
    Order K.” <i>Discrete and Computational Geometry</i>. Springer, 2019. <a href="https://doi.org/10.1007/s00454-018-0049-2">https://doi.org/10.1007/s00454-018-0049-2</a>.
  ieee: H. Edelsbrunner and A. Nikitenko, “Poisson–Delaunay Mosaics of Order k,” <i>Discrete
    and Computational Geometry</i>, vol. 62, no. 4. Springer, pp. 865–878, 2019.
  ista: Edelsbrunner H, Nikitenko A. 2019. Poisson–Delaunay Mosaics of Order k. Discrete
    and Computational Geometry. 62(4), 865–878.
  mla: Edelsbrunner, Herbert, and Anton Nikitenko. “Poisson–Delaunay Mosaics of Order
    K.” <i>Discrete and Computational Geometry</i>, vol. 62, no. 4, Springer, 2019,
    pp. 865–878, doi:<a href="https://doi.org/10.1007/s00454-018-0049-2">10.1007/s00454-018-0049-2</a>.
  short: H. Edelsbrunner, A. Nikitenko, Discrete and Computational Geometry 62 (2019)
    865–878.
corr_author: '1'
date_created: 2018-12-16T22:59:20Z
date_published: 2019-12-01T00:00:00Z
date_updated: 2026-07-28T13:38:08Z
day: '01'
ddc:
- '516'
department:
- _id: HeEd
doi: 10.1007/s00454-018-0049-2
ec_funded: 1
external_id:
  arxiv:
  - '1709.09380'
  isi:
  - '000494042900008'
file:
- access_level: open_access
  checksum: f9d00e166efaccb5a76bbcbb4dcea3b4
  content_type: application/pdf
  creator: dernst
  date_created: 2019-02-06T10:10:46Z
  date_updated: 2020-07-14T12:47:10Z
  file_id: '5932'
  file_name: 2018_DiscreteCompGeometry_Edelsbrunner.pdf
  file_size: 599339
  relation: main_file
file_date_updated: 2020-07-14T12:47:10Z
fulldoi: https://doi.org/10.1007/s00454-018-0049-2
has_accepted_license: '1'
intvolume: '        62'
isi: 1
issue: '4'
language:
- iso: eng
month: '12'
oa: 1
oa_version: Published Version
page: 865–878
project:
- _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
quality_controlled: '1'
related_material:
  record:
  - id: '6287'
    relation: dissertation_contains
    status: public
scopus_import: '1'
status: public
title: Poisson–Delaunay Mosaics of Order k
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: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 62
year: '2019'
...