[{"scopus_import":"1","file":[{"access_level":"open_access","success":1,"checksum":"a8f7feb1aa3b896e31195841a989d622","relation":"main_file","content_type":"application/pdf","file_name":"2025_LIPIcs.SoCG_Streltsova.pdf","date_created":"2025-07-14T07:11:04Z","file_id":"20015","creator":"dernst","file_size":952807,"date_updated":"2025-07-14T07:11:04Z"}],"citation":{"ista":"Streltsova E, Wagner U. 2025. Levels in arrangements: Linear relations, the g-matrix, and applications to crossing numbers.  41st International Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 332, 75.","short":"E. Streltsova, U. Wagner, in:,  41st International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025.","mla":"Streltsova, Elizaveta, and Uli Wagner. “Levels in Arrangements: Linear Relations, the g-Matrix, and Applications to Crossing Numbers.” <i> 41st International Symposium on Computational Geometry</i>, vol. 332, 75, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2025.75\">10.4230/LIPIcs.SoCG.2025.75</a>.","chicago":"Streltsova, Elizaveta, and Uli Wagner. “Levels in Arrangements: Linear Relations, the g-Matrix, and Applications to Crossing Numbers.” In <i> 41st International Symposium on Computational Geometry</i>, Vol. 332. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2025.75\">https://doi.org/10.4230/LIPIcs.SoCG.2025.75</a>.","apa":"Streltsova, E., &#38; Wagner, U. (2025). Levels in arrangements: Linear relations, the g-matrix, and applications to crossing numbers. In <i> 41st International Symposium on Computational Geometry</i> (Vol. 332). Kanazawa, Japan: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2025.75\">https://doi.org/10.4230/LIPIcs.SoCG.2025.75</a>","ama":"Streltsova E, Wagner U. Levels in arrangements: Linear relations, the g-matrix, and applications to crossing numbers. In: <i> 41st International Symposium on Computational Geometry</i>. Vol 332. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2025. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2025.75\">10.4230/LIPIcs.SoCG.2025.75</a>","ieee":"E. Streltsova and U. Wagner, “Levels in arrangements: Linear relations, the g-matrix, and applications to crossing numbers,” in <i> 41st International Symposium on Computational Geometry</i>, Kanazawa, Japan, 2025, vol. 332."},"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png"},"status":"public","quality_controlled":"1","language":[{"iso":"eng"}],"oa_version":"Published Version","arxiv":1,"doi":"10.4230/LIPIcs.SoCG.2025.75","day":"20","department":[{"_id":"UlWa"}],"publication_status":"published","corr_author":"1","month":"06","date_updated":"2025-07-14T07:19:19Z","type":"conference","license":"https://creativecommons.org/licenses/by/4.0/","file_date_updated":"2025-07-14T07:11:04Z","publication_identifier":{"eissn":["1868-8969"],"isbn":["9783959773706"]},"date_created":"2025-07-13T22:01:22Z","publication":" 41st International Symposium on Computational Geometry","abstract":[{"text":"A long-standing conjecture of Eckhoff, Linhart, and Welzl, which would generalize McMullen’s Upper Bound Theorem for polytopes and refine asymptotic bounds due to Clarkson, asserts that for k ⩽ ⌊(n-d-2)/2⌋, the complexity of the (⩽ k)-level in a simple arrangement of n hemispheres in S^d is maximized for arrangements that are polar duals of neighborly d-polytopes. We prove this conjecture in the case n = d+4. By Gale duality, this implies the following result about crossing numbers: In every spherical arc drawing of K_n in S² (given by a set V ⊂ S² of n unit vectors connected by spherical arcs), the number of crossings is at least 1/4 ⌊n/2⌋ ⌊(n-1)/2⌋ ⌊(n-2)/2⌋ ⌊(n-3)/2⌋. This lower bound is attained if every open linear halfspace contains at least ⌊(n-2)/2⌋ of the vectors in V.\r\nMoreover, we determine the space of all linear and affine relations that hold between the face numbers of levels in simple arrangements of n hemispheres in S^d. This completes a long line of research on such relations, answers a question posed by Andrzejak and Welzl in 2003, and generalizes the classical fact that the Dehn-Sommerville relations generate all linear relations between the face numbers of simple polytopes (which correspond to the 0-level).\r\nTo prove these results, we introduce the notion of the g-matrix, which encodes the face numbers of levels in an arrangement and generalizes the classical g-vector of a polytope.","lang":"eng"}],"oa":1,"has_accepted_license":"1","conference":{"start_date":"2025-06-23","name":"SoCG: Symposium on Computational Geometry","end_date":"2025-06-27","location":"Kanazawa, Japan"},"OA_type":"gold","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","title":"Levels in arrangements: Linear relations, the g-matrix, and applications to crossing numbers","OA_place":"publisher","article_number":"75","year":"2025","ddc":["510"],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","article_processing_charge":"Yes","date_published":"2025-06-20T00:00:00Z","volume":332,"intvolume":"       332","author":[{"first_name":"Elizaveta","full_name":"Streltsova, Elizaveta","id":"57a170da-dc96-11ea-b7c8-ab3565071bf7","last_name":"Streltsova"},{"full_name":"Wagner, Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","last_name":"Wagner","orcid":"0000-0002-1494-0568","first_name":"Uli"}],"_id":"20004","external_id":{"arxiv":["2504.07752","2504.07770"]},"alternative_title":["LIPIcs"]},{"status":"public","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png"},"citation":{"mla":"Edelsbrunner, Herbert, et al. “On Spheres with k Points Inside.” <i>41st International Symposium on Computational Geometry</i>, vol. 332, 43, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2025.43\">10.4230/LIPIcs.SoCG.2025.43</a>.","short":"H. Edelsbrunner, A. Garber, M. Saghafian, in:, 41st International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025.","chicago":"Edelsbrunner, Herbert, Alexey Garber, and Morteza Saghafian. “On Spheres with k Points Inside.” In <i>41st International Symposium on Computational Geometry</i>, Vol. 332. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2025.43\">https://doi.org/10.4230/LIPIcs.SoCG.2025.43</a>.","ista":"Edelsbrunner H, Garber A, Saghafian M. 2025. On spheres with k points inside. 41st International Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 332, 43.","ieee":"H. Edelsbrunner, A. Garber, and M. Saghafian, “On spheres with k points inside,” in <i>41st International Symposium on Computational Geometry</i>, Kanazawa, Japan, 2025, vol. 332.","ama":"Edelsbrunner H, Garber A, Saghafian M. On spheres with k points inside. In: <i>41st International Symposium on Computational Geometry</i>. Vol 332. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2025. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2025.43\">10.4230/LIPIcs.SoCG.2025.43</a>","apa":"Edelsbrunner, H., Garber, A., &#38; Saghafian, M. (2025). On spheres with k points inside. In <i>41st International Symposium on Computational Geometry</i> (Vol. 332). Kanazawa, Japan: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2025.43\">https://doi.org/10.4230/LIPIcs.SoCG.2025.43</a>"},"file":[{"creator":"dernst","file_size":661893,"date_updated":"2025-07-14T07:24:22Z","file_name":"2025_LIPIcs.SoCG_Edelsbrunner.pdf","file_id":"20016","date_created":"2025-07-14T07:24:22Z","checksum":"b5313ed8575ea87913c71a6e3c7513c8","relation":"main_file","content_type":"application/pdf","access_level":"open_access","success":1}],"scopus_import":"1","acknowledgement":"Herbert Edelsbrunner: partially supported by the Wittgenstein Prize, Austrian Science\r\nFund (FWF), grant no. Z 342-N31, and by the DFG Collaborative Research Center TRR 109,\r\nAustrian Science Fund (FWF), grant no. I 02979-N35.\r\nAlexey Garber: partially supported by the Simons Foundation.\r\nMorteza Saghafian: partially supported by the Wittgenstein Prize, Austrian Science Fund (FWF),\r\ngrant no. Z 342-N31, and by the DFG Collaborative Research Center TRR 109, Austrian Science\r\nFund (FWF), grant no. I 02979-N35","month":"06","corr_author":"1","publication_status":"published","department":[{"_id":"HeEd"}],"doi":"10.4230/LIPIcs.SoCG.2025.43","day":"20","arxiv":1,"oa_version":"Published Version","language":[{"iso":"eng"}],"quality_controlled":"1","abstract":[{"text":"We generalize a classical result by Boris Delaunay that introduced Delaunay triangulations. In particular, we prove that for a locally finite and coarsely dense generic point set A in ℝ^d, every generic point of ℝ^d belongs to exactly binom(d+k,d) simplices whose vertices belong to A and whose circumspheres enclose exactly k points of A. We extend this result to the cases in which the points are weighted, and when A contains only finitely many points in ℝ^d or in 𝕊^d. Furthermore, we use the result to give a new geometric proof for the fact that volumes of hypersimplices are Eulerian numbers.","lang":"eng"}],"publication":"41st International Symposium on Computational Geometry","date_created":"2025-07-13T22:01:22Z","publication_identifier":{"isbn":["9783959773706"],"eissn":["1868-8969"]},"file_date_updated":"2025-07-14T07:24:22Z","type":"conference","date_updated":"2025-07-14T07:26:14Z","OA_place":"publisher","title":"On spheres with k points inside","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","OA_type":"gold","conference":{"location":"Kanazawa, Japan","end_date":"2025-06-27","name":"SoCG: Symposium on Computational Geometry","start_date":"2025-06-23"},"oa":1,"has_accepted_license":"1","project":[{"call_identifier":"FWF","name":"Mathematics, Computer Science","grant_number":"Z00342","_id":"268116B8-B435-11E9-9278-68D0E5697425"},{"_id":"2561EBF4-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","name":"Persistence and stability of geometric complexes","grant_number":"I02979-N35"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","ddc":["510"],"year":"2025","article_number":"43","date_published":"2025-06-20T00:00:00Z","article_processing_charge":"Yes","intvolume":"       332","volume":332,"alternative_title":["LIPIcs"],"_id":"20005","external_id":{"arxiv":["2410.21204"]},"author":[{"first_name":"Herbert","orcid":"0000-0002-9823-6833","last_name":"Edelsbrunner","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","full_name":"Edelsbrunner, Herbert"},{"last_name":"Garber","full_name":"Garber, Alexey","first_name":"Alexey"},{"last_name":"Saghafian","full_name":"Saghafian, Morteza","id":"f86f7148-b140-11ec-9577-95435b8df824","first_name":"Morteza"}]},{"oa":1,"has_accepted_license":"1","conference":{"start_date":"2025-06-23","name":"SoCG: Symposium on Computational Geometry","end_date":"2025-06-27","location":"Kanazawa, Japan"},"title":"Banana trees for the persistence in time series experimentally","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","OA_type":"gold","OA_place":"publisher","type":"conference","date_updated":"2025-12-30T11:04:33Z","file_date_updated":"2025-07-14T08:23:38Z","publication":"41st International Symposium on Computational Geometry","date_created":"2025-07-13T22:01:22Z","publication_identifier":{"isbn":["9783959773706"],"eissn":["1868-8969"]},"abstract":[{"text":"In numerous fields, dynamic time series data require continuous updates, necessitating efficient data processing techniques for accurate analysis. This paper examines the banana tree data structure, specifically designed to efficiently maintain the multi-scale topological descriptor commonly known as persistent homology for dynamically changing time series data. We implement this data structure and conduct an experimental study to assess its properties and runtime for update operations. Our findings indicate that banana trees are highly effective with unbiased random data, outperforming state-of-the-art static algorithms in these scenarios. Additionally, our results show that real-world time series share structural properties with unbiased random walks, suggesting potential practical utility for our implementation.","lang":"eng"}],"oa_version":"Published Version","language":[{"iso":"eng"}],"quality_controlled":"1","arxiv":1,"publication_status":"published","department":[{"_id":"HeEd"}],"doi":"10.4230/LIPIcs.SoCG.2025.71","day":"20","related_material":{"link":[{"url":"https://github.com/laraost/BananaPersist","relation":"software"}]},"month":"06","corr_author":"1","acknowledgement":"Lara Ost: Supported by the Vienna Graduate School on Computational Optimization\r\n(VGSCO), FWF project no. W1260-N35.\r\nSebastiano Cultrera di Montesano: Supported by the Eric and Wendy Schmidt Center at the Broad Institute of MIT and Harvard.\r\nHerbert Edelsbrunner: Partially supported by the Wittgenstein Prize, FWF grant no. Z 342-N31,\r\nand by the DFG Collaborative Research Center TRR 109, FWF grant no. I 02979-N35.","scopus_import":"1","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png"},"file":[{"file_size":834623,"creator":"dernst","date_updated":"2025-07-14T08:23:38Z","file_name":"2025_LIPIcs.SoCG_Ost.pdf","date_created":"2025-07-14T08:23:38Z","file_id":"20017","relation":"main_file","checksum":"3a4a7a707a56e0cfdf51428782dee55a","content_type":"application/pdf","success":1,"access_level":"open_access"}],"citation":{"ama":"Ost L, Cultrera di Montesano S, Edelsbrunner H. Banana trees for the persistence in time series experimentally. In: <i>41st International Symposium on Computational Geometry</i>. Vol 332. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2025. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2025.71\">10.4230/LIPIcs.SoCG.2025.71</a>","apa":"Ost, L., Cultrera di Montesano, S., &#38; Edelsbrunner, H. (2025). Banana trees for the persistence in time series experimentally. In <i>41st International Symposium on Computational Geometry</i> (Vol. 332). Kanazawa, Japan: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2025.71\">https://doi.org/10.4230/LIPIcs.SoCG.2025.71</a>","ieee":"L. Ost, S. Cultrera di Montesano, and H. Edelsbrunner, “Banana trees for the persistence in time series experimentally,” in <i>41st International Symposium on Computational Geometry</i>, Kanazawa, Japan, 2025, vol. 332.","ista":"Ost L, Cultrera di Montesano S, Edelsbrunner H. 2025. Banana trees for the persistence in time series experimentally. 41st International Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 332, 71.","mla":"Ost, Lara, et al. “Banana Trees for the Persistence in Time Series Experimentally.” <i>41st International Symposium on Computational Geometry</i>, vol. 332, 71, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2025.71\">10.4230/LIPIcs.SoCG.2025.71</a>.","short":"L. Ost, S. Cultrera di Montesano, H. Edelsbrunner, in:, 41st International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025.","chicago":"Ost, Lara, Sebastiano Cultrera di Montesano, and Herbert Edelsbrunner. “Banana Trees for the Persistence in Time Series Experimentally.” In <i>41st International Symposium on Computational Geometry</i>, Vol. 332. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2025.71\">https://doi.org/10.4230/LIPIcs.SoCG.2025.71</a>."},"status":"public","author":[{"full_name":"Ost, Lara","last_name":"Ost","first_name":"Lara"},{"last_name":"Cultrera di Montesano","id":"34D2A09C-F248-11E8-B48F-1D18A9856A87","full_name":"Cultrera di Montesano, Sebastiano","first_name":"Sebastiano","orcid":"0000-0001-6249-0832"},{"orcid":"0000-0002-9823-6833","first_name":"Herbert","last_name":"Edelsbrunner","full_name":"Edelsbrunner, Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87"}],"alternative_title":["LIPIcs"],"external_id":{"arxiv":["2405.17920"]},"_id":"20006","volume":332,"intvolume":"       332","article_processing_charge":"Yes","date_published":"2025-06-20T00:00:00Z","year":"2025","article_number":"71","ddc":["000"],"project":[{"grant_number":"W1260-N35","name":"Vienna Graduate School on Computational Optimization","_id":"9B9290DE-BA93-11EA-9121-9846C619BF3A"},{"call_identifier":"FWF","name":"Persistence and stability of geometric complexes","grant_number":"I02979-N35","_id":"2561EBF4-B435-11E9-9278-68D0E5697425"},{"call_identifier":"FWF","name":"Mathematics, Computer Science","grant_number":"Z00342","_id":"268116B8-B435-11E9-9278-68D0E5697425"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik"}]