[{"project":[{"_id":"B67AFEDC-15C9-11EA-A837-991A96BB2854","name":"IST Austria Open Access Fund"},{"call_identifier":"H2020","_id":"266A2E9E-B435-11E9-9278-68D0E5697425","name":"Alpha Shape Theory Extended","grant_number":"788183"},{"call_identifier":"FWF","_id":"2561EBF4-B435-11E9-9278-68D0E5697425","name":"Persistence and stability of geometric complexes","grant_number":"I02979-N35"}],"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","citation":{"ista":"Edelsbrunner H, Ölsböck K. 2020. Tri-partitions and bases of an ordered complex. Discrete and Computational Geometry. 64, 759–775.","chicago":"Edelsbrunner, Herbert, and Katharina Ölsböck. “Tri-Partitions and Bases of an Ordered Complex.” Discrete and Computational Geometry. Springer Nature, 2020. https://doi.org/10.1007/s00454-020-00188-x.","apa":"Edelsbrunner, H., & Ölsböck, K. (2020). Tri-partitions and bases of an ordered complex. Discrete and Computational Geometry. Springer Nature. https://doi.org/10.1007/s00454-020-00188-x","ama":"Edelsbrunner H, Ölsböck K. Tri-partitions and bases of an ordered complex. Discrete and Computational Geometry. 2020;64:759-775. doi:10.1007/s00454-020-00188-x","ieee":"H. Edelsbrunner and K. Ölsböck, “Tri-partitions and bases of an ordered complex,” Discrete and Computational Geometry, vol. 64. Springer Nature, pp. 759–775, 2020.","short":"H. Edelsbrunner, K. Ölsböck, Discrete and Computational Geometry 64 (2020) 759–775.","mla":"Edelsbrunner, Herbert, and Katharina Ölsböck. “Tri-Partitions and Bases of an Ordered Complex.” Discrete and Computational Geometry, vol. 64, Springer Nature, 2020, pp. 759–75, doi:10.1007/s00454-020-00188-x."},"title":"Tri-partitions and bases of an ordered complex","external_id":{"isi":["000520918800001"]},"article_processing_charge":"Yes (via OA deal)","author":[{"first_name":"Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","last_name":"Edelsbrunner","full_name":"Edelsbrunner, Herbert","orcid":"0000-0002-9823-6833"},{"id":"4D4AA390-F248-11E8-B48F-1D18A9856A87","first_name":"Katharina","orcid":"0000-0002-4672-8297","full_name":"Ölsböck, Katharina","last_name":"Ölsböck"}],"acknowledgement":"This project has received funding from the European Research Council under the European Union’s Horizon 2020 research and innovation programme (Grant Agreement No. 78818 Alpha). It is also partially supported by the DFG Collaborative Research Center TRR 109, ‘Discretization in Geometry and Dynamics’, through Grant No. I02979-N35 of the Austrian Science Fund (FWF).","oa":1,"quality_controlled":"1","publisher":"Springer Nature","publication":"Discrete and Computational Geometry","day":"20","year":"2020","isi":1,"has_accepted_license":"1","date_created":"2020-04-19T22:00:56Z","date_published":"2020-03-20T00:00:00Z","doi":"10.1007/s00454-020-00188-x","page":"759-775","_id":"7666","status":"public","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"article_type":"original","type":"journal_article","ddc":["510"],"date_updated":"2023-08-21T06:13:48Z","file_date_updated":"2020-11-20T13:22:21Z","department":[{"_id":"HeEd"}],"oa_version":"Published Version","abstract":[{"text":"Generalizing the decomposition of a connected planar graph into a tree and a dual tree, we prove a combinatorial analog of the classic Helmholtz–Hodge decomposition of a smooth vector field. Specifically, we show that for every polyhedral complex, K, and every dimension, p, there is a partition of the set of p-cells into a maximal p-tree, a maximal p-cotree, and a collection of p-cells whose cardinality is the p-th reduced Betti number of K. Given an ordering of the p-cells, this tri-partition is unique, and it can be computed by a matrix reduction algorithm that also constructs canonical bases of cycle and boundary groups.","lang":"eng"}],"intvolume":" 64","month":"03","scopus_import":"1","language":[{"iso":"eng"}],"file":[{"file_size":701673,"date_updated":"2020-11-20T13:22:21Z","creator":"dernst","file_name":"2020_DiscreteCompGeo_Edelsbrunner.pdf","date_created":"2020-11-20T13:22:21Z","content_type":"application/pdf","relation":"main_file","access_level":"open_access","success":1,"file_id":"8786","checksum":"f8cc96e497f00c38340b5dafe0cb91d7"}],"publication_status":"published","publication_identifier":{"eissn":["14320444"],"issn":["01795376"]},"ec_funded":1,"volume":64},{"external_id":{"arxiv":["1907.00885"],"isi":["000537329400001"]},"article_processing_charge":"No","author":[{"first_name":"Gil","full_name":"Kalai, Gil","last_name":"Kalai"},{"last_name":"Patakova","orcid":"0000-0002-3975-1683","full_name":"Patakova, Zuzana","first_name":"Zuzana","id":"48B57058-F248-11E8-B48F-1D18A9856A87"}],"title":"Intersection patterns of planar sets","citation":{"mla":"Kalai, Gil, and Zuzana Patakova. “Intersection Patterns of Planar Sets.” Discrete and Computational Geometry, vol. 64, Springer Nature, 2020, pp. 304–23, doi:10.1007/s00454-020-00205-z.","ama":"Kalai G, Patakova Z. Intersection patterns of planar sets. Discrete and Computational Geometry. 2020;64:304-323. doi:10.1007/s00454-020-00205-z","apa":"Kalai, G., & Patakova, Z. (2020). Intersection patterns of planar sets. Discrete and Computational Geometry. Springer Nature. https://doi.org/10.1007/s00454-020-00205-z","ieee":"G. Kalai and Z. Patakova, “Intersection patterns of planar sets,” Discrete and Computational Geometry, vol. 64. Springer Nature, pp. 304–323, 2020.","short":"G. Kalai, Z. Patakova, Discrete and Computational Geometry 64 (2020) 304–323.","chicago":"Kalai, Gil, and Zuzana Patakova. “Intersection Patterns of Planar Sets.” Discrete and Computational Geometry. Springer Nature, 2020. https://doi.org/10.1007/s00454-020-00205-z.","ista":"Kalai G, Patakova Z. 2020. Intersection patterns of planar sets. Discrete and Computational Geometry. 64, 304–323."},"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","oa":1,"quality_controlled":"1","publisher":"Springer Nature","acknowledgement":"We are very grateful to Pavel Paták for many helpful discussions and remarks. We also thank the referees for helpful comments, which greatly improved the presentation.\r\nThe project was supported by ERC Advanced Grant 320924. GK was also partially supported by NSF grant DMS1300120. The research stay of ZP at IST Austria is funded by the project CZ.02.2.69/0.0/0.0/17_050/0008466 Improvement of internationalization in the field of research and development at Charles University, through the support of quality projects MSCA-IF.","page":"304-323","date_created":"2020-06-14T22:00:50Z","date_published":"2020-09-01T00:00:00Z","doi":"10.1007/s00454-020-00205-z","year":"2020","isi":1,"publication":"Discrete and Computational Geometry","day":"01","article_type":"original","type":"journal_article","status":"public","_id":"7960","department":[{"_id":"UlWa"}],"date_updated":"2023-08-21T08:26:34Z","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1907.00885"}],"scopus_import":"1","intvolume":" 64","month":"09","abstract":[{"lang":"eng","text":"Let A={A1,…,An} be a family of sets in the plane. For 0≤i2b be integers. We prove that if each k-wise or (k+1)-wise intersection of sets from A has at most b path-connected components, which all are open, then fk+1=0 implies fk≤cfk−1 for some positive constant c depending only on b and k. These results also extend to two-dimensional compact surfaces."}],"oa_version":"Preprint","volume":64,"publication_status":"published","publication_identifier":{"issn":["01795376"],"eissn":["14320444"]},"language":[{"iso":"eng"}]},{"date_updated":"2023-08-21T08:49:18Z","department":[{"_id":"HeEd"}],"_id":"7962","type":"journal_article","article_type":"original","status":"public","publication_identifier":{"issn":["01795376"],"eissn":["14320444"]},"publication_status":"published","language":[{"iso":"eng"}],"volume":63,"issue":"4","abstract":[{"lang":"eng","text":"A string graph is the intersection graph of a family of continuous arcs in the plane. The intersection graph of a family of plane convex sets is a string graph, but not all string graphs can be obtained in this way. We prove the following structure theorem conjectured by Janson and Uzzell: The vertex set of almost all string graphs on n vertices can be partitioned into five cliques such that some pair of them is not connected by any edge (n→∞). We also show that every graph with the above property is an intersection graph of plane convex sets. As a corollary, we obtain that almost all string graphs on n vertices are intersection graphs of plane convex sets."}],"oa_version":"Preprint","scopus_import":"1","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1803.06710"}],"month":"06","intvolume":" 63","citation":{"mla":"Pach, János, et al. “Almost All String Graphs Are Intersection Graphs of Plane Convex Sets.” Discrete and Computational Geometry, vol. 63, no. 4, Springer Nature, 2020, pp. 888–917, doi:10.1007/s00454-020-00213-z.","ieee":"J. Pach, B. Reed, and Y. Yuditsky, “Almost all string graphs are intersection graphs of plane convex sets,” Discrete and Computational Geometry, vol. 63, no. 4. Springer Nature, pp. 888–917, 2020.","short":"J. Pach, B. Reed, Y. Yuditsky, Discrete and Computational Geometry 63 (2020) 888–917.","apa":"Pach, J., Reed, B., & Yuditsky, Y. (2020). Almost all string graphs are intersection graphs of plane convex sets. Discrete and Computational Geometry. Springer Nature. https://doi.org/10.1007/s00454-020-00213-z","ama":"Pach J, Reed B, Yuditsky Y. Almost all string graphs are intersection graphs of plane convex sets. Discrete and Computational Geometry. 2020;63(4):888-917. doi:10.1007/s00454-020-00213-z","chicago":"Pach, János, Bruce Reed, and Yelena Yuditsky. “Almost All String Graphs Are Intersection Graphs of Plane Convex Sets.” Discrete and Computational Geometry. Springer Nature, 2020. https://doi.org/10.1007/s00454-020-00213-z.","ista":"Pach J, Reed B, Yuditsky Y. 2020. Almost all string graphs are intersection graphs of plane convex sets. Discrete and Computational Geometry. 63(4), 888–917."},"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","author":[{"full_name":"Pach, János","last_name":"Pach","id":"E62E3130-B088-11EA-B919-BF823C25FEA4","first_name":"János"},{"first_name":"Bruce","full_name":"Reed, Bruce","last_name":"Reed"},{"first_name":"Yelena","full_name":"Yuditsky, Yelena","last_name":"Yuditsky"}],"article_processing_charge":"No","external_id":{"arxiv":["1803.06710"],"isi":["000538229000001"]},"title":"Almost all string graphs are intersection graphs of plane convex sets","project":[{"grant_number":"Z00342","name":"The Wittgenstein Prize","call_identifier":"FWF","_id":"268116B8-B435-11E9-9278-68D0E5697425"}],"isi":1,"year":"2020","day":"05","publication":"Discrete and Computational Geometry","page":"888-917","doi":"10.1007/s00454-020-00213-z","date_published":"2020-06-05T00:00:00Z","date_created":"2020-06-14T22:00:51Z","quality_controlled":"1","publisher":"Springer Nature","oa":1},{"publisher":"Springer Nature","oa":1,"page":"571-574","date_published":"2020-10-01T00:00:00Z","doi":"10.1007/s00454-020-00237-5","date_created":"2020-08-30T22:01:12Z","isi":1,"year":"2020","day":"01","publication":"Discrete and Computational Geometry","author":[{"first_name":"János","id":"E62E3130-B088-11EA-B919-BF823C25FEA4","last_name":"Pach","full_name":"Pach, János"}],"external_id":{"isi":["000561483500001"]},"article_processing_charge":"No","title":"A farewell to Ricky Pollack","citation":{"mla":"Pach, János. “A Farewell to Ricky Pollack.” Discrete and Computational Geometry, vol. 64, Springer Nature, 2020, pp. 571–74, doi:10.1007/s00454-020-00237-5.","ama":"Pach J. A farewell to Ricky Pollack. Discrete and Computational Geometry. 2020;64:571-574. doi:10.1007/s00454-020-00237-5","apa":"Pach, J. (2020). A farewell to Ricky Pollack. Discrete and Computational Geometry. Springer Nature. https://doi.org/10.1007/s00454-020-00237-5","ieee":"J. Pach, “A farewell to Ricky Pollack,” Discrete and Computational Geometry, vol. 64. Springer Nature, pp. 571–574, 2020.","short":"J. Pach, Discrete and Computational Geometry 64 (2020) 571–574.","chicago":"Pach, János. “A Farewell to Ricky Pollack.” Discrete and Computational Geometry. Springer Nature, 2020. https://doi.org/10.1007/s00454-020-00237-5.","ista":"Pach J. 2020. A farewell to Ricky Pollack. Discrete and Computational Geometry. 64, 571–574."},"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","scopus_import":"1","main_file_link":[{"open_access":"1","url":"https://doi.org/10.1007/s00454-020-00237-5"}],"month":"10","intvolume":" 64","oa_version":"None","volume":64,"publication_identifier":{"issn":["01795376"],"eissn":["14320444"]},"publication_status":"published","language":[{"iso":"eng"}],"article_type":"letter_note","type":"journal_article","status":"public","_id":"8323","department":[{"_id":"HeEd"}],"date_updated":"2023-08-22T09:05:04Z"},{"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","citation":{"mla":"Edelsbrunner, Herbert, and Anton Nikitenko. “Poisson–Delaunay Mosaics of Order K.” Discrete and Computational Geometry, vol. 62, no. 4, Springer, 2019, pp. 865–878, doi:10.1007/s00454-018-0049-2.","ama":"Edelsbrunner H, Nikitenko A. Poisson–Delaunay Mosaics of Order k. Discrete and Computational Geometry. 2019;62(4):865–878. doi:10.1007/s00454-018-0049-2","apa":"Edelsbrunner, H., & Nikitenko, A. (2019). Poisson–Delaunay Mosaics of Order k. Discrete and Computational Geometry. Springer. https://doi.org/10.1007/s00454-018-0049-2","ieee":"H. Edelsbrunner and A. Nikitenko, “Poisson–Delaunay Mosaics of Order k,” Discrete and Computational Geometry, vol. 62, no. 4. Springer, pp. 865–878, 2019.","short":"H. Edelsbrunner, A. Nikitenko, Discrete and Computational Geometry 62 (2019) 865–878.","chicago":"Edelsbrunner, Herbert, and Anton Nikitenko. “Poisson–Delaunay Mosaics of Order K.” Discrete and Computational Geometry. Springer, 2019. https://doi.org/10.1007/s00454-018-0049-2.","ista":"Edelsbrunner H, Nikitenko A. 2019. Poisson–Delaunay Mosaics of Order k. Discrete and Computational Geometry. 62(4), 865–878."},"title":"Poisson–Delaunay Mosaics of Order k","external_id":{"isi":["000494042900008"],"arxiv":["1709.09380"]},"article_processing_charge":"Yes (via OA deal)","author":[{"last_name":"Edelsbrunner","full_name":"Edelsbrunner, Herbert","orcid":"0000-0002-9823-6833","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","first_name":"Herbert"},{"last_name":"Nikitenko","orcid":"0000-0002-0659-3201","full_name":"Nikitenko, Anton","id":"3E4FF1BA-F248-11E8-B48F-1D18A9856A87","first_name":"Anton"}],"project":[{"call_identifier":"H2020","_id":"266A2E9E-B435-11E9-9278-68D0E5697425","name":"Alpha Shape Theory Extended","grant_number":"788183"},{"name":"Persistence and stability of geometric complexes","grant_number":"I02979-N35","_id":"2561EBF4-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"name":"IST Austria Open Access Fund","_id":"B67AFEDC-15C9-11EA-A837-991A96BB2854"}],"publication":"Discrete and Computational Geometry","day":"01","year":"2019","has_accepted_license":"1","isi":1,"date_created":"2018-12-16T22:59:20Z","date_published":"2019-12-01T00:00:00Z","doi":"10.1007/s00454-018-0049-2","page":"865–878","oa":1,"publisher":"Springer","quality_controlled":"1","ddc":["516"],"date_updated":"2023-09-07T12:07:12Z","file_date_updated":"2020-07-14T12:47:10Z","department":[{"_id":"HeEd"}],"_id":"5678","status":"public","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"type":"journal_article","article_type":"original","language":[{"iso":"eng"}],"file":[{"date_created":"2019-02-06T10:10:46Z","file_name":"2018_DiscreteCompGeometry_Edelsbrunner.pdf","creator":"dernst","date_updated":"2020-07-14T12:47:10Z","file_size":599339,"checksum":"f9d00e166efaccb5a76bbcbb4dcea3b4","file_id":"5932","access_level":"open_access","relation":"main_file","content_type":"application/pdf"}],"publication_status":"published","publication_identifier":{"issn":["01795376"],"eissn":["14320444"]},"ec_funded":1,"issue":"4","volume":62,"related_material":{"record":[{"relation":"dissertation_contains","status":"public","id":"6287"}]},"oa_version":"Published Version","abstract":[{"lang":"eng","text":"The order-k Voronoi tessellation of a locally finite set 𝑋⊆ℝ𝑛 decomposes ℝ𝑛 into convex domains whose points have the same k nearest neighbors in X. Assuming X is a stationary Poisson point process, we give explicit formulas for the expected number and total area of faces of a given dimension per unit volume of space. We also develop a relaxed version of discrete Morse theory and generalize by counting only faces, for which the k nearest points in X are within a given distance threshold."}],"intvolume":" 62","month":"12","scopus_import":"1"},{"year":"2018","isi":1,"has_accepted_license":"1","publication":"Discrete & Computational Geometry","day":"01","page":"1001-1009","date_created":"2018-12-11T11:49:57Z","doi":"10.1007/s00454-017-9883-x","date_published":"2018-06-01T00:00:00Z","oa":1,"quality_controlled":"1","publisher":"Springer","citation":{"ieee":"A. Akopyan, A. Balitskiy, and M. Grigorev, “On the circle covering theorem by A.W. Goodman and R.E. Goodman,” Discrete & Computational Geometry, vol. 59, no. 4. Springer, pp. 1001–1009, 2018.","short":"A. Akopyan, A. Balitskiy, M. Grigorev, Discrete & Computational Geometry 59 (2018) 1001–1009.","apa":"Akopyan, A., Balitskiy, A., & Grigorev, M. (2018). On the circle covering theorem by A.W. Goodman and R.E. Goodman. Discrete & Computational Geometry. Springer. https://doi.org/10.1007/s00454-017-9883-x","ama":"Akopyan A, Balitskiy A, Grigorev M. On the circle covering theorem by A.W. Goodman and R.E. Goodman. Discrete & Computational Geometry. 2018;59(4):1001-1009. doi:10.1007/s00454-017-9883-x","mla":"Akopyan, Arseniy, et al. “On the Circle Covering Theorem by A.W. Goodman and R.E. Goodman.” Discrete & Computational Geometry, vol. 59, no. 4, Springer, 2018, pp. 1001–09, doi:10.1007/s00454-017-9883-x.","ista":"Akopyan A, Balitskiy A, Grigorev M. 2018. On the circle covering theorem by A.W. Goodman and R.E. Goodman. Discrete & Computational Geometry. 59(4), 1001–1009.","chicago":"Akopyan, Arseniy, Alexey Balitskiy, and Mikhail Grigorev. “On the Circle Covering Theorem by A.W. Goodman and R.E. Goodman.” Discrete & Computational Geometry. Springer, 2018. https://doi.org/10.1007/s00454-017-9883-x."},"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","external_id":{"isi":["000432205500011"]},"article_processing_charge":"Yes (via OA deal)","publist_id":"6324","author":[{"first_name":"Arseniy","id":"430D2C90-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-2548-617X","full_name":"Akopyan, Arseniy","last_name":"Akopyan"},{"first_name":"Alexey","last_name":"Balitskiy","full_name":"Balitskiy, Alexey"},{"last_name":"Grigorev","full_name":"Grigorev, Mikhail","first_name":"Mikhail"}],"title":"On the circle covering theorem by A.W. Goodman and R.E. Goodman","project":[{"call_identifier":"FP7","_id":"25681D80-B435-11E9-9278-68D0E5697425","name":"International IST Postdoc Fellowship Programme","grant_number":"291734"}],"publication_status":"published","publication_identifier":{"issn":["01795376"],"eissn":["14320444"]},"language":[{"iso":"eng"}],"file":[{"content_type":"application/pdf","relation":"main_file","access_level":"open_access","success":1,"file_id":"5844","file_size":482518,"date_updated":"2019-01-18T09:27:36Z","creator":"dernst","file_name":"2018_DiscreteComp_Akopyan.pdf","date_created":"2019-01-18T09:27:36Z"}],"ec_funded":1,"issue":"4","volume":59,"abstract":[{"lang":"eng","text":"In 1945, A.W. Goodman and R.E. Goodman proved the following conjecture by P. Erdős: Given a family of (round) disks of radii r1, … , rn in the plane, it is always possible to cover them by a disk of radius R= ∑ ri, provided they cannot be separated into two subfamilies by a straight line disjoint from the disks. In this note we show that essentially the same idea may work for different analogues and generalizations of their result. In particular, we prove the following: Given a family of positive homothetic copies of a fixed convex body K⊂ Rd with homothety coefficients τ1, … , τn> 0 , it is always possible to cover them by a translate of d+12(∑τi)K, provided they cannot be separated into two subfamilies by a hyperplane disjoint from the homothets."}],"oa_version":"Published Version","scopus_import":"1","intvolume":" 59","month":"06","date_updated":"2023-09-20T12:08:51Z","ddc":["516","000"],"file_date_updated":"2019-01-18T09:27:36Z","department":[{"_id":"HeEd"}],"_id":"1064","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"type":"journal_article","article_type":"original","status":"public"}]