---
_id: '312'
abstract:
- lang: eng
  text: Motivated by biological questions, we study configurations of equal spheres
    that neither pack nor cover. Placing their centers on a lattice, we define the
    soft density of the configuration by penalizing multiple overlaps. Considering
    the 1-parameter family of diagonally distorted 3-dimensional integer lattices,
    we show that the soft density is maximized at the FCC lattice.
acknowledgement: This work was partially supported by the DFG Collaborative Research
  Center TRR 109, “Discretization in Geometry and Dynamics,” through grant I02979-N35
  of the Austrian Science Fund (FWF).
article_processing_charge: No
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: Mabel
  full_name: Iglesias Ham, Mabel
  id: 41B58C0C-F248-11E8-B48F-1D18A9856A87
  last_name: Iglesias Ham
citation:
  ama: Edelsbrunner H, Iglesias Ham M. On the optimality of the FCC lattice for soft
    sphere packing. <i>SIAM J Discrete Math</i>. 2018;32(1):750-782. doi:<a href="https://doi.org/10.1137/16M1097201">10.1137/16M1097201</a>
  apa: Edelsbrunner, H., &#38; Iglesias Ham, M. (2018). On the optimality of the FCC
    lattice for soft sphere packing. <i>SIAM J Discrete Math</i>. Society for Industrial
    and Applied Mathematics . <a href="https://doi.org/10.1137/16M1097201">https://doi.org/10.1137/16M1097201</a>
  chicago: Edelsbrunner, Herbert, and Mabel Iglesias Ham. “On the Optimality of the
    FCC Lattice for Soft Sphere Packing.” <i>SIAM J Discrete Math</i>. Society for
    Industrial and Applied Mathematics , 2018. <a href="https://doi.org/10.1137/16M1097201">https://doi.org/10.1137/16M1097201</a>.
  ieee: H. Edelsbrunner and M. Iglesias Ham, “On the optimality of the FCC lattice
    for soft sphere packing,” <i>SIAM J Discrete Math</i>, vol. 32, no. 1. Society
    for Industrial and Applied Mathematics , pp. 750–782, 2018.
  ista: Edelsbrunner H, Iglesias Ham M. 2018. On the optimality of the FCC lattice
    for soft sphere packing. SIAM J Discrete Math. 32(1), 750–782.
  mla: Edelsbrunner, Herbert, and Mabel Iglesias Ham. “On the Optimality of the FCC
    Lattice for Soft Sphere Packing.” <i>SIAM J Discrete Math</i>, vol. 32, no. 1,
    Society for Industrial and Applied Mathematics , 2018, pp. 750–82, doi:<a href="https://doi.org/10.1137/16M1097201">10.1137/16M1097201</a>.
  short: H. Edelsbrunner, M. Iglesias Ham, SIAM J Discrete Math 32 (2018) 750–782.
date_created: 2018-12-11T11:45:46Z
date_published: 2018-03-29T00:00:00Z
date_updated: 2023-09-13T09:34:38Z
day: '29'
department:
- _id: HeEd
doi: 10.1137/16M1097201
external_id:
  isi:
  - '000428958900038'
intvolume: '        32'
isi: 1
issue: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: http://pdfs.semanticscholar.org/d2d5/6da00fbc674e6a8b1bb9d857167e54200dc6.pdf
month: '03'
oa: 1
oa_version: Submitted Version
page: 750 - 782
project:
- _id: 2561EBF4-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: I02979-N35
  name: Persistence and stability of geometric complexes
publication: SIAM J Discrete Math
publication_identifier:
  issn:
  - '08954801'
publication_status: published
publisher: 'Society for Industrial and Applied Mathematics '
publist_id: '7553'
quality_controlled: '1'
scopus_import: '1'
status: public
title: On the optimality of the FCC lattice for soft sphere packing
type: journal_article
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 32
year: '2018'
...
---
_id: '201'
abstract:
- lang: eng
  text: 'We describe arrangements of three-dimensional spheres from a geometrical
    and topological point of view. Real data (fitting this setup) often consist of
    soft spheres which show certain degree of deformation while strongly packing against
    each other. In this context, we answer the following questions: If we model a
    soft packing of spheres by hard spheres that are allowed to overlap, can we measure
    the volume in the overlapped areas? Can we be more specific about the overlap
    volume, i.e. quantify how much volume is there covered exactly twice, three times,
    or k times? What would be a good optimization criteria that rule the arrangement
    of soft spheres while making a good use of the available space? Fixing a particular
    criterion, what would be the optimal sphere configuration? The first result of
    this thesis are short formulas for the computation of volumes covered by at least
    k of the balls. The formulas exploit information contained in the order-k Voronoi
    diagrams and its closely related Level-k complex. The used complexes lead to a
    natural generalization into poset diagrams, a theoretical formalism that contains
    the order-k and degree-k diagrams as special cases. In parallel, we define different
    criteria to determine what could be considered an optimal arrangement from a geometrical
    point of view. Fixing a criterion, we find optimal soft packing configurations
    in 2D and 3D where the ball centers lie on a lattice. As a last step, we use tools
    from computational topology on real physical data, to show the potentials of higher-order
    diagrams in the description of melting crystals. The results of the experiments
    leaves us with an open window to apply the theories developed in this thesis in
    real applications.'
alternative_title:
- ISTA Thesis
article_processing_charge: No
author:
- first_name: Mabel
  full_name: Iglesias Ham, Mabel
  id: 41B58C0C-F248-11E8-B48F-1D18A9856A87
  last_name: Iglesias Ham
citation:
  ama: Iglesias Ham M. Multiple covers with balls. 2018. doi:<a href="https://doi.org/10.15479/AT:ISTA:th_1026">10.15479/AT:ISTA:th_1026</a>
  apa: Iglesias Ham, M. (2018). <i>Multiple covers with balls</i>. Institute of Science
    and Technology Austria. <a href="https://doi.org/10.15479/AT:ISTA:th_1026">https://doi.org/10.15479/AT:ISTA:th_1026</a>
  chicago: Iglesias Ham, Mabel. “Multiple Covers with Balls.” Institute of Science
    and Technology Austria, 2018. <a href="https://doi.org/10.15479/AT:ISTA:th_1026">https://doi.org/10.15479/AT:ISTA:th_1026</a>.
  ieee: M. Iglesias Ham, “Multiple covers with balls,” Institute of Science and Technology
    Austria, 2018.
  ista: Iglesias Ham M. 2018. Multiple covers with balls. Institute of Science and
    Technology Austria.
  mla: Iglesias Ham, Mabel. <i>Multiple Covers with Balls</i>. Institute of Science
    and Technology Austria, 2018, doi:<a href="https://doi.org/10.15479/AT:ISTA:th_1026">10.15479/AT:ISTA:th_1026</a>.
  short: M. Iglesias Ham, Multiple Covers with Balls, Institute of Science and Technology
    Austria, 2018.
date_created: 2018-12-11T11:45:10Z
date_published: 2018-06-11T00:00:00Z
date_updated: 2023-09-07T12:25:32Z
day: '11'
ddc:
- '514'
- '516'
degree_awarded: PhD
department:
- _id: HeEd
doi: 10.15479/AT:ISTA:th_1026
file:
- access_level: closed
  checksum: dd699303623e96d1478a6ae07210dd05
  content_type: application/zip
  creator: kschuh
  date_created: 2019-02-05T07:43:31Z
  date_updated: 2020-07-14T12:45:24Z
  file_id: '5918'
  file_name: IST-2018-1025-v2+5_ist-thesis-iglesias-11June2018(1).zip
  file_size: 11827713
  relation: source_file
- access_level: open_access
  checksum: ba163849a190d2b41d66fef0e4983294
  content_type: application/pdf
  creator: kschuh
  date_created: 2019-02-05T07:43:45Z
  date_updated: 2020-07-14T12:45:24Z
  file_id: '5919'
  file_name: IST-2018-1025-v2+4_ThesisIglesiasFinal11June2018.pdf
  file_size: 4783846
  relation: main_file
file_date_updated: 2020-07-14T12:45:24Z
has_accepted_license: '1'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: '171'
publication_identifier:
  issn:
  - 2663-337X
publication_status: published
publisher: Institute of Science and Technology Austria
publist_id: '7712'
pubrep_id: '1026'
status: public
supervisor:
- first_name: Herbert
  full_name: Edelsbrunner, Herbert
  id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
  last_name: Edelsbrunner
  orcid: 0000-0002-9823-6833
title: Multiple covers with balls
type: dissertation
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
year: '2018'
...
---
_id: '530'
abstract:
- lang: eng
  text: Inclusion–exclusion is an effective method for computing the volume of a union
    of measurable sets. We extend it to multiple coverings, proving short inclusion–exclusion
    formulas for the subset of Rn covered by at least k balls in a finite set. We
    implement two of the formulas in dimension n=3 and report on results obtained
    with our software.
article_processing_charge: No
author:
- first_name: Herbert
  full_name: Edelsbrunner, Herbert
  id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
  last_name: Edelsbrunner
  orcid: 0000-0002-9823-6833
- first_name: Mabel
  full_name: Iglesias Ham, Mabel
  id: 41B58C0C-F248-11E8-B48F-1D18A9856A87
  last_name: Iglesias Ham
citation:
  ama: 'Edelsbrunner H, Iglesias Ham M. Multiple covers with balls I: Inclusion–exclusion.
    <i>Computational Geometry: Theory and Applications</i>. 2018;68:119-133. doi:<a
    href="https://doi.org/10.1016/j.comgeo.2017.06.014">10.1016/j.comgeo.2017.06.014</a>'
  apa: 'Edelsbrunner, H., &#38; Iglesias Ham, M. (2018). Multiple covers with balls
    I: Inclusion–exclusion. <i>Computational Geometry: Theory and Applications</i>.
    Elsevier. <a href="https://doi.org/10.1016/j.comgeo.2017.06.014">https://doi.org/10.1016/j.comgeo.2017.06.014</a>'
  chicago: 'Edelsbrunner, Herbert, and Mabel Iglesias Ham. “Multiple Covers with Balls
    I: Inclusion–Exclusion.” <i>Computational Geometry: Theory and Applications</i>.
    Elsevier, 2018. <a href="https://doi.org/10.1016/j.comgeo.2017.06.014">https://doi.org/10.1016/j.comgeo.2017.06.014</a>.'
  ieee: 'H. Edelsbrunner and M. Iglesias Ham, “Multiple covers with balls I: Inclusion–exclusion,”
    <i>Computational Geometry: Theory and Applications</i>, vol. 68. Elsevier, pp.
    119–133, 2018.'
  ista: 'Edelsbrunner H, Iglesias Ham M. 2018. Multiple covers with balls I: Inclusion–exclusion.
    Computational Geometry: Theory and Applications. 68, 119–133.'
  mla: 'Edelsbrunner, Herbert, and Mabel Iglesias Ham. “Multiple Covers with Balls
    I: Inclusion–Exclusion.” <i>Computational Geometry: Theory and Applications</i>,
    vol. 68, Elsevier, 2018, pp. 119–33, doi:<a href="https://doi.org/10.1016/j.comgeo.2017.06.014">10.1016/j.comgeo.2017.06.014</a>.'
  short: 'H. Edelsbrunner, M. Iglesias Ham, Computational Geometry: Theory and Applications
    68 (2018) 119–133.'
date_created: 2018-12-11T11:46:59Z
date_published: 2018-03-01T00:00:00Z
date_updated: 2023-09-13T08:59:00Z
day: '01'
ddc:
- '000'
department:
- _id: HeEd
doi: 10.1016/j.comgeo.2017.06.014
ec_funded: 1
external_id:
  isi:
  - '000415778300010'
file:
- access_level: open_access
  checksum: 1c8d58cd489a66cd3e2064c1141c8c5e
  content_type: application/pdf
  creator: dernst
  date_created: 2019-02-12T06:47:52Z
  date_updated: 2020-07-14T12:46:38Z
  file_id: '5953'
  file_name: 2018_Edelsbrunner.pdf
  file_size: 708357
  relation: main_file
file_date_updated: 2020-07-14T12:46:38Z
has_accepted_license: '1'
intvolume: '        68'
isi: 1
language:
- iso: eng
month: '03'
oa: 1
oa_version: Preprint
page: 119 - 133
project:
- _id: 255D761E-B435-11E9-9278-68D0E5697425
  call_identifier: FP7
  grant_number: '318493'
  name: Topological Complex Systems
publication: 'Computational Geometry: Theory and Applications'
publication_status: published
publisher: Elsevier
publist_id: '7289'
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Multiple covers with balls I: Inclusion–exclusion'
type: journal_article
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 68
year: '2018'
...
---
_id: '1295'
abstract:
- lang: eng
  text: Voronoi diagrams and Delaunay triangulations have been extensively used to
    represent and compute geometric features of point configurations. We introduce
    a generalization to poset diagrams and poset complexes, which contain order-k
    and degree-k Voronoi diagrams and their duals as special cases. Extending a result
    of Aurenhammer from 1990, we show how to construct poset diagrams as weighted
    Voronoi diagrams of average balls.
acknowledgement: This work is partially supported by the Toposys project FP7-ICT-318493-STREP,
  and by ESF under the ACAT Research Network Programme.
author:
- first_name: Herbert
  full_name: Edelsbrunner, Herbert
  id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
  last_name: Edelsbrunner
  orcid: 0000-0002-9823-6833
- first_name: Mabel
  full_name: Iglesias Ham, Mabel
  id: 41B58C0C-F248-11E8-B48F-1D18A9856A87
  last_name: Iglesias Ham
citation:
  ama: 'Edelsbrunner H, Iglesias Ham M. Multiple covers with balls II: Weighted averages.
    <i>Electronic Notes in Discrete Mathematics</i>. 2016;54:169-174. doi:<a href="https://doi.org/10.1016/j.endm.2016.09.030">10.1016/j.endm.2016.09.030</a>'
  apa: 'Edelsbrunner, H., &#38; Iglesias Ham, M. (2016). Multiple covers with balls
    II: Weighted averages. <i>Electronic Notes in Discrete Mathematics</i>. Elsevier.
    <a href="https://doi.org/10.1016/j.endm.2016.09.030">https://doi.org/10.1016/j.endm.2016.09.030</a>'
  chicago: 'Edelsbrunner, Herbert, and Mabel Iglesias Ham. “Multiple Covers with Balls
    II: Weighted Averages.” <i>Electronic Notes in Discrete Mathematics</i>. Elsevier,
    2016. <a href="https://doi.org/10.1016/j.endm.2016.09.030">https://doi.org/10.1016/j.endm.2016.09.030</a>.'
  ieee: 'H. Edelsbrunner and M. Iglesias Ham, “Multiple covers with balls II: Weighted
    averages,” <i>Electronic Notes in Discrete Mathematics</i>, vol. 54. Elsevier,
    pp. 169–174, 2016.'
  ista: 'Edelsbrunner H, Iglesias Ham M. 2016. Multiple covers with balls II: Weighted
    averages. Electronic Notes in Discrete Mathematics. 54, 169–174.'
  mla: 'Edelsbrunner, Herbert, and Mabel Iglesias Ham. “Multiple Covers with Balls
    II: Weighted Averages.” <i>Electronic Notes in Discrete Mathematics</i>, vol.
    54, Elsevier, 2016, pp. 169–74, doi:<a href="https://doi.org/10.1016/j.endm.2016.09.030">10.1016/j.endm.2016.09.030</a>.'
  short: H. Edelsbrunner, M. Iglesias Ham, Electronic Notes in Discrete Mathematics
    54 (2016) 169–174.
date_created: 2018-12-11T11:51:12Z
date_published: 2016-10-01T00:00:00Z
date_updated: 2021-01-12T06:49:41Z
day: '01'
department:
- _id: HeEd
doi: 10.1016/j.endm.2016.09.030
ec_funded: 1
intvolume: '        54'
language:
- iso: eng
month: '10'
oa_version: None
page: 169 - 174
project:
- _id: 255D761E-B435-11E9-9278-68D0E5697425
  call_identifier: FP7
  grant_number: '318493'
  name: Topological Complex Systems
publication: Electronic Notes in Discrete Mathematics
publication_status: published
publisher: Elsevier
publist_id: '5976'
quality_controlled: '1'
scopus_import: 1
status: public
title: 'Multiple covers with balls II: Weighted averages'
type: journal_article
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 54
year: '2016'
...
---
_id: '1495'
abstract:
- lang: eng
  text: 'Motivated by biological questions, we study configurations of equal-sized
    disks in the Euclidean plane that neither pack nor cover. Measuring the quality
    by the probability that a random point lies in exactly one disk, we show that
    the regular hexagonal grid gives the maximum among lattice configurations. '
author:
- first_name: Herbert
  full_name: Edelsbrunner, Herbert
  id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
  last_name: Edelsbrunner
  orcid: 0000-0002-9823-6833
- first_name: Mabel
  full_name: Iglesias Ham, Mabel
  id: 41B58C0C-F248-11E8-B48F-1D18A9856A87
  last_name: Iglesias Ham
- first_name: Vitaliy
  full_name: Kurlin, Vitaliy
  last_name: Kurlin
citation:
  ama: 'Edelsbrunner H, Iglesias Ham M, Kurlin V. Relaxed disk packing. In: <i>Proceedings
    of the 27th Canadian Conference on Computational Geometry</i>. Vol 2015-August.
    Queen’s University; 2015:128-135.'
  apa: 'Edelsbrunner, H., Iglesias Ham, M., &#38; Kurlin, V. (2015). Relaxed disk
    packing. In <i>Proceedings of the 27th Canadian Conference on Computational Geometry</i>
    (Vol. 2015–August, pp. 128–135). Ontario, Canada: Queen’s University.'
  chicago: Edelsbrunner, Herbert, Mabel Iglesias Ham, and Vitaliy Kurlin. “Relaxed
    Disk Packing.” In <i>Proceedings of the 27th Canadian Conference on Computational
    Geometry</i>, 2015–August:128–35. Queen’s University, 2015.
  ieee: H. Edelsbrunner, M. Iglesias Ham, and V. Kurlin, “Relaxed disk packing,” in
    <i>Proceedings of the 27th Canadian Conference on Computational Geometry</i>,
    Ontario, Canada, 2015, vol. 2015–August, pp. 128–135.
  ista: 'Edelsbrunner H, Iglesias Ham M, Kurlin V. 2015. Relaxed disk packing. Proceedings
    of the 27th Canadian Conference on Computational Geometry. CCCG: Canadian Conference
    on Computational Geometry vol. 2015–August, 128–135.'
  mla: Edelsbrunner, Herbert, et al. “Relaxed Disk Packing.” <i>Proceedings of the
    27th Canadian Conference on Computational Geometry</i>, vol. 2015–August, Queen’s
    University, 2015, pp. 128–35.
  short: H. Edelsbrunner, M. Iglesias Ham, V. Kurlin, in:, Proceedings of the 27th
    Canadian Conference on Computational Geometry, Queen’s University, 2015, pp. 128–135.
conference:
  end_date: 2015-08-12
  location: Ontario, Canada
  name: 'CCCG: Canadian Conference on Computational Geometry'
  start_date: 2015-08-10
date_created: 2018-12-11T11:52:21Z
date_published: 2015-08-01T00:00:00Z
date_updated: 2021-01-12T06:51:09Z
day: '01'
department:
- _id: HeEd
ec_funded: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1505.03402
month: '08'
oa: 1
oa_version: Submitted Version
page: 128-135
project:
- _id: 255D761E-B435-11E9-9278-68D0E5697425
  call_identifier: FP7
  grant_number: '318493'
  name: Topological Complex Systems
publication: Proceedings of the 27th Canadian Conference on Computational Geometry
publication_status: published
publisher: Queen's University
publist_id: '5684'
quality_controlled: '1'
scopus_import: 1
status: public
title: Relaxed disk packing
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 2015-August
year: '2015'
...
---
_id: '2012'
abstract:
- lang: eng
  text: The classical sphere packing problem asks for the best (infinite) arrangement
    of non-overlapping unit balls which cover as much space as possible. We define
    a generalized version of the problem, where we allow each ball a limited amount
    of overlap with other balls. We study two natural choices of overlap measures
    and obtain the optimal lattice packings in a parameterized family of lattices
    which contains the FCC, BCC, and integer lattice.
acknowledgement: We thank Herbert Edelsbrunner for his valuable discussions and ideas
  on the topic of this paper.  The second author has been supported by the Max Planck
  Center for Visual Computing and Communication
article_number: '1401.0468'
article_processing_charge: No
arxiv: 1
author:
- first_name: Mabel
  full_name: Iglesias Ham, Mabel
  id: 41B58C0C-F248-11E8-B48F-1D18A9856A87
  last_name: Iglesias Ham
- first_name: Michael
  full_name: Kerber, Michael
  last_name: Kerber
  orcid: 0000-0002-8030-9299
- first_name: Caroline
  full_name: Uhler, Caroline
  id: 49ADD78E-F248-11E8-B48F-1D18A9856A87
  last_name: Uhler
  orcid: 0000-0002-7008-0216
citation:
  ama: Iglesias Ham M, Kerber M, Uhler C. Sphere packing with limited overlap. <i>arXiv</i>.
    doi:<a href="https://doi.org/10.48550/arXiv.1401.0468">10.48550/arXiv.1401.0468</a>
  apa: Iglesias Ham, M., Kerber, M., &#38; Uhler, C. (n.d.). Sphere packing with limited
    overlap. <i>arXiv</i>. <a href="https://doi.org/10.48550/arXiv.1401.0468">https://doi.org/10.48550/arXiv.1401.0468</a>
  chicago: Iglesias Ham, Mabel, Michael Kerber, and Caroline Uhler. “Sphere Packing
    with Limited Overlap.” <i>ArXiv</i>, n.d. <a href="https://doi.org/10.48550/arXiv.1401.0468">https://doi.org/10.48550/arXiv.1401.0468</a>.
  ieee: M. Iglesias Ham, M. Kerber, and C. Uhler, “Sphere packing with limited overlap,”
    <i>arXiv</i>. .
  ista: Iglesias Ham M, Kerber M, Uhler C. Sphere packing with limited overlap. arXiv,
    1401.0468.
  mla: Iglesias Ham, Mabel, et al. “Sphere Packing with Limited Overlap.” <i>ArXiv</i>,
    1401.0468, doi:<a href="https://doi.org/10.48550/arXiv.1401.0468">10.48550/arXiv.1401.0468</a>.
  short: M. Iglesias Ham, M. Kerber, C. Uhler, ArXiv (n.d.).
date_created: 2018-12-11T11:55:12Z
date_published: 2014-01-01T00:00:00Z
date_updated: 2023-10-18T08:06:45Z
day: '01'
department:
- _id: HeEd
- _id: CaUh
doi: 10.48550/arXiv.1401.0468
external_id:
  arxiv:
  - '1401.0468'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: http://cccg.ca/proceedings/2014/papers/paper23.pdf
month: '01'
oa: 1
oa_version: Submitted Version
publication: arXiv
publication_status: submitted
publist_id: '5064'
status: public
title: Sphere packing with limited overlap
type: preprint
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2014'
...