[{"page":"38:1-38:13","quality_controlled":"1","file_date_updated":"2020-07-14T12:47:35Z","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","_id":"6647","scopus_import":1,"author":[{"id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-8485-1774","full_name":"Fulek, Radoslav","first_name":"Radoslav","last_name":"Fulek"},{"first_name":"Bernd","last_name":"Gärtner","full_name":"Gärtner, Bernd"},{"last_name":"Kupavskii","first_name":"Andrey","full_name":"Kupavskii, Andrey"},{"last_name":"Valtr","first_name":"Pavel","full_name":"Valtr, Pavel"},{"id":"36690CA2-F248-11E8-B48F-1D18A9856A87","first_name":"Uli","last_name":"Wagner","orcid":"0000-0002-1494-0568","full_name":"Wagner, Uli"}],"publication_status":"published","department":[{"_id":"UlWa"}],"date_created":"2019-07-17T10:35:04Z","title":"The crossing Tverberg theorem","alternative_title":["LIPIcs"],"intvolume":"       129","volume":129,"ddc":["000","510"],"date_updated":"2023-12-13T12:03:35Z","year":"2019","citation":{"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.","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.","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>","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>"},"external_id":{"arxiv":["1812.04911"]},"arxiv":1,"doi":"10.4230/LIPICS.SOCG.2019.38","day":"01","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."}],"language":[{"iso":"eng"}],"conference":{"location":"Portland, OR, United States","end_date":"2019-06-21","name":"SoCG 2019: Symposium on Computational Geometry","start_date":"2019-06-18"},"publication":"35th International Symposium on Computational Geometry","has_accepted_license":"1","oa_version":"Published Version","project":[{"_id":"261FA626-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","name":"Eliminating intersections in drawings of graphs","grant_number":"M02281"}],"month":"06","file":[{"creator":"dernst","file_id":"6667","relation":"main_file","access_level":"open_access","content_type":"application/pdf","file_name":"2019_LIPICS_Fulek.pdf","date_updated":"2020-07-14T12:47:35Z","checksum":"d6d017f8b41291b94d102294fa96ae9c","file_size":559837,"date_created":"2019-07-24T06:54:52Z"}],"status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","related_material":{"record":[{"status":"public","id":"13974","relation":"later_version"}]},"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"date_published":"2019-06-01T00:00:00Z","type":"conference","publication_identifier":{"issn":["1868-8969"],"isbn":["9783959771047"]},"oa":1},{"author":[{"orcid":"0000-0002-9823-6833","full_name":"Edelsbrunner, Herbert","first_name":"Herbert","last_name":"Edelsbrunner","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Virk, Ziga","last_name":"Virk","first_name":"Ziga"},{"full_name":"Wagner, Hubert","last_name":"Wagner","first_name":"Hubert","id":"379CA8B8-F248-11E8-B48F-1D18A9856A87"}],"scopus_import":1,"_id":"6648","intvolume":"       129","alternative_title":["LIPIcs"],"title":"Topological data analysis in information space","department":[{"_id":"HeEd"}],"date_created":"2019-07-17T10:36:09Z","publication_status":"published","file_date_updated":"2020-07-14T12:47:35Z","quality_controlled":"1","page":"31:1-31:14","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","external_id":{"arxiv":["1903.08510"]},"citation":{"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.","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>.","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>","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>","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.","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.","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>."},"year":"2019","date_updated":"2021-01-12T08:08:23Z","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."}],"day":"01","arxiv":1,"doi":"10.4230/LIPICS.SOCG.2019.31","ddc":["510"],"volume":129,"has_accepted_license":"1","publication":"35th International Symposium on Computational Geometry","month":"06","project":[{"grant_number":"I02979-N35","name":"Persistence and stability of geometric complexes","_id":"2561EBF4-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"}],"oa_version":"Published Version","language":[{"iso":"eng"}],"conference":{"name":"SoCG 2019: Symposium on Computational Geometry","start_date":"2019-06-18","end_date":"2019-06-21","location":"Portland, OR, United States"},"type":"conference","date_published":"2019-06-01T00:00:00Z","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"oa":1,"publication_identifier":{"isbn":["9783959771047"]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","status":"public","file":[{"checksum":"8ec8720730d4c789bf7b06540f1c29f4","file_size":1355179,"date_created":"2019-07-24T06:40:01Z","file_name":"2019_LIPICS_Edelsbrunner.pdf","content_type":"application/pdf","date_updated":"2020-07-14T12:47:35Z","relation":"main_file","access_level":"open_access","creator":"dernst","file_id":"6666"}]}]