---
_id: '9604'
abstract:
- lang: eng
  text: Generalizing Lee’s inductive argument for counting the cells of higher order
    Voronoi tessellations in ℝ² to ℝ³, we get precise relations in terms of Morse
    theoretic quantities for piecewise constant functions on planar arrangements.
    Specifically, we prove that for a generic set of n ≥ 5 points in ℝ³, the number
    of regions in the order-k Voronoi tessellation is N_{k-1} - binom(k,2)n + n, for
    1 ≤ k ≤ n-1, in which N_{k-1} is the sum of Euler characteristics of these function’s
    first k-1 sublevel sets. We get similar expressions for the vertices, edges, and
    polygons of the order-k Voronoi tessellation.
alternative_title:
- LIPIcs
article_number: '16'
article_processing_charge: No
author:
- first_name: Ranita
  full_name: Biswas, Ranita
  id: 3C2B033E-F248-11E8-B48F-1D18A9856A87
  last_name: Biswas
  orcid: 0000-0002-5372-7890
- first_name: Sebastiano
  full_name: Cultrera di Montesano, Sebastiano
  id: 34D2A09C-F248-11E8-B48F-1D18A9856A87
  last_name: Cultrera di Montesano
  orcid: 0000-0001-6249-0832
- first_name: Herbert
  full_name: Edelsbrunner, Herbert
  id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
  last_name: Edelsbrunner
  orcid: 0000-0002-9823-6833
- first_name: Morteza
  full_name: Saghafian, Morteza
  last_name: Saghafian
citation:
  ama: 'Biswas R, Cultrera di Montesano S, Edelsbrunner H, Saghafian M. Counting cells
    of order-k voronoi tessellations in ℝ<sup>3</sup> with morse theory. In: <i>Leibniz
    International Proceedings in Informatics</i>. Vol 189. Schloss Dagstuhl - Leibniz-Zentrum
    für Informatik; 2021. doi:<a href="https://doi.org/10.4230/LIPIcs.SoCG.2021.16">10.4230/LIPIcs.SoCG.2021.16</a>'
  apa: 'Biswas, R., Cultrera di Montesano, S., Edelsbrunner, H., &#38; Saghafian,
    M. (2021). Counting cells of order-k voronoi tessellations in ℝ<sup>3</sup> with
    morse theory. In <i>Leibniz International Proceedings in Informatics</i> (Vol.
    189). Online: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href="https://doi.org/10.4230/LIPIcs.SoCG.2021.16">https://doi.org/10.4230/LIPIcs.SoCG.2021.16</a>'
  chicago: Biswas, Ranita, Sebastiano Cultrera di Montesano, Herbert Edelsbrunner,
    and Morteza Saghafian. “Counting Cells of Order-k Voronoi Tessellations in ℝ<sup>3</sup>
    with Morse Theory.” In <i>Leibniz International Proceedings in Informatics</i>,
    Vol. 189. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. <a href="https://doi.org/10.4230/LIPIcs.SoCG.2021.16">https://doi.org/10.4230/LIPIcs.SoCG.2021.16</a>.
  ieee: R. Biswas, S. Cultrera di Montesano, H. Edelsbrunner, and M. Saghafian, “Counting
    cells of order-k voronoi tessellations in ℝ<sup>3</sup> with morse theory,” in
    <i>Leibniz International Proceedings in Informatics</i>, Online, 2021, vol. 189.
  ista: 'Biswas R, Cultrera di Montesano S, Edelsbrunner H, Saghafian M. 2021. Counting
    cells of order-k voronoi tessellations in ℝ<sup>3</sup> with morse theory. Leibniz
    International Proceedings in Informatics. SoCG: International Symposium on Computational
    Geometry, LIPIcs, vol. 189, 16.'
  mla: Biswas, Ranita, et al. “Counting Cells of Order-k Voronoi Tessellations in
    ℝ<sup>3</sup> with Morse Theory.” <i>Leibniz International Proceedings in Informatics</i>,
    vol. 189, 16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021, doi:<a
    href="https://doi.org/10.4230/LIPIcs.SoCG.2021.16">10.4230/LIPIcs.SoCG.2021.16</a>.
  short: R. Biswas, S. Cultrera di Montesano, H. Edelsbrunner, M. Saghafian, in:,
    Leibniz International Proceedings in Informatics, Schloss Dagstuhl - Leibniz-Zentrum
    für Informatik, 2021.
conference:
  end_date: 2021-06-11
  location: Online
  name: 'SoCG: International Symposium on Computational Geometry'
  start_date: 2021-06-07
date_created: 2021-06-27T22:01:48Z
date_published: 2021-06-02T00:00:00Z
date_updated: 2023-02-23T14:02:28Z
day: '02'
ddc:
- '516'
department:
- _id: HeEd
doi: 10.4230/LIPIcs.SoCG.2021.16
ec_funded: 1
file:
- access_level: open_access
  checksum: 22b11a719018b22ecba2471b51f2eb40
  content_type: application/pdf
  creator: asandaue
  date_created: 2021-06-28T13:11:39Z
  date_updated: 2021-06-28T13:11:39Z
  file_id: '9611'
  file_name: 2021_LIPIcs_Biswas.pdf
  file_size: 727817
  relation: main_file
  success: 1
file_date_updated: 2021-06-28T13:11:39Z
has_accepted_license: '1'
intvolume: '       189'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
project:
- _id: 266A2E9E-B435-11E9-9278-68D0E5697425
  call_identifier: H2020
  grant_number: '788183'
  name: Alpha Shape Theory Extended
- _id: 268116B8-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: Z00342
  name: The Wittgenstein Prize
- _id: 0aa4bc98-070f-11eb-9043-e6fff9c6a316
  grant_number: I4887
  name: Discretization in Geometry and Dynamics
publication: Leibniz International Proceedings in Informatics
publication_identifier:
  isbn:
  - '9783959771849'
  issn:
  - '18688969'
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Counting cells of order-k voronoi tessellations in ℝ<sup>3</sup> with morse
  theory
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: conference
user_id: D865714E-FA4E-11E9-B85B-F5C5E5697425
volume: 189
year: '2021'
...
---
_id: '9605'
abstract:
- lang: eng
  text: 'Given a finite set A ⊂ ℝ^d, let Cov_{r,k} denote the set of all points within
    distance r to at least k points of A. Allowing r and k to vary, we obtain a 2-parameter
    family of spaces that grow larger when r increases or k decreases, called the
    multicover bifiltration. Motivated by the problem of computing the homology of
    this bifiltration, we introduce two closely related combinatorial bifiltrations,
    one polyhedral and the other simplicial, which are both topologically equivalent
    to the multicover bifiltration and far smaller than a Čech-based model considered
    in prior work of Sheehy. Our polyhedral construction is a bifiltration of the
    rhomboid tiling of Edelsbrunner and Osang, and can be efficiently computed using
    a variant of an algorithm given by these authors as well. Using an implementation
    for dimension 2 and 3, we provide experimental results. Our simplicial construction
    is useful for understanding the polyhedral construction and proving its correctness. '
acknowledgement: The authors want to thank the reviewers for many helpful comments
  and suggestions.
alternative_title:
- LIPIcs
article_number: '27'
article_processing_charge: No
arxiv: 1
author:
- first_name: René
  full_name: Corbet, René
  last_name: Corbet
- first_name: Michael
  full_name: Kerber, Michael
  last_name: Kerber
- first_name: Michael
  full_name: Lesnick, Michael
  last_name: Lesnick
- first_name: Georg F
  full_name: Osang, Georg F
  id: 464B40D6-F248-11E8-B48F-1D18A9856A87
  last_name: Osang
  orcid: 0000-0002-8882-5116
citation:
  ama: 'Corbet R, Kerber M, Lesnick M, Osang GF. Computing the multicover bifiltration.
    In: <i>Leibniz International Proceedings in Informatics</i>. Vol 189. Schloss
    Dagstuhl - Leibniz-Zentrum für Informatik; 2021. doi:<a href="https://doi.org/10.4230/LIPIcs.SoCG.2021.27">10.4230/LIPIcs.SoCG.2021.27</a>'
  apa: 'Corbet, R., Kerber, M., Lesnick, M., &#38; Osang, G. F. (2021). Computing
    the multicover bifiltration. In <i>Leibniz International Proceedings in Informatics</i>
    (Vol. 189). Online: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href="https://doi.org/10.4230/LIPIcs.SoCG.2021.27">https://doi.org/10.4230/LIPIcs.SoCG.2021.27</a>'
  chicago: Corbet, René, Michael Kerber, Michael Lesnick, and Georg F Osang. “Computing
    the Multicover Bifiltration.” In <i>Leibniz International Proceedings in Informatics</i>,
    Vol. 189. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. <a href="https://doi.org/10.4230/LIPIcs.SoCG.2021.27">https://doi.org/10.4230/LIPIcs.SoCG.2021.27</a>.
  ieee: R. Corbet, M. Kerber, M. Lesnick, and G. F. Osang, “Computing the multicover
    bifiltration,” in <i>Leibniz International Proceedings in Informatics</i>, Online,
    2021, vol. 189.
  ista: 'Corbet R, Kerber M, Lesnick M, Osang GF. 2021. Computing the multicover bifiltration.
    Leibniz International Proceedings in Informatics. SoCG: International Symposium
    on Computational Geometry, LIPIcs, vol. 189, 27.'
  mla: Corbet, René, et al. “Computing the Multicover Bifiltration.” <i>Leibniz International
    Proceedings in Informatics</i>, vol. 189, 27, Schloss Dagstuhl - Leibniz-Zentrum
    für Informatik, 2021, doi:<a href="https://doi.org/10.4230/LIPIcs.SoCG.2021.27">10.4230/LIPIcs.SoCG.2021.27</a>.
  short: R. Corbet, M. Kerber, M. Lesnick, G.F. Osang, in:, Leibniz International
    Proceedings in Informatics, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
    2021.
conference:
  end_date: 2021-06-11
  location: Online
  name: 'SoCG: International Symposium on Computational Geometry'
  start_date: 2021-06-07
date_created: 2021-06-27T22:01:49Z
date_published: 2021-06-02T00:00:00Z
date_updated: 2023-10-04T12:03:39Z
day: '02'
ddc:
- '516'
department:
- _id: HeEd
doi: 10.4230/LIPIcs.SoCG.2021.27
external_id:
  arxiv:
  - '2103.07823'
file:
- access_level: open_access
  checksum: 0de217501e7ba8b267d58deed0d51761
  content_type: application/pdf
  creator: cziletti
  date_created: 2021-06-28T12:40:47Z
  date_updated: 2021-06-28T12:40:47Z
  file_id: '9610'
  file_name: 2021_LIPIcs_Corbet.pdf
  file_size: '1367983'
  relation: main_file
  success: 1
file_date_updated: 2021-06-28T12:40:47Z
has_accepted_license: '1'
intvolume: '       189'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
publication: Leibniz International Proceedings in Informatics
publication_identifier:
  isbn:
  - '9783959771849'
  issn:
  - '18688969'
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
related_material:
  link:
  - relation: extended_version
    url: https://arxiv.org/abs/2103.07823
  record:
  - id: '12709'
    relation: later_version
    status: public
scopus_import: '1'
status: public
title: Computing the multicover bifiltration
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: conference
user_id: D865714E-FA4E-11E9-B85B-F5C5E5697425
volume: 189
year: '2021'
...