---
_id: '6647'
abstract:
- lang: eng
  text: The Tverberg theorem is one of the cornerstones of discrete geometry. It states
    that, given a set X of at least (d+1)(r-1)+1 points in R^d, one can find a partition
    X=X_1 cup ... cup X_r of X, such that the convex hulls of the X_i, i=1,...,r,
    all share a common point. In this paper, we prove a strengthening of this theorem
    that guarantees a partition which, in addition to the above, has the property
    that the boundaries of full-dimensional convex hulls have pairwise nonempty intersections.
    Possible generalizations and algorithmic aspects are also discussed. As a concrete
    application, we show that any n points in the plane in general position span floor[n/3]
    vertex-disjoint triangles that are pairwise crossing, meaning that their boundaries
    have pairwise nonempty intersections; this number is clearly best possible. A
    previous result of Alvarez-Rebollar et al. guarantees floor[n/6] pairwise crossing
    triangles. Our result generalizes to a result about simplices in R^d,d >=2.
alternative_title:
- LIPIcs
arxiv: 1
author:
- first_name: Radoslav
  full_name: Fulek, Radoslav
  id: 39F3FFE4-F248-11E8-B48F-1D18A9856A87
  last_name: Fulek
  orcid: 0000-0001-8485-1774
- first_name: Bernd
  full_name: Gärtner, Bernd
  last_name: Gärtner
- first_name: Andrey
  full_name: Kupavskii, Andrey
  last_name: Kupavskii
- first_name: Pavel
  full_name: Valtr, Pavel
  last_name: Valtr
- first_name: Uli
  full_name: Wagner, Uli
  id: 36690CA2-F248-11E8-B48F-1D18A9856A87
  last_name: Wagner
  orcid: 0000-0002-1494-0568
citation:
  ama: 'Fulek R, Gärtner B, Kupavskii A, Valtr P, Wagner U. The crossing Tverberg
    theorem. In: <i>35th International Symposium on Computational Geometry</i>. Vol
    129. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2019:38:1-38:13. doi:<a
    href="https://doi.org/10.4230/LIPICS.SOCG.2019.38">10.4230/LIPICS.SOCG.2019.38</a>'
  apa: 'Fulek, R., Gärtner, B., Kupavskii, A., Valtr, P., &#38; Wagner, U. (2019).
    The crossing Tverberg theorem. In <i>35th International Symposium on Computational
    Geometry</i> (Vol. 129, p. 38:1-38:13). Portland, OR, United States: Schloss Dagstuhl
    - Leibniz-Zentrum für Informatik. <a href="https://doi.org/10.4230/LIPICS.SOCG.2019.38">https://doi.org/10.4230/LIPICS.SOCG.2019.38</a>'
  chicago: Fulek, Radoslav, Bernd Gärtner, Andrey Kupavskii, Pavel Valtr, and Uli
    Wagner. “The Crossing Tverberg Theorem.” In <i>35th International Symposium on
    Computational Geometry</i>, 129:38:1-38:13. Schloss Dagstuhl - Leibniz-Zentrum
    für Informatik, 2019. <a href="https://doi.org/10.4230/LIPICS.SOCG.2019.38">https://doi.org/10.4230/LIPICS.SOCG.2019.38</a>.
  ieee: R. Fulek, B. Gärtner, A. Kupavskii, P. Valtr, and U. Wagner, “The crossing
    Tverberg theorem,” in <i>35th International Symposium on Computational Geometry</i>,
    Portland, OR, United States, 2019, vol. 129, p. 38:1-38:13.
  ista: 'Fulek R, Gärtner B, Kupavskii A, Valtr P, Wagner U. 2019. The crossing Tverberg
    theorem. 35th International Symposium on Computational Geometry. SoCG 2019: Symposium
    on Computational Geometry, LIPIcs, vol. 129, 38:1-38:13.'
  mla: Fulek, Radoslav, et al. “The Crossing Tverberg Theorem.” <i>35th International
    Symposium on Computational Geometry</i>, vol. 129, Schloss Dagstuhl - Leibniz-Zentrum
    für Informatik, 2019, p. 38:1-38:13, doi:<a href="https://doi.org/10.4230/LIPICS.SOCG.2019.38">10.4230/LIPICS.SOCG.2019.38</a>.
  short: R. Fulek, B. Gärtner, A. Kupavskii, P. Valtr, U. Wagner, in:, 35th International
    Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
    2019, p. 38:1-38:13.
conference:
  end_date: 2019-06-21
  location: Portland, OR, United States
  name: 'SoCG 2019: Symposium on Computational Geometry'
  start_date: 2019-06-18
date_created: 2019-07-17T10:35:04Z
date_published: 2019-06-01T00:00:00Z
date_updated: 2023-12-13T12:03:35Z
day: '01'
ddc:
- '000'
- '510'
department:
- _id: UlWa
doi: 10.4230/LIPICS.SOCG.2019.38
external_id:
  arxiv:
  - '1812.04911'
file:
- access_level: open_access
  checksum: d6d017f8b41291b94d102294fa96ae9c
  content_type: application/pdf
  creator: dernst
  date_created: 2019-07-24T06:54:52Z
  date_updated: 2020-07-14T12:47:35Z
  file_id: '6667'
  file_name: 2019_LIPICS_Fulek.pdf
  file_size: 559837
  relation: main_file
file_date_updated: 2020-07-14T12:47:35Z
has_accepted_license: '1'
intvolume: '       129'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: 38:1-38:13
project:
- _id: 261FA626-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: M02281
  name: Eliminating intersections in drawings of graphs
publication: 35th International Symposium on Computational Geometry
publication_identifier:
  isbn:
  - '9783959771047'
  issn:
  - 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
related_material:
  record:
  - id: '13974'
    relation: later_version
    status: public
scopus_import: 1
status: public
title: The crossing Tverberg theorem
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: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 129
year: '2019'
...
---
_id: '6648'
abstract:
- lang: eng
  text: "Various kinds of data are routinely represented as discrete probability distributions.
    Examples include text documents summarized by histograms of word occurrences and
    images represented as histograms of oriented gradients. Viewing a discrete probability
    distribution as a point in the standard simplex of the appropriate dimension,
    we can understand collections of such objects in geometric and topological terms.
    Importantly, instead of using the standard Euclidean distance, we look into dissimilarity
    measures with information-theoretic justification, and we develop the theory\r\nneeded
    for applying topological data analysis in this setting. In doing so, we emphasize
    constructions that enable the usage of existing computational topology software
    in this context."
alternative_title:
- LIPIcs
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: Ziga
  full_name: Virk, Ziga
  last_name: Virk
- first_name: Hubert
  full_name: Wagner, Hubert
  id: 379CA8B8-F248-11E8-B48F-1D18A9856A87
  last_name: Wagner
citation:
  ama: 'Edelsbrunner H, Virk Z, Wagner H. Topological data analysis in information
    space. In: <i>35th International Symposium on Computational Geometry</i>. Vol
    129. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2019:31:1-31:14. doi:<a
    href="https://doi.org/10.4230/LIPICS.SOCG.2019.31">10.4230/LIPICS.SOCG.2019.31</a>'
  apa: 'Edelsbrunner, H., Virk, Z., &#38; Wagner, H. (2019). Topological data analysis
    in information space. In <i>35th International Symposium on Computational Geometry</i>
    (Vol. 129, p. 31:1-31:14). Portland, OR, United States: Schloss Dagstuhl - Leibniz-Zentrum
    für Informatik. <a href="https://doi.org/10.4230/LIPICS.SOCG.2019.31">https://doi.org/10.4230/LIPICS.SOCG.2019.31</a>'
  chicago: Edelsbrunner, Herbert, Ziga Virk, and Hubert Wagner. “Topological Data
    Analysis in Information Space.” In <i>35th International Symposium on Computational
    Geometry</i>, 129:31:1-31:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
    2019. <a href="https://doi.org/10.4230/LIPICS.SOCG.2019.31">https://doi.org/10.4230/LIPICS.SOCG.2019.31</a>.
  ieee: H. Edelsbrunner, Z. Virk, and H. Wagner, “Topological data analysis in information
    space,” in <i>35th International Symposium on Computational Geometry</i>, Portland,
    OR, United States, 2019, vol. 129, p. 31:1-31:14.
  ista: 'Edelsbrunner H, Virk Z, Wagner H. 2019. Topological data analysis in information
    space. 35th International Symposium on Computational Geometry. SoCG 2019: Symposium
    on Computational Geometry, LIPIcs, vol. 129, 31:1-31:14.'
  mla: Edelsbrunner, Herbert, et al. “Topological Data Analysis in Information Space.”
    <i>35th International Symposium on Computational Geometry</i>, vol. 129, Schloss
    Dagstuhl - Leibniz-Zentrum für Informatik, 2019, p. 31:1-31:14, doi:<a href="https://doi.org/10.4230/LIPICS.SOCG.2019.31">10.4230/LIPICS.SOCG.2019.31</a>.
  short: H. Edelsbrunner, Z. Virk, H. Wagner, in:, 35th International Symposium on
    Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019,
    p. 31:1-31:14.
conference:
  end_date: 2019-06-21
  location: Portland, OR, United States
  name: 'SoCG 2019: Symposium on Computational Geometry'
  start_date: 2019-06-18
date_created: 2019-07-17T10:36:09Z
date_published: 2019-06-01T00:00:00Z
date_updated: 2021-01-12T08:08:23Z
day: '01'
ddc:
- '510'
department:
- _id: HeEd
doi: 10.4230/LIPICS.SOCG.2019.31
external_id:
  arxiv:
  - '1903.08510'
file:
- access_level: open_access
  checksum: 8ec8720730d4c789bf7b06540f1c29f4
  content_type: application/pdf
  creator: dernst
  date_created: 2019-07-24T06:40:01Z
  date_updated: 2020-07-14T12:47:35Z
  file_id: '6666'
  file_name: 2019_LIPICS_Edelsbrunner.pdf
  file_size: 1355179
  relation: main_file
file_date_updated: 2020-07-14T12:47:35Z
has_accepted_license: '1'
intvolume: '       129'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: 31:1-31:14
project:
- _id: 2561EBF4-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: I02979-N35
  name: Persistence and stability of geometric complexes
publication: 35th International Symposium on Computational Geometry
publication_identifier:
  isbn:
  - '9783959771047'
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: 1
status: public
title: Topological data analysis in information space
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: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 129
year: '2019'
...