[{"date_published":"2024-01-01T00:00:00Z","month":"01","language":[{"iso":"eng"}],"scopus_import":"1","publisher":"Springer Nature","department":[{"_id":"HeEd"}],"date_created":"2024-02-18T23:01:03Z","conference":{"location":"Isola delle Femmine, Palermo, Italy","name":"GD: Graph Drawing and Network Visualization","end_date":"2023-09-22","start_date":"2023-09-20"},"type":"conference","day":"01","status":"public","intvolume":" 14465","page":"339-346","publication":"31st International Symposium on Graph Drawing and Network Visualization","ec_funded":1,"doi":"10.1007/978-3-031-49272-3_23","year":"2024","external_id":{"arxiv":["2306.13201"]},"title":"Decomposition of geometric graphs into star-forests","main_file_link":[{"url":"https://doi.org/10.48550/arXiv.2306.13201","open_access":"1"}],"alternative_title":["LNCS"],"citation":{"short":"J. Pach, M. Saghafian, P. Schnider, in:, 31st International Symposium on Graph Drawing and Network Visualization, Springer Nature, 2024, pp. 339–346.","ista":"Pach J, Saghafian M, Schnider P. 2024. Decomposition of geometric graphs into star-forests. 31st International Symposium on Graph Drawing and Network Visualization. GD: Graph Drawing and Network Visualization, LNCS, vol. 14465, 339–346.","mla":"Pach, János, et al. “Decomposition of Geometric Graphs into Star-Forests.” 31st International Symposium on Graph Drawing and Network Visualization, vol. 14465, Springer Nature, 2024, pp. 339–46, doi:10.1007/978-3-031-49272-3_23.","ama":"Pach J, Saghafian M, Schnider P. Decomposition of geometric graphs into star-forests. In: 31st International Symposium on Graph Drawing and Network Visualization. Vol 14465. Springer Nature; 2024:339-346. doi:10.1007/978-3-031-49272-3_23","chicago":"Pach, János, Morteza Saghafian, and Patrick Schnider. “Decomposition of Geometric Graphs into Star-Forests.” In 31st International Symposium on Graph Drawing and Network Visualization, 14465:339–46. Springer Nature, 2024. https://doi.org/10.1007/978-3-031-49272-3_23.","ieee":"J. Pach, M. Saghafian, and P. Schnider, “Decomposition of geometric graphs into star-forests,” in 31st International Symposium on Graph Drawing and Network Visualization, Isola delle Femmine, Palermo, Italy, 2024, vol. 14465, pp. 339–346.","apa":"Pach, J., Saghafian, M., & Schnider, P. (2024). Decomposition of geometric graphs into star-forests. In 31st International Symposium on Graph Drawing and Network Visualization (Vol. 14465, pp. 339–346). Isola delle Femmine, Palermo, Italy: Springer Nature. https://doi.org/10.1007/978-3-031-49272-3_23"},"publication_status":"published","author":[{"last_name":"Pach","full_name":"Pach, János","first_name":"János","id":"E62E3130-B088-11EA-B919-BF823C25FEA4"},{"first_name":"Morteza","last_name":"Saghafian","full_name":"Saghafian, Morteza","id":"f86f7148-b140-11ec-9577-95435b8df824"},{"first_name":"Patrick","full_name":"Schnider, Patrick","last_name":"Schnider"}],"abstract":[{"text":"We solve a problem of Dujmović and Wood (2007) by showing that a complete convex geometric graph on n vertices cannot be decomposed into fewer than n-1 star-forests, each consisting of noncrossing edges. This bound is clearly tight. We also discuss similar questions for abstract graphs.","lang":"eng"}],"article_processing_charge":"No","volume":14465,"date_updated":"2024-02-20T09:13:07Z","oa":1,"arxiv":1,"oa_version":"Preprint","project":[{"grant_number":"788183","_id":"266A2E9E-B435-11E9-9278-68D0E5697425","name":"Alpha Shape Theory Extended","call_identifier":"H2020"},{"call_identifier":"FWF","_id":"268116B8-B435-11E9-9278-68D0E5697425","name":"The Wittgenstein Prize","grant_number":"Z00342"}],"quality_controlled":"1","acknowledgement":"János Pach’s Research partially supported by European Research Council (ERC), grant “GeoScape” No. 882971 and by the Hungarian Science Foundation (NKFIH), grant K-131529. Work by Morteza Saghafian is partially supported by the European Research Council (ERC), grant No. 788183, and by the Wittgenstein Prize, Austrian Science Fund (FWF), grant No. Z 342-N31.","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication_identifier":{"isbn":["9783031492716"],"issn":["03029743"],"eissn":["16113349"]},"_id":"15012"},{"article_type":"original","date_published":"2023-09-07T00:00:00Z","month":"09","language":[{"iso":"eng"}],"scopus_import":"1","publisher":"Springer Nature","department":[{"_id":"HeEd"}],"date_created":"2023-09-17T22:01:10Z","type":"journal_article","day":"07","status":"public","publication":"Discrete and Computational Geometry","ec_funded":1,"year":"2023","doi":"10.1007/s00454-023-00566-1","external_id":{"arxiv":["2204.01076"],"isi":["001060727600004"]},"title":"On angles in higher order Brillouin tessellations and related tilings in the plane","main_file_link":[{"url":"https://doi.org/10.1007/s00454-023-00566-1","open_access":"1"}],"isi":1,"citation":{"apa":"Edelsbrunner, H., Garber, A., Ghafari, M., Heiss, T., & Saghafian, M. (2023). On angles in higher order Brillouin tessellations and related tilings in the plane. Discrete and Computational Geometry. Springer Nature. https://doi.org/10.1007/s00454-023-00566-1","ieee":"H. Edelsbrunner, A. Garber, M. Ghafari, T. Heiss, and M. Saghafian, “On angles in higher order Brillouin tessellations and related tilings in the plane,” Discrete and Computational Geometry. Springer Nature, 2023.","chicago":"Edelsbrunner, Herbert, Alexey Garber, Mohadese Ghafari, Teresa Heiss, and Morteza Saghafian. “On Angles in Higher Order Brillouin Tessellations and Related Tilings in the Plane.” Discrete and Computational Geometry. Springer Nature, 2023. https://doi.org/10.1007/s00454-023-00566-1.","ama":"Edelsbrunner H, Garber A, Ghafari M, Heiss T, Saghafian M. On angles in higher order Brillouin tessellations and related tilings in the plane. Discrete and Computational Geometry. 2023. doi:10.1007/s00454-023-00566-1","mla":"Edelsbrunner, Herbert, et al. “On Angles in Higher Order Brillouin Tessellations and Related Tilings in the Plane.” Discrete and Computational Geometry, Springer Nature, 2023, doi:10.1007/s00454-023-00566-1.","ista":"Edelsbrunner H, Garber A, Ghafari M, Heiss T, Saghafian M. 2023. On angles in higher order Brillouin tessellations and related tilings in the plane. Discrete and Computational Geometry.","short":"H. Edelsbrunner, A. Garber, M. Ghafari, T. Heiss, M. Saghafian, Discrete and Computational Geometry (2023)."},"publication_status":"epub_ahead","author":[{"id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","first_name":"Herbert","orcid":"0000-0002-9823-6833","last_name":"Edelsbrunner","full_name":"Edelsbrunner, Herbert"},{"first_name":"Alexey","last_name":"Garber","full_name":"Garber, Alexey"},{"first_name":"Mohadese","full_name":"Ghafari, Mohadese","last_name":"Ghafari"},{"first_name":"Teresa","orcid":"0000-0002-1780-2689","full_name":"Heiss, Teresa","last_name":"Heiss","id":"4879BB4E-F248-11E8-B48F-1D18A9856A87"},{"id":"f86f7148-b140-11ec-9577-95435b8df824","first_name":"Morteza","last_name":"Saghafian","full_name":"Saghafian, Morteza"}],"abstract":[{"text":"For a locally finite set in R2, the order-k Brillouin tessellations form an infinite sequence of convex face-to-face tilings of the plane. If the set is coarsely dense and generic, then the corresponding infinite sequences of minimum and maximum angles are both monotonic in k. As an example, a stationary Poisson point process in R2 is locally finite, coarsely dense, and generic with probability one. For such a set, the distributions of angles in the Voronoi tessellations, Delaunay mosaics, and Brillouin tessellations are independent of the order and can be derived from the formula for angles in order-1 Delaunay mosaics given by Miles (Math. Biosci. 6, 85–127 (1970)).","lang":"eng"}],"article_processing_charge":"Yes (via OA deal)","oa":1,"date_updated":"2023-12-13T12:25:06Z","arxiv":1,"quality_controlled":"1","project":[{"call_identifier":"H2020","name":"Alpha Shape Theory Extended","_id":"266A2E9E-B435-11E9-9278-68D0E5697425","grant_number":"788183"},{"grant_number":"Z00342","name":"The Wittgenstein Prize","_id":"268116B8-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"grant_number":"I02979-N35","call_identifier":"FWF","_id":"2561EBF4-B435-11E9-9278-68D0E5697425","name":"Persistence and stability of geometric complexes"}],"oa_version":"Published Version","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","acknowledgement":"Work by all authors but A. Garber is supported by the European Research Council (ERC), Grant No. 788183, by the Wittgenstein Prize, Austrian Science Fund (FWF), Grant No. Z 342-N31, and by the DFG Collaborative Research Center TRR 109, Austrian Science Fund (FWF), Grant No. I 02979-N35. Work by A. Garber is partially supported by the Alexander von Humboldt Foundation.","publication_identifier":{"eissn":["1432-0444"],"issn":["0179-5376"]},"_id":"14345"},{"type":"journal_article","day":"17","status":"public","file_date_updated":"2023-07-03T09:41:05Z","publication":"Journal of Applied and Computational Topology","article_type":"original","date_published":"2023-06-17T00:00:00Z","month":"06","language":[{"iso":"eng"}],"publisher":"Springer Nature","scopus_import":"1","department":[{"_id":"HeEd"}],"has_accepted_license":"1","file":[{"access_level":"open_access","date_updated":"2023-07-03T09:41:05Z","file_size":487355,"file_name":"2023_Journal of Applied and Computational Topology_Biswas.pdf","checksum":"697249d5d1c61dea4410b9f021b70fce","date_created":"2023-07-03T09:41:05Z","relation":"main_file","content_type":"application/pdf","creator":"alisjak","file_id":"13185","success":1}],"date_created":"2023-07-02T22:00:44Z","publication_status":"epub_ahead","citation":{"ista":"Biswas R, Cultrera di Montesano S, Edelsbrunner H, Saghafian M. 2023. Geometric characterization of the persistence of 1D maps. Journal of Applied and Computational Topology.","short":"R. Biswas, S. Cultrera di Montesano, H. Edelsbrunner, M. Saghafian, Journal of Applied and Computational Topology (2023).","mla":"Biswas, Ranita, et al. “Geometric Characterization of the Persistence of 1D Maps.” Journal of Applied and Computational Topology, Springer Nature, 2023, doi:10.1007/s41468-023-00126-9.","ama":"Biswas R, Cultrera di Montesano S, Edelsbrunner H, Saghafian M. Geometric characterization of the persistence of 1D maps. Journal of Applied and Computational Topology. 2023. doi:10.1007/s41468-023-00126-9","chicago":"Biswas, Ranita, Sebastiano Cultrera di Montesano, Herbert Edelsbrunner, and Morteza Saghafian. “Geometric Characterization of the Persistence of 1D Maps.” Journal of Applied and Computational Topology. Springer Nature, 2023. https://doi.org/10.1007/s41468-023-00126-9.","apa":"Biswas, R., Cultrera di Montesano, S., Edelsbrunner, H., & Saghafian, M. (2023). Geometric characterization of the persistence of 1D maps. Journal of Applied and Computational Topology. Springer Nature. https://doi.org/10.1007/s41468-023-00126-9","ieee":"R. Biswas, S. Cultrera di Montesano, H. Edelsbrunner, and M. Saghafian, “Geometric characterization of the persistence of 1D maps,” Journal of Applied and Computational Topology. Springer Nature, 2023."},"author":[{"first_name":"Ranita","full_name":"Biswas, Ranita","last_name":"Biswas","orcid":"0000-0002-5372-7890","id":"3C2B033E-F248-11E8-B48F-1D18A9856A87"},{"id":"34D2A09C-F248-11E8-B48F-1D18A9856A87","first_name":"Sebastiano","orcid":"0000-0001-6249-0832","last_name":"Cultrera Di Montesano","full_name":"Cultrera Di Montesano, Sebastiano"},{"id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","first_name":"Herbert","orcid":"0000-0002-9823-6833","full_name":"Edelsbrunner, Herbert","last_name":"Edelsbrunner"},{"full_name":"Saghafian, Morteza","last_name":"Saghafian","first_name":"Morteza","id":"f86f7148-b140-11ec-9577-95435b8df824"}],"abstract":[{"text":"We characterize critical points of 1-dimensional maps paired in persistent homology\r\ngeometrically and this way get elementary proofs of theorems about the symmetry\r\nof persistence diagrams and the variation of such maps. In particular, we identify\r\nbranching points and endpoints of networks as the sole source of asymmetry and\r\nrelate the cycle basis in persistent homology with a version of the stable marriage\r\nproblem. Our analysis provides the foundations of fast algorithms for maintaining a\r\ncollection of sorted lists together with its persistence diagram.","lang":"eng"}],"oa":1,"date_updated":"2023-10-18T08:13:10Z","article_processing_charge":"Yes (via OA deal)","acknowledgement":"Open access funding provided by Austrian Science Fund (FWF). This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme, grant no. 788183, from the Wittgenstein Prize, Austrian Science Fund (FWF), Grant No. Z 342-N31, and from the DFG Collaborative Research Center TRR 109, ‘Discretization in Geometry and Dynamics’, Austrian Science Fund (FWF), Grant No. I 02979-N35. The authors of this paper thank anonymous reviewers for their constructive criticism and Monika Henzinger for detailed comments on an earlier version of this paper.","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa_version":"Published Version","project":[{"call_identifier":"H2020","_id":"266A2E9E-B435-11E9-9278-68D0E5697425","name":"Alpha Shape Theory Extended","grant_number":"788183"},{"name":"Discretization in Geometry and Dynamics","_id":"0aa4bc98-070f-11eb-9043-e6fff9c6a316","grant_number":"I4887"},{"name":"The Wittgenstein Prize","_id":"268116B8-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"Z00342"}],"quality_controlled":"1","_id":"13182","publication_identifier":{"eissn":["2367-1734"],"issn":["2367-1726"]},"ec_funded":1,"doi":"10.1007/s41468-023-00126-9","year":"2023","title":"Geometric characterization of the persistence of 1D maps","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)"},"ddc":["000"]},{"external_id":{"isi":["000846967100001"]},"title":"A simple algorithm for higher-order Delaunay mosaics and alpha shapes","doi":"10.1007/s00453-022-01027-6","year":"2023","ec_funded":1,"ddc":["510"],"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)"},"isi":1,"abstract":[{"text":"We present a simple algorithm for computing higher-order Delaunay mosaics that works in Euclidean spaces of any finite dimensions. The algorithm selects the vertices of the order-k mosaic from incrementally constructed lower-order mosaics and uses an algorithm for weighted first-order Delaunay mosaics as a black-box to construct the order-k mosaic from its vertices. Beyond this black-box, the algorithm uses only combinatorial operations, thus facilitating easy implementation. We extend this algorithm to compute higher-order α-shapes and provide open-source implementations. We present experimental results for properties of higher-order Delaunay mosaics of random point sets.","lang":"eng"}],"author":[{"orcid":"0000-0002-9823-6833","last_name":"Edelsbrunner","full_name":"Edelsbrunner, Herbert","first_name":"Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87"},{"id":"464B40D6-F248-11E8-B48F-1D18A9856A87","full_name":"Osang, Georg F","last_name":"Osang","first_name":"Georg F"}],"citation":{"chicago":"Edelsbrunner, Herbert, and Georg F Osang. “A Simple Algorithm for Higher-Order Delaunay Mosaics and Alpha Shapes.” Algorithmica. Springer Nature, 2023. https://doi.org/10.1007/s00453-022-01027-6.","ieee":"H. Edelsbrunner and G. F. Osang, “A simple algorithm for higher-order Delaunay mosaics and alpha shapes,” Algorithmica, vol. 85. Springer Nature, pp. 277–295, 2023.","apa":"Edelsbrunner, H., & Osang, G. F. (2023). A simple algorithm for higher-order Delaunay mosaics and alpha shapes. Algorithmica. Springer Nature. https://doi.org/10.1007/s00453-022-01027-6","short":"H. Edelsbrunner, G.F. Osang, Algorithmica 85 (2023) 277–295.","ista":"Edelsbrunner H, Osang GF. 2023. A simple algorithm for higher-order Delaunay mosaics and alpha shapes. Algorithmica. 85, 277–295.","mla":"Edelsbrunner, Herbert, and Georg F. Osang. “A Simple Algorithm for Higher-Order Delaunay Mosaics and Alpha Shapes.” Algorithmica, vol. 85, Springer Nature, 2023, pp. 277–95, doi:10.1007/s00453-022-01027-6.","ama":"Edelsbrunner H, Osang GF. A simple algorithm for higher-order Delaunay mosaics and alpha shapes. Algorithmica. 2023;85:277-295. doi:10.1007/s00453-022-01027-6"},"publication_status":"published","publication_identifier":{"issn":["0178-4617"],"eissn":["1432-0541"]},"_id":"12086","quality_controlled":"1","oa_version":"Published Version","project":[{"grant_number":"788183","name":"Alpha Shape Theory Extended","_id":"266A2E9E-B435-11E9-9278-68D0E5697425","call_identifier":"H2020"},{"grant_number":"Z00342","name":"The Wittgenstein Prize","_id":"268116B8-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"call_identifier":"FWF","_id":"2561EBF4-B435-11E9-9278-68D0E5697425","name":"Persistence and stability of geometric complexes","grant_number":"I02979-N35"}],"acknowledgement":"Open access funding provided by Austrian Science Fund (FWF). This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme, Grant No. 788183, from the Wittgenstein Prize, Austrian Science Fund (FWF), Grant No. Z 342-N31, and from the DFG Collaborative Research Center TRR 109, ‘Discretization in Geometry and Dynamics’, Austrian Science Fund (FWF), Grant No. I 02979-N35.","user_id":"2EBD1598-F248-11E8-B48F-1D18A9856A87","article_processing_charge":"Yes (via OA deal)","oa":1,"date_updated":"2023-06-27T12:53:43Z","volume":85,"scopus_import":"1","publisher":"Springer Nature","language":[{"iso":"eng"}],"month":"01","date_published":"2023-01-01T00:00:00Z","article_type":"original","file":[{"access_level":"open_access","date_updated":"2023-01-20T10:02:48Z","checksum":"71685ca5121f4c837f40c3f8eb50c915","date_created":"2023-01-20T10:02:48Z","file_size":911017,"file_name":"2023_Algorithmica_Edelsbrunner.pdf","creator":"dernst","file_id":"12322","relation":"main_file","content_type":"application/pdf","success":1}],"date_created":"2022-09-11T22:01:57Z","has_accepted_license":"1","department":[{"_id":"HeEd"}],"intvolume":" 85","status":"public","day":"01","type":"journal_article","publication":"Algorithmica","file_date_updated":"2023-01-20T10:02:48Z","page":"277-295"},{"title":"Computing the volume, surface area, mean, and Gaussian curvatures of molecules and their derivatives","external_id":{"isi":["000920370700001"],"pmid":["36638318"]},"ec_funded":1,"year":"2023","doi":"10.1021/acs.jcim.2c01346","ddc":["510","540"],"isi":1,"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)"},"author":[{"first_name":"Patrice","last_name":"Koehl","full_name":"Koehl, Patrice"},{"id":"430D2C90-F248-11E8-B48F-1D18A9856A87","first_name":"Arseniy","full_name":"Akopyan, Arseniy","last_name":"Akopyan","orcid":"0000-0002-2548-617X"},{"id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","first_name":"Herbert","full_name":"Edelsbrunner, Herbert","last_name":"Edelsbrunner","orcid":"0000-0002-9823-6833"}],"abstract":[{"lang":"eng","text":"Geometry is crucial in our efforts to comprehend the structures and dynamics of biomolecules. For example, volume, surface area, and integrated mean and Gaussian curvature of the union of balls representing a molecule are used to quantify its interactions with the water surrounding it in the morphometric implicit solvent models. The Alpha Shape theory provides an accurate and reliable method for computing these geometric measures. In this paper, we derive homogeneous formulas for the expressions of these measures and their derivatives with respect to the atomic coordinates, and we provide algorithms that implement them into a new software package, AlphaMol. The only variables in these formulas are the interatomic distances, making them insensitive to translations and rotations. AlphaMol includes a sequential algorithm and a parallel algorithm. In the parallel version, we partition the atoms of the molecule of interest into 3D rectangular blocks, using a kd-tree algorithm. We then apply the sequential algorithm of AlphaMol to each block, augmented by a buffer zone to account for atoms whose ball representations may partially cover the block. The current parallel version of AlphaMol leads to a 20-fold speed-up compared to an independent serial implementation when using 32 processors. For instance, it takes 31 s to compute the geometric measures and derivatives of each atom in a viral capsid with more than 26 million atoms on 32 Intel processors running at 2.7 GHz. The presence of the buffer zones, however, leads to redundant computations, which ultimately limit the impact of using multiple processors. AlphaMol is available as an OpenSource software."}],"citation":{"mla":"Koehl, Patrice, et al. “Computing the Volume, Surface Area, Mean, and Gaussian Curvatures of Molecules and Their Derivatives.” Journal of Chemical Information and Modeling, vol. 63, no. 3, American Chemical Society, 2023, pp. 973–85, doi:10.1021/acs.jcim.2c01346.","ama":"Koehl P, Akopyan A, Edelsbrunner H. Computing the volume, surface area, mean, and Gaussian curvatures of molecules and their derivatives. Journal of Chemical Information and Modeling. 2023;63(3):973-985. doi:10.1021/acs.jcim.2c01346","short":"P. Koehl, A. Akopyan, H. Edelsbrunner, Journal of Chemical Information and Modeling 63 (2023) 973–985.","ista":"Koehl P, Akopyan A, Edelsbrunner H. 2023. Computing the volume, surface area, mean, and Gaussian curvatures of molecules and their derivatives. Journal of Chemical Information and Modeling. 63(3), 973–985.","ieee":"P. Koehl, A. Akopyan, and H. Edelsbrunner, “Computing the volume, surface area, mean, and Gaussian curvatures of molecules and their derivatives,” Journal of Chemical Information and Modeling, vol. 63, no. 3. American Chemical Society, pp. 973–985, 2023.","apa":"Koehl, P., Akopyan, A., & Edelsbrunner, H. (2023). Computing the volume, surface area, mean, and Gaussian curvatures of molecules and their derivatives. Journal of Chemical Information and Modeling. American Chemical Society. https://doi.org/10.1021/acs.jcim.2c01346","chicago":"Koehl, Patrice, Arseniy Akopyan, and Herbert Edelsbrunner. “Computing the Volume, Surface Area, Mean, and Gaussian Curvatures of Molecules and Their Derivatives.” Journal of Chemical Information and Modeling. American Chemical Society, 2023. https://doi.org/10.1021/acs.jcim.2c01346."},"publication_status":"published","project":[{"call_identifier":"H2020","_id":"266A2E9E-B435-11E9-9278-68D0E5697425","name":"Alpha Shape Theory Extended","grant_number":"788183"},{"call_identifier":"FWF","_id":"268116B8-B435-11E9-9278-68D0E5697425","name":"The Wittgenstein Prize","grant_number":"Z00342"},{"call_identifier":"FWF","name":"Persistence and stability of geometric complexes","_id":"2561EBF4-B435-11E9-9278-68D0E5697425","grant_number":"I02979-N35"}],"oa_version":"Published Version","quality_controlled":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","acknowledgement":"P.K. acknowledges support from the University of California Multicampus Research Programs and Initiatives (Grant No. M21PR3267) and from the NSF (Grant No.1760485). H.E. acknowledges support from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation program, Grant No. 788183, from the Wittgenstein Prize, Austrian Science Fund (FWF), Grant No. Z 342-N31, and from the DFG Collaborative Research Center TRR 109, ‘Discretization in Geometry and Dynamics’, Austrian Science Fund (FWF), Grant No. I 02979-N35.\r\nOpen Access is funded by the Austrian Science Fund (FWF).","publication_identifier":{"issn":["1549-9596"],"eissn":["1549-960X"]},"_id":"12544","pmid":1,"article_processing_charge":"No","date_updated":"2023-08-16T12:22:07Z","volume":63,"oa":1,"language":[{"iso":"eng"}],"scopus_import":"1","publisher":"American Chemical Society","date_published":"2023-02-13T00:00:00Z","article_type":"original","month":"02","date_created":"2023-02-12T23:00:59Z","file":[{"access_level":"open_access","date_updated":"2023-08-16T12:21:13Z","file_size":8069223,"file_name":"2023_JCIM_Koehl.pdf","checksum":"7d20562269edff1e31b9d6019d4983b0","date_created":"2023-08-16T12:21:13Z","relation":"main_file","content_type":"application/pdf","creator":"dernst","file_id":"14070","success":1}],"department":[{"_id":"HeEd"}],"has_accepted_license":"1","status":"public","intvolume":" 63","type":"journal_article","day":"13","file_date_updated":"2023-08-16T12:21:13Z","page":"973-985","publication":"Journal of Chemical Information and Modeling","issue":"3"},{"file_date_updated":"2022-07-27T09:25:53Z","publication":"Leibniz International Proceedings on Mathematics","status":"public","type":"journal_article","day":"27","date_created":"2022-07-27T09:27:34Z","file":[{"creator":"scultrer","file_id":"11659","relation":"main_file","content_type":"application/pdf","access_level":"open_access","date_updated":"2022-07-27T09:25:53Z","checksum":"b2f511e8b1cae5f1892b0cdec341acac","date_created":"2022-07-27T09:25:53Z","file_size":639266,"file_name":"D-S-E.pdf"}],"department":[{"_id":"GradSch"},{"_id":"HeEd"}],"has_accepted_license":"1","language":[{"iso":"eng"}],"publisher":"Schloss Dagstuhl - Leibniz Zentrum für Informatik","date_published":"2022-07-27T00:00:00Z","month":"07","project":[{"grant_number":"788183","call_identifier":"H2020","name":"Alpha Shape Theory Extended","_id":"266A2E9E-B435-11E9-9278-68D0E5697425"},{"name":"The Wittgenstein Prize","_id":"268116B8-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"Z00342"},{"grant_number":"I02979-N35","call_identifier":"FWF","name":"Persistence and stability of geometric complexes","_id":"2561EBF4-B435-11E9-9278-68D0E5697425"}],"oa_version":"Submitted Version","quality_controlled":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","acknowledgement":"This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme, grant no. 788183, from the Wittgenstein Prize, Austrian Science Fund (FWF), grant no. Z 342-N31, and from the DFG Collaborative Research Center TRR 109, ‘Discretization in Geometry and Dynamics’, Austrian Science Fund (FWF), grant no. I 02979-N35.","_id":"11658","article_processing_charge":"No","date_updated":"2022-07-28T07:57:48Z","oa":1,"author":[{"id":"3C2B033E-F248-11E8-B48F-1D18A9856A87","first_name":"Ranita","full_name":"Biswas, Ranita","last_name":"Biswas","orcid":"0000-0002-5372-7890"},{"id":"34D2A09C-F248-11E8-B48F-1D18A9856A87","first_name":"Sebastiano","full_name":"Cultrera di Montesano, Sebastiano","last_name":"Cultrera di Montesano","orcid":"0000-0001-6249-0832"},{"first_name":"Herbert","orcid":"0000-0002-9823-6833","last_name":"Edelsbrunner","full_name":"Edelsbrunner, Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87"},{"id":"f86f7148-b140-11ec-9577-95435b8df824","first_name":"Morteza","last_name":"Saghafian","full_name":"Saghafian, Morteza"}],"abstract":[{"text":"The depth of a cell in an arrangement of n (non-vertical) great-spheres in Sd is the number of great-spheres that pass above the cell. We prove Euler-type relations, which imply extensions of the classic Dehn–Sommerville relations for convex polytopes to sublevel sets of the depth function, and we use the relations to extend the expressions for the number of faces of neighborly polytopes to the number of cells of levels in neighborly arrangements.","lang":"eng"}],"citation":{"apa":"Biswas, R., Cultrera di Montesano, S., Edelsbrunner, H., & Saghafian, M. (n.d.). Depth in arrangements: Dehn–Sommerville–Euler relations with applications. Leibniz International Proceedings on Mathematics. Schloss Dagstuhl - Leibniz Zentrum für Informatik.","ieee":"R. Biswas, S. Cultrera di Montesano, H. Edelsbrunner, and M. Saghafian, “Depth in arrangements: Dehn–Sommerville–Euler relations with applications,” Leibniz International Proceedings on Mathematics. Schloss Dagstuhl - Leibniz Zentrum für Informatik.","chicago":"Biswas, Ranita, Sebastiano Cultrera di Montesano, Herbert Edelsbrunner, and Morteza Saghafian. “Depth in Arrangements: Dehn–Sommerville–Euler Relations with Applications.” Leibniz International Proceedings on Mathematics. Schloss Dagstuhl - Leibniz Zentrum für Informatik, n.d.","ama":"Biswas R, Cultrera di Montesano S, Edelsbrunner H, Saghafian M. Depth in arrangements: Dehn–Sommerville–Euler relations with applications. Leibniz International Proceedings on Mathematics.","mla":"Biswas, Ranita, et al. “Depth in Arrangements: Dehn–Sommerville–Euler Relations with Applications.” Leibniz International Proceedings on Mathematics, Schloss Dagstuhl - Leibniz Zentrum für Informatik.","ista":"Biswas R, Cultrera di Montesano S, Edelsbrunner H, Saghafian M. Depth in arrangements: Dehn–Sommerville–Euler relations with applications. Leibniz International Proceedings on Mathematics.","short":"R. Biswas, S. Cultrera di Montesano, H. Edelsbrunner, M. Saghafian, Leibniz International Proceedings on Mathematics (n.d.)."},"publication_status":"submitted","ddc":["510"],"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)"},"title":"Depth in arrangements: Dehn–Sommerville–Euler relations with applications","ec_funded":1,"year":"2022"},{"citation":{"mla":"Biswas, Ranita, et al. “A Window to the Persistence of 1D Maps. I: Geometric Characterization of Critical Point Pairs.” LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum für Informatik.","ama":"Biswas R, Cultrera di Montesano S, Edelsbrunner H, Saghafian M. A window to the persistence of 1D maps. I: Geometric characterization of critical point pairs. LIPIcs.","ista":"Biswas R, Cultrera di Montesano S, Edelsbrunner H, Saghafian M. A window to the persistence of 1D maps. I: Geometric characterization of critical point pairs. LIPIcs.","short":"R. Biswas, S. Cultrera di Montesano, H. Edelsbrunner, M. Saghafian, LIPIcs (n.d.).","ieee":"R. Biswas, S. Cultrera di Montesano, H. Edelsbrunner, and M. Saghafian, “A window to the persistence of 1D maps. I: Geometric characterization of critical point pairs,” LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik.","apa":"Biswas, R., Cultrera di Montesano, S., Edelsbrunner, H., & Saghafian, M. (n.d.). A window to the persistence of 1D maps. I: Geometric characterization of critical point pairs. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik.","chicago":"Biswas, Ranita, Sebastiano Cultrera di Montesano, Herbert Edelsbrunner, and Morteza Saghafian. “A Window to the Persistence of 1D Maps. I: Geometric Characterization of Critical Point Pairs.” LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, n.d."},"publication_status":"submitted","author":[{"id":"3C2B033E-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-5372-7890","full_name":"Biswas, Ranita","last_name":"Biswas","first_name":"Ranita"},{"last_name":"Cultrera di Montesano","full_name":"Cultrera di Montesano, Sebastiano","orcid":"0000-0001-6249-0832","first_name":"Sebastiano","id":"34D2A09C-F248-11E8-B48F-1D18A9856A87"},{"orcid":"0000-0002-9823-6833","full_name":"Edelsbrunner, Herbert","last_name":"Edelsbrunner","first_name":"Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Morteza","full_name":"Saghafian, Morteza","last_name":"Saghafian"}],"abstract":[{"lang":"eng","text":"We characterize critical points of 1-dimensional maps paired in persistent homology geometrically and this way get elementary proofs of theorems about the symmetry of persistence diagrams and the variation of such maps. In particular, we identify branching points and endpoints of networks as the sole source of asymmetry and relate the cycle basis in persistent homology with a version of the stable marriage problem. Our analysis provides the foundations of fast algorithms for maintaining collections of interrelated sorted lists together with their persistence diagrams. "}],"article_processing_charge":"No","oa":1,"date_updated":"2022-07-28T08:05:34Z","oa_version":"Submitted Version","project":[{"_id":"266A2E9E-B435-11E9-9278-68D0E5697425","name":"Alpha Shape Theory Extended","call_identifier":"H2020","grant_number":"788183"},{"name":"The Wittgenstein Prize","_id":"268116B8-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"Z00342"},{"grant_number":"I02979-N35","name":"Persistence and stability of geometric complexes","_id":"2561EBF4-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"}],"quality_controlled":"1","acknowledgement":"This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme, grant no. 788183, from the Wittgenstein Prize, Austrian Science Fund (FWF), grant no. Z 342-N31, and from the DFG Collaborative Research Center TRR 109, ‘Discretization in Geometry and Dynamics’, Austrian Science Fund (FWF), grant no. I 02979-N35. ","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"11660","ec_funded":1,"year":"2022","title":"A window to the persistence of 1D maps. I: Geometric characterization of critical point pairs","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)"},"alternative_title":["LIPIcs"],"ddc":["510"],"type":"journal_article","day":"25","status":"public","file_date_updated":"2022-07-27T09:30:30Z","publication":"LIPIcs","date_published":"2022-07-25T00:00:00Z","month":"07","language":[{"iso":"eng"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","department":[{"_id":"GradSch"},{"_id":"HeEd"}],"has_accepted_license":"1","file":[{"creator":"scultrer","file_id":"11661","content_type":"application/pdf","relation":"main_file","date_updated":"2022-07-27T09:30:30Z","access_level":"open_access","date_created":"2022-07-27T09:30:30Z","checksum":"95903f9d1649e8e437a967b6f2f64730","file_name":"window 1.pdf","file_size":564836}],"date_created":"2022-07-27T09:31:15Z"},{"publication_status":"published","citation":{"apa":"Goudarzi, S., Sharif, M., & Karimipour, F. (2022). A context-aware dimension reduction framework for trajectory and health signal analyses. Journal of Ambient Intelligence and Humanized Computing. Springer Nature. https://doi.org/10.1007/s12652-021-03569-z","ieee":"S. Goudarzi, M. Sharif, and F. Karimipour, “A context-aware dimension reduction framework for trajectory and health signal analyses,” Journal of Ambient Intelligence and Humanized Computing, vol. 13. Springer Nature, pp. 2621–2635, 2022.","chicago":"Goudarzi, Samira, Mohammad Sharif, and Farid Karimipour. “A Context-Aware Dimension Reduction Framework for Trajectory and Health Signal Analyses.” Journal of Ambient Intelligence and Humanized Computing. Springer Nature, 2022. https://doi.org/10.1007/s12652-021-03569-z.","mla":"Goudarzi, Samira, et al. “A Context-Aware Dimension Reduction Framework for Trajectory and Health Signal Analyses.” Journal of Ambient Intelligence and Humanized Computing, vol. 13, Springer Nature, 2022, pp. 2621–2635, doi:10.1007/s12652-021-03569-z.","ama":"Goudarzi S, Sharif M, Karimipour F. A context-aware dimension reduction framework for trajectory and health signal analyses. Journal of Ambient Intelligence and Humanized Computing. 2022;13:2621–2635. doi:10.1007/s12652-021-03569-z","short":"S. Goudarzi, M. Sharif, F. Karimipour, Journal of Ambient Intelligence and Humanized Computing 13 (2022) 2621–2635.","ista":"Goudarzi S, Sharif M, Karimipour F. 2022. A context-aware dimension reduction framework for trajectory and health signal analyses. Journal of Ambient Intelligence and Humanized Computing. 13, 2621–2635."},"abstract":[{"text":"It is practical to collect a huge amount of movement data and environmental context information along with the health signals of individuals because there is the emergence of new generations of positioning and tracking technologies and rapid advancements of health sensors. The study of the relations between these datasets and their sequence similarity analysis is of interest to many applications such as health monitoring and recommender systems. However, entering all movement parameters and health signals can lead to the complexity of the problem and an increase in its computational load. In this situation, dimension reduction techniques can be used to avoid consideration of simultaneous dependent parameters in the process of similarity measurement of the trajectories. The present study provides a framework, named CaDRAW, to use spatial–temporal data and movement parameters along with independent context information in the process of measuring the similarity of trajectories. In this regard, the omission of dependent movement characteristic signals is conducted by using an unsupervised feature selection dimension reduction technique. To evaluate the effectiveness of the proposed framework, it was applied to a real contextualized movement and related health signal datasets of individuals. The results indicated the capability of the proposed framework in measuring the similarity and in decreasing the characteristic signals in such a way that the similarity results -before and after reduction of dependent characteristic signals- have small differences. The mean differences between the obtained results before and after reducing the dimension were 0.029 and 0.023 for the round path, respectively.","lang":"eng"}],"keyword":["general computer science"],"author":[{"first_name":"Samira","last_name":"Goudarzi","full_name":"Goudarzi, Samira"},{"first_name":"Mohammad","full_name":"Sharif, Mohammad","last_name":"Sharif"},{"first_name":"Farid","full_name":"Karimipour, Farid","last_name":"Karimipour","orcid":"0000-0001-6746-4174","id":"2A2BCDC4-CF62-11E9-BE5E-3B1EE6697425"}],"volume":13,"oa":1,"date_updated":"2023-08-02T13:31:48Z","article_processing_charge":"No","_id":"10208","publication_identifier":{"eissn":["1868-5145"],"issn":["1868-5137"]},"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","acknowledgement":"The third author acknowledges the funding received from the Wittgenstein Prize, Austrian Science Fund (FWF), grant no. Z 342-N31.","quality_controlled":"1","project":[{"grant_number":"Z00342","call_identifier":"FWF","name":"The Wittgenstein Prize","_id":"268116B8-B435-11E9-9278-68D0E5697425"}],"oa_version":"Submitted Version","doi":"10.1007/s12652-021-03569-z","year":"2022","title":"A context-aware dimension reduction framework for trajectory and health signal analyses","external_id":{"isi":["000712198000001"]},"isi":1,"ddc":["000"],"day":"01","type":"journal_article","intvolume":" 13","status":"public","publication":"Journal of Ambient Intelligence and Humanized Computing","file_date_updated":"2022-12-20T23:30:08Z","page":"2621–2635","month":"05","date_published":"2022-05-01T00:00:00Z","article_type":"original","publisher":"Springer Nature","scopus_import":"1","language":[{"iso":"eng"}],"has_accepted_license":"1","department":[{"_id":"HeEd"}],"date_created":"2021-11-02T09:28:55Z","file":[{"file_id":"10279","creator":"fkarimip","relation":"main_file","content_type":"application/pdf","checksum":"0a8961416a9bb2be5a1cebda65468bcf","date_created":"2021-11-12T19:38:05Z","file_size":1634958,"embargo":"2022-11-12","file_name":"A Context‑aware Dimension Reduction Framework - Journal of Ambient Intelligence 2021 (Preprint version).pdf","access_level":"open_access","date_updated":"2022-12-20T23:30:08Z"}]},{"related_material":{"record":[{"id":"9296","relation":"earlier_version","status":"public"}]},"ddc":["000"],"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)"},"external_id":{"arxiv":["2101.03928"]},"title":"On compatible matchings","doi":"10.7155/jgaa.00591","year":"2022","ec_funded":1,"_id":"11938","publication_identifier":{"issn":["1526-1719"]},"acknowledgement":"A.A. funded by the Marie Sklodowska-Curie grant agreement No 754411. Z.M. partially funded by Wittgenstein Prize, Austrian Science Fund (FWF), grant no. Z 342-N31. I.P., D.P., and B.V. partially supported by FWF within the collaborative DACH project Arrangements and Drawings as FWF project I 3340-N35. A.P. supported by a Schrödinger fellowship of the FWF: J-3847-N35. J.T. partially supported by ERC Start grant no. (279307: Graph Games), FWF grant no. P23499-N23 and S11407-N23 (RiSE).","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa_version":"Published Version","project":[{"grant_number":"754411","_id":"260C2330-B435-11E9-9278-68D0E5697425","name":"ISTplus - Postdoctoral Fellowships","call_identifier":"H2020"},{"_id":"268116B8-B435-11E9-9278-68D0E5697425","name":"The Wittgenstein Prize","call_identifier":"FWF","grant_number":"Z00342"},{"grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications","_id":"2581B60A-B435-11E9-9278-68D0E5697425","call_identifier":"FP7"},{"name":"Modern Graph Algorithmic Techniques in Formal Verification","_id":"2584A770-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"P 23499-N23"},{"grant_number":"S11407","name":"Game Theory","_id":"25863FF4-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"}],"quality_controlled":"1","arxiv":1,"date_updated":"2023-02-23T13:54:21Z","volume":26,"oa":1,"article_processing_charge":"No","abstract":[{"text":"A matching is compatible to two or more labeled point sets of size n with labels {1, . . . , n} if its straight-line drawing on each of these point sets is crossing-free. We study the maximum number of edges in a matching compatible to two or more labeled point sets in general position in the plane. We show that for any two labeled sets of n points in convex position there exists a compatible matching with ⌊√2n + 1 − 1⌋ edges. More generally, for any ℓ labeled point sets we construct compatible matchings of size Ω(n1/ℓ). As a corresponding upper bound, we use probabilistic arguments to show that for any ℓ given sets of n points there exists a labeling of each set such that the largest compatible matching has O(n2/(ℓ+1)) edges. Finally, we show that Θ(log n) copies of any set of n points are necessary and sufficient for the existence of labelings of these point sets such that any compatible matching consists only of a single edge.","lang":"eng"}],"author":[{"first_name":"Oswin","last_name":"Aichholzer","full_name":"Aichholzer, Oswin"},{"orcid":"0000-0003-2401-8670","full_name":"Arroyo Guevara, Alan M","last_name":"Arroyo Guevara","first_name":"Alan M","id":"3207FDC6-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Zuzana","orcid":"0000-0002-6660-1322","full_name":"Masárová, Zuzana","last_name":"Masárová","id":"45CFE238-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Parada","full_name":"Parada, Irene","first_name":"Irene"},{"first_name":"Daniel","full_name":"Perz, Daniel","last_name":"Perz"},{"first_name":"Alexander","full_name":"Pilz, Alexander","last_name":"Pilz"},{"full_name":"Tkadlec, Josef","last_name":"Tkadlec","orcid":"0000-0002-1097-9684","first_name":"Josef","id":"3F24CCC8-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Birgit","full_name":"Vogtenhuber, Birgit","last_name":"Vogtenhuber"}],"publication_status":"published","citation":{"short":"O. Aichholzer, A.M. Arroyo Guevara, Z. Masárová, I. Parada, D. Perz, A. Pilz, J. Tkadlec, B. Vogtenhuber, Journal of Graph Algorithms and Applications 26 (2022) 225–240.","ista":"Aichholzer O, Arroyo Guevara AM, Masárová Z, Parada I, Perz D, Pilz A, Tkadlec J, Vogtenhuber B. 2022. On compatible matchings. Journal of Graph Algorithms and Applications. 26(2), 225–240.","mla":"Aichholzer, Oswin, et al. “On Compatible Matchings.” Journal of Graph Algorithms and Applications, vol. 26, no. 2, Brown University, 2022, pp. 225–40, doi:10.7155/jgaa.00591.","ama":"Aichholzer O, Arroyo Guevara AM, Masárová Z, et al. On compatible matchings. Journal of Graph Algorithms and Applications. 2022;26(2):225-240. doi:10.7155/jgaa.00591","chicago":"Aichholzer, Oswin, Alan M Arroyo Guevara, Zuzana Masárová, Irene Parada, Daniel Perz, Alexander Pilz, Josef Tkadlec, and Birgit Vogtenhuber. “On Compatible Matchings.” Journal of Graph Algorithms and Applications. Brown University, 2022. https://doi.org/10.7155/jgaa.00591.","apa":"Aichholzer, O., Arroyo Guevara, A. M., Masárová, Z., Parada, I., Perz, D., Pilz, A., … Vogtenhuber, B. (2022). On compatible matchings. Journal of Graph Algorithms and Applications. Brown University. https://doi.org/10.7155/jgaa.00591","ieee":"O. Aichholzer et al., “On compatible matchings,” Journal of Graph Algorithms and Applications, vol. 26, no. 2. Brown University, pp. 225–240, 2022."},"file":[{"success":1,"file_id":"11940","creator":"dernst","relation":"main_file","content_type":"application/pdf","checksum":"dc6e255e3558faff924fd9e370886c11","date_created":"2022-08-22T06:42:42Z","file_size":694538,"file_name":"2022_JourGraphAlgorithmsApplic_Aichholzer.pdf","access_level":"open_access","date_updated":"2022-08-22T06:42:42Z"}],"date_created":"2022-08-21T22:01:56Z","has_accepted_license":"1","department":[{"_id":"UlWa"},{"_id":"HeEd"},{"_id":"KrCh"}],"publisher":"Brown University","scopus_import":"1","language":[{"iso":"eng"}],"month":"06","article_type":"original","date_published":"2022-06-01T00:00:00Z","issue":"2","publication":"Journal of Graph Algorithms and Applications","file_date_updated":"2022-08-22T06:42:42Z","page":"225-240","intvolume":" 26","status":"public","day":"01","type":"journal_article"},{"arxiv":1,"article_processing_charge":"No","date_updated":"2023-08-04T10:57:42Z","oa":1,"volume":93,"publication_identifier":{"issn":["09257721"]},"_id":"8317","oa_version":"Preprint","quality_controlled":"1","project":[{"name":"The Wittgenstein Prize","_id":"268116B8-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"Z00342"}],"acknowledgement":"This research was performed in part at the 33rd Bellairs Winter Workshop on Computational Geometry. We thank all other participants for a fruitful atmosphere. H. Akitaya was supported by NSF CCF-1422311 & 1423615. Z. Masárová was partially funded by Wittgenstein Prize, Austrian Science Fund (FWF), grant no. Z 342-N31.","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","citation":{"ama":"Aichholzer O, Akitaya HA, Cheung KC, et al. Folding polyominoes with holes into a cube. Computational Geometry: Theory and Applications. 2021;93. doi:10.1016/j.comgeo.2020.101700","mla":"Aichholzer, Oswin, et al. “Folding Polyominoes with Holes into a Cube.” Computational Geometry: Theory and Applications, vol. 93, 101700, Elsevier, 2021, doi:10.1016/j.comgeo.2020.101700.","ista":"Aichholzer O, Akitaya HA, Cheung KC, Demaine ED, Demaine ML, Fekete SP, Kleist L, Kostitsyna I, Löffler M, Masárová Z, Mundilova K, Schmidt C. 2021. Folding polyominoes with holes into a cube. Computational Geometry: Theory and Applications. 93, 101700.","short":"O. Aichholzer, H.A. Akitaya, K.C. Cheung, E.D. Demaine, M.L. Demaine, S.P. Fekete, L. Kleist, I. Kostitsyna, M. Löffler, Z. Masárová, K. Mundilova, C. Schmidt, Computational Geometry: Theory and Applications 93 (2021).","ieee":"O. Aichholzer et al., “Folding polyominoes with holes into a cube,” Computational Geometry: Theory and Applications, vol. 93. Elsevier, 2021.","apa":"Aichholzer, O., Akitaya, H. A., Cheung, K. C., Demaine, E. D., Demaine, M. L., Fekete, S. P., … Schmidt, C. (2021). Folding polyominoes with holes into a cube. Computational Geometry: Theory and Applications. Elsevier. https://doi.org/10.1016/j.comgeo.2020.101700","chicago":"Aichholzer, Oswin, Hugo A. Akitaya, Kenneth C. Cheung, Erik D. Demaine, Martin L. Demaine, Sándor P. Fekete, Linda Kleist, et al. “Folding Polyominoes with Holes into a Cube.” Computational Geometry: Theory and Applications. Elsevier, 2021. https://doi.org/10.1016/j.comgeo.2020.101700."},"publication_status":"published","abstract":[{"text":"When can a polyomino piece of paper be folded into a unit cube? Prior work studied tree-like polyominoes, but polyominoes with holes remain an intriguing open problem. We present sufficient conditions for a polyomino with one or several holes to fold into a cube, and conditions under which cube folding is impossible. In particular, we show that all but five special “basic” holes guarantee foldability.","lang":"eng"}],"author":[{"first_name":"Oswin","last_name":"Aichholzer","full_name":"Aichholzer, Oswin"},{"last_name":"Akitaya","full_name":"Akitaya, Hugo A.","first_name":"Hugo A."},{"first_name":"Kenneth C.","full_name":"Cheung, Kenneth C.","last_name":"Cheung"},{"last_name":"Demaine","full_name":"Demaine, Erik D.","first_name":"Erik D."},{"last_name":"Demaine","full_name":"Demaine, Martin L.","first_name":"Martin L."},{"last_name":"Fekete","full_name":"Fekete, Sándor P.","first_name":"Sándor P."},{"full_name":"Kleist, Linda","last_name":"Kleist","first_name":"Linda"},{"full_name":"Kostitsyna, Irina","last_name":"Kostitsyna","first_name":"Irina"},{"full_name":"Löffler, Maarten","last_name":"Löffler","first_name":"Maarten"},{"first_name":"Zuzana","last_name":"Masárová","full_name":"Masárová, Zuzana","orcid":"0000-0002-6660-1322","id":"45CFE238-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Klara","full_name":"Mundilova, Klara","last_name":"Mundilova"},{"last_name":"Schmidt","full_name":"Schmidt, Christiane","first_name":"Christiane"}],"isi":1,"article_number":"101700","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1910.09917v3"}],"related_material":{"record":[{"id":"6989","relation":"shorter_version","status":"public"}]},"year":"2021","doi":"10.1016/j.comgeo.2020.101700","external_id":{"isi":["000579185100004"],"arxiv":["1910.09917"]},"title":"Folding polyominoes with holes into a cube","publication":"Computational Geometry: Theory and Applications","day":"01","type":"journal_article","intvolume":" 93","status":"public","department":[{"_id":"HeEd"}],"date_created":"2020-08-30T22:01:09Z","month":"02","date_published":"2021-02-01T00:00:00Z","article_type":"original","scopus_import":"1","publisher":"Elsevier","language":[{"iso":"eng"}]},{"page":"221-233","publication":"15th International Conference on Algorithms and Computation","type":"conference","day":"16","status":"public","intvolume":" 12635","department":[{"_id":"UlWa"},{"_id":"HeEd"},{"_id":"KrCh"}],"date_created":"2021-03-28T22:01:41Z","conference":{"end_date":"2021-03-02","location":"Yangon, Myanmar","name":"WALCOM: Algorithms and Computation","start_date":"2021-02-28"},"date_published":"2021-02-16T00:00:00Z","month":"02","language":[{"iso":"eng"}],"scopus_import":"1","publisher":"Springer Nature","article_processing_charge":"No","volume":12635,"date_updated":"2023-02-21T16:33:44Z","oa":1,"arxiv":1,"oa_version":"Preprint","project":[{"name":"ISTplus - Postdoctoral Fellowships","_id":"260C2330-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","grant_number":"754411"},{"name":"The Wittgenstein Prize","_id":"268116B8-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"Z00342"},{"name":"Quantitative Graph Games: Theory and Applications","_id":"2581B60A-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","grant_number":"279307"},{"_id":"2584A770-B435-11E9-9278-68D0E5697425","name":"Modern Graph Algorithmic Techniques in Formal Verification","call_identifier":"FWF","grant_number":"P 23499-N23"},{"grant_number":"S11407","name":"Game Theory","_id":"25863FF4-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"}],"quality_controlled":"1","user_id":"D865714E-FA4E-11E9-B85B-F5C5E5697425","acknowledgement":"A.A. funded by the Marie Skłodowska-Curie grant agreement No. 754411. Z.M. partially funded by Wittgenstein Prize, Austrian Science Fund (FWF), grant no. Z 342-N31. I.P., D.P., and B.V. partially supported by FWF within the collaborative DACH project Arrangements and Drawings as FWF project I 3340-N35. A.P. supported by a Schrödinger fellowship of the FWF: J-3847-N35. J.T. partially supported by ERC Start grant no. (279307: Graph Games), FWF grant no. P23499-N23 and S11407-N23 (RiSE).","publication_identifier":{"isbn":["9783030682101"],"issn":["03029743"],"eissn":["16113349"]},"_id":"9296","citation":{"ieee":"O. Aichholzer et al., “On compatible matchings,” in 15th International Conference on Algorithms and Computation, Yangon, Myanmar, 2021, vol. 12635, pp. 221–233.","apa":"Aichholzer, O., Arroyo Guevara, A. M., Masárová, Z., Parada, I., Perz, D., Pilz, A., … Vogtenhuber, B. (2021). On compatible matchings. In 15th International Conference on Algorithms and Computation (Vol. 12635, pp. 221–233). Yangon, Myanmar: Springer Nature. https://doi.org/10.1007/978-3-030-68211-8_18","chicago":"Aichholzer, Oswin, Alan M Arroyo Guevara, Zuzana Masárová, Irene Parada, Daniel Perz, Alexander Pilz, Josef Tkadlec, and Birgit Vogtenhuber. “On Compatible Matchings.” In 15th International Conference on Algorithms and Computation, 12635:221–33. Springer Nature, 2021. https://doi.org/10.1007/978-3-030-68211-8_18.","mla":"Aichholzer, Oswin, et al. “On Compatible Matchings.” 15th International Conference on Algorithms and Computation, vol. 12635, Springer Nature, 2021, pp. 221–33, doi:10.1007/978-3-030-68211-8_18.","ama":"Aichholzer O, Arroyo Guevara AM, Masárová Z, et al. On compatible matchings. In: 15th International Conference on Algorithms and Computation. Vol 12635. Springer Nature; 2021:221-233. doi:10.1007/978-3-030-68211-8_18","ista":"Aichholzer O, Arroyo Guevara AM, Masárová Z, Parada I, Perz D, Pilz A, Tkadlec J, Vogtenhuber B. 2021. On compatible matchings. 15th International Conference on Algorithms and Computation. WALCOM: Algorithms and Computation, LNCS, vol. 12635, 221–233.","short":"O. Aichholzer, A.M. Arroyo Guevara, Z. Masárová, I. Parada, D. Perz, A. Pilz, J. Tkadlec, B. Vogtenhuber, in:, 15th International Conference on Algorithms and Computation, Springer Nature, 2021, pp. 221–233."},"publication_status":"published","author":[{"full_name":"Aichholzer, Oswin","last_name":"Aichholzer","first_name":"Oswin"},{"id":"3207FDC6-F248-11E8-B48F-1D18A9856A87","last_name":"Arroyo Guevara","full_name":"Arroyo Guevara, Alan M","orcid":"0000-0003-2401-8670","first_name":"Alan M"},{"last_name":"Masárová","full_name":"Masárová, Zuzana","orcid":"0000-0002-6660-1322","first_name":"Zuzana","id":"45CFE238-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Irene","last_name":"Parada","full_name":"Parada, Irene"},{"first_name":"Daniel","full_name":"Perz, Daniel","last_name":"Perz"},{"last_name":"Pilz","full_name":"Pilz, Alexander","first_name":"Alexander"},{"orcid":"0000-0002-1097-9684","last_name":"Tkadlec","full_name":"Tkadlec, Josef","first_name":"Josef","id":"3F24CCC8-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Vogtenhuber, Birgit","last_name":"Vogtenhuber","first_name":"Birgit"}],"abstract":[{"text":" matching is compatible to two or more labeled point sets of size n with labels {1,…,n} if its straight-line drawing on each of these point sets is crossing-free. We study the maximum number of edges in a matching compatible to two or more labeled point sets in general position in the plane. We show that for any two labeled convex sets of n points there exists a compatible matching with ⌊2n−−√⌋ edges. More generally, for any ℓ labeled point sets we construct compatible matchings of size Ω(n1/ℓ) . As a corresponding upper bound, we use probabilistic arguments to show that for any ℓ given sets of n points there exists a labeling of each set such that the largest compatible matching has O(n2/(ℓ+1)) edges. Finally, we show that Θ(logn) copies of any set of n points are necessary and sufficient for the existence of a labeling such that any compatible matching consists only of a single edge.","lang":"eng"}],"main_file_link":[{"url":"https://arxiv.org/abs/2101.03928","open_access":"1"}],"alternative_title":["LNCS"],"related_material":{"record":[{"id":"11938","relation":"later_version","status":"public"}]},"ec_funded":1,"doi":"10.1007/978-3-030-68211-8_18","year":"2021","external_id":{"arxiv":["2101.03928"]},"title":"On compatible matchings"},{"page":"21-37","file_date_updated":"2021-06-28T13:33:23Z","publication":"Journal of Combinatorial Theory. Series B","type":"journal_article","day":"09","status":"public","intvolume":" 151","department":[{"_id":"HeEd"}],"has_accepted_license":"1","file":[{"creator":"asandaue","file_id":"9612","relation":"main_file","content_type":"application/pdf","success":1,"access_level":"open_access","date_updated":"2021-06-28T13:33:23Z","checksum":"15fbc9064cd9d1c777ac0043b78c8f12","date_created":"2021-06-28T13:33:23Z","file_size":418168,"file_name":"2021_JournalOfCombinatorialTheory_Pach.pdf"}],"date_created":"2021-06-27T22:01:47Z","article_type":"original","date_published":"2021-06-09T00:00:00Z","month":"06","language":[{"iso":"eng"}],"scopus_import":"1","publisher":"Elsevier","article_processing_charge":"No","volume":151,"date_updated":"2023-08-10T13:38:00Z","oa":1,"project":[{"call_identifier":"FWF","_id":"268116B8-B435-11E9-9278-68D0E5697425","name":"The Wittgenstein Prize","grant_number":"Z00342"}],"oa_version":"Published Version","quality_controlled":"1","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","acknowledgement":"We would like to thank the anonymous referees for their useful comments and suggestions. János Pach is partially supported by Austrian Science Fund (FWF) grant Z 342-N31 and by ERC Advanced grant “GeoScape.” István Tomon is partially supported by Swiss National Science Foundation grant no. 200021_196965, and thanks the support of MIPT Moscow. Both authors are partially supported by The Russian Government in the framework of MegaGrant no. 075-15-2019-1926.","publication_identifier":{"issn":["0095-8956"]},"_id":"9602","citation":{"ista":"Pach J, Tomon I. 2021. Erdős-Hajnal-type results for monotone paths. Journal of Combinatorial Theory. Series B. 151, 21–37.","short":"J. Pach, I. Tomon, Journal of Combinatorial Theory. Series B 151 (2021) 21–37.","mla":"Pach, János, and István Tomon. “Erdős-Hajnal-Type Results for Monotone Paths.” Journal of Combinatorial Theory. Series B, vol. 151, Elsevier, 2021, pp. 21–37, doi:10.1016/j.jctb.2021.05.004.","ama":"Pach J, Tomon I. Erdős-Hajnal-type results for monotone paths. Journal of Combinatorial Theory Series B. 2021;151:21-37. doi:10.1016/j.jctb.2021.05.004","chicago":"Pach, János, and István Tomon. “Erdős-Hajnal-Type Results for Monotone Paths.” Journal of Combinatorial Theory. Series B. Elsevier, 2021. https://doi.org/10.1016/j.jctb.2021.05.004.","apa":"Pach, J., & Tomon, I. (2021). Erdős-Hajnal-type results for monotone paths. Journal of Combinatorial Theory. Series B. Elsevier. https://doi.org/10.1016/j.jctb.2021.05.004","ieee":"J. Pach and I. Tomon, “Erdős-Hajnal-type results for monotone paths,” Journal of Combinatorial Theory. Series B, vol. 151. Elsevier, pp. 21–37, 2021."},"publication_status":"published","author":[{"first_name":"János","last_name":"Pach","full_name":"Pach, János","id":"E62E3130-B088-11EA-B919-BF823C25FEA4"},{"first_name":"István","full_name":"Tomon, István","last_name":"Tomon"}],"abstract":[{"text":"An ordered graph is a graph with a linear ordering on its vertex set. We prove that for every positive integer k, there exists a constant ck > 0 such that any ordered graph G on n vertices with the property that neither G nor its complement contains an induced monotone path of size k, has either a clique or an independent set of size at least n^ck . This strengthens a result of Bousquet, Lagoutte, and Thomassé, who proved the analogous result for unordered graphs.\r\nA key idea of the above paper was to show that any unordered graph on n vertices that does not contain an induced path of size k, and whose maximum degree is at most c(k)n for some small c(k) > 0, contains two disjoint linear size subsets with no edge between them. This approach fails for ordered graphs, because the analogous statement is false for k ≥ 3, by a construction of Fox. We provide some further examples showing that this statement also fails for ordered graphs avoiding other ordered trees.","lang":"eng"}],"isi":1,"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)"},"ddc":["510"],"year":"2021","doi":"10.1016/j.jctb.2021.05.004","title":"Erdős-Hajnal-type results for monotone paths","external_id":{"isi":["000702280800002"]}},{"date_published":"2021-06-02T00:00:00Z","month":"06","language":[{"iso":"eng"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","scopus_import":"1","department":[{"_id":"HeEd"}],"has_accepted_license":"1","file":[{"success":1,"creator":"asandaue","file_id":"9611","content_type":"application/pdf","relation":"main_file","date_created":"2021-06-28T13:11:39Z","checksum":"22b11a719018b22ecba2471b51f2eb40","file_name":"2021_LIPIcs_Biswas.pdf","file_size":727817,"date_updated":"2021-06-28T13:11:39Z","access_level":"open_access"}],"date_created":"2021-06-27T22:01:48Z","conference":{"name":"SoCG: International Symposium on Computational Geometry","end_date":"2021-06-11","location":"Online","start_date":"2021-06-07"},"type":"conference","day":"02","status":"public","intvolume":" 189","file_date_updated":"2021-06-28T13:11:39Z","publication":"Leibniz International Proceedings in Informatics","ec_funded":1,"doi":"10.4230/LIPIcs.SoCG.2021.16","year":"2021","title":"Counting cells of order-k voronoi tessellations in ℝ3 with morse theory","article_number":"16","alternative_title":["LIPIcs"],"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)"},"ddc":["516"],"publication_status":"published","citation":{"mla":"Biswas, Ranita, et al. “Counting Cells of Order-k Voronoi Tessellations in ℝ3 with Morse Theory.” Leibniz International Proceedings in Informatics, vol. 189, 16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021, doi:10.4230/LIPIcs.SoCG.2021.16.","ama":"Biswas R, Cultrera di Montesano S, Edelsbrunner H, Saghafian M. Counting cells of order-k voronoi tessellations in ℝ3 with morse theory. In: Leibniz International Proceedings in Informatics. Vol 189. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2021. doi:10.4230/LIPIcs.SoCG.2021.16","ista":"Biswas R, Cultrera di Montesano S, Edelsbrunner H, Saghafian M. 2021. Counting cells of order-k voronoi tessellations in ℝ3 with morse theory. Leibniz International Proceedings in Informatics. SoCG: International Symposium on Computational Geometry, LIPIcs, vol. 189, 16.","short":"R. Biswas, S. Cultrera di Montesano, H. Edelsbrunner, M. Saghafian, in:, Leibniz International Proceedings in Informatics, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.","apa":"Biswas, R., Cultrera di Montesano, S., Edelsbrunner, H., & Saghafian, M. (2021). Counting cells of order-k voronoi tessellations in ℝ3 with morse theory. In Leibniz International Proceedings in Informatics (Vol. 189). Online: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2021.16","ieee":"R. Biswas, S. Cultrera di Montesano, H. Edelsbrunner, and M. Saghafian, “Counting cells of order-k voronoi tessellations in ℝ3 with morse theory,” in Leibniz International Proceedings in Informatics, Online, 2021, vol. 189.","chicago":"Biswas, Ranita, Sebastiano Cultrera di Montesano, Herbert Edelsbrunner, and Morteza Saghafian. “Counting Cells of Order-k Voronoi Tessellations in ℝ3 with Morse Theory.” In Leibniz International Proceedings in Informatics, Vol. 189. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. https://doi.org/10.4230/LIPIcs.SoCG.2021.16."},"author":[{"id":"3C2B033E-F248-11E8-B48F-1D18A9856A87","first_name":"Ranita","orcid":"0000-0002-5372-7890","last_name":"Biswas","full_name":"Biswas, Ranita"},{"id":"34D2A09C-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-6249-0832","last_name":"Cultrera di Montesano","full_name":"Cultrera di Montesano, Sebastiano","first_name":"Sebastiano"},{"id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","last_name":"Edelsbrunner","full_name":"Edelsbrunner, Herbert","orcid":"0000-0002-9823-6833","first_name":"Herbert"},{"first_name":"Morteza","last_name":"Saghafian","full_name":"Saghafian, Morteza"}],"abstract":[{"lang":"eng","text":"Generalizing Lee’s inductive argument for counting the cells of higher order Voronoi tessellations in ℝ² to ℝ³, we get precise relations in terms of Morse theoretic quantities for piecewise constant functions on planar arrangements. Specifically, we prove that for a generic set of n ≥ 5 points in ℝ³, the number of regions in the order-k Voronoi tessellation is N_{k-1} - binom(k,2)n + n, for 1 ≤ k ≤ n-1, in which N_{k-1} is the sum of Euler characteristics of these function’s first k-1 sublevel sets. We get similar expressions for the vertices, edges, and polygons of the order-k Voronoi tessellation."}],"oa":1,"volume":189,"date_updated":"2023-02-23T14:02:28Z","article_processing_charge":"No","user_id":"D865714E-FA4E-11E9-B85B-F5C5E5697425","quality_controlled":"1","project":[{"grant_number":"788183","name":"Alpha Shape Theory Extended","_id":"266A2E9E-B435-11E9-9278-68D0E5697425","call_identifier":"H2020"},{"grant_number":"Z00342","call_identifier":"FWF","_id":"268116B8-B435-11E9-9278-68D0E5697425","name":"The Wittgenstein Prize"},{"name":"Discretization in Geometry and Dynamics","_id":"0aa4bc98-070f-11eb-9043-e6fff9c6a316","grant_number":"I4887"}],"oa_version":"Published Version","_id":"9604","publication_identifier":{"issn":["18688969"],"isbn":["9783959771849"]}},{"ddc":["540"],"isi":1,"title":"Topological signatures and stability of hexagonal close packing and Barlow stackings","external_id":{"isi":["000700090000001"],"pmid":["34569592"]},"year":"2021","doi":"10.1039/d1sm00774b","ec_funded":1,"_id":"10204","pmid":1,"publication_identifier":{"issn":["1744-683X"],"eissn":["1744-6848"]},"acknowledgement":"MS acknowledges the support by Australian Research Council funding through the ARC Training Centre for M3D Innovation (IC180100008). MS thanks M. Hanifpour and N. Francois for their input and valuable discussions. This project has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme, grant no. 788183 and from the Wittgenstein Prize, Austrian Science Fund (FWF), grant no. Z 342-N31.","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","quality_controlled":"1","project":[{"name":"Alpha Shape Theory Extended","_id":"266A2E9E-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","grant_number":"788183"},{"_id":"268116B8-B435-11E9-9278-68D0E5697425","name":"The Wittgenstein Prize","call_identifier":"FWF","grant_number":"Z00342"}],"oa_version":"Submitted Version","date_updated":"2023-10-03T09:24:27Z","volume":17,"oa":1,"article_processing_charge":"No","abstract":[{"lang":"eng","text":"Two common representations of close packings of identical spheres consisting of hexagonal layers, called Barlow stackings, appear abundantly in minerals and metals. These motifs, however, occupy an identical portion of space and bear identical first-order topological signatures as measured by persistent homology. Here we present a novel method based on k-fold covers that unambiguously distinguishes between these patterns. Moreover, our approach provides topological evidence that the FCC motif is the more stable of the two in the context of evolving experimental sphere packings during the transition from disordered to an ordered state. We conclude that our approach can be generalised to distinguish between various Barlow stackings manifested in minerals and metals."}],"author":[{"orcid":"0000-0002-8882-5116","full_name":"Osang, Georg F","last_name":"Osang","first_name":"Georg F","id":"464B40D6-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Edelsbrunner","full_name":"Edelsbrunner, Herbert","orcid":"0000-0002-9823-6833","first_name":"Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Mohammad","full_name":"Saadatfar, Mohammad","last_name":"Saadatfar"}],"publication_status":"published","citation":{"apa":"Osang, G. F., Edelsbrunner, H., & Saadatfar, M. (2021). Topological signatures and stability of hexagonal close packing and Barlow stackings. Soft Matter. Royal Society of Chemistry . https://doi.org/10.1039/d1sm00774b","ieee":"G. F. Osang, H. Edelsbrunner, and M. Saadatfar, “Topological signatures and stability of hexagonal close packing and Barlow stackings,” Soft Matter, vol. 17, no. 40. Royal Society of Chemistry , pp. 9107–9115, 2021.","chicago":"Osang, Georg F, Herbert Edelsbrunner, and Mohammad Saadatfar. “Topological Signatures and Stability of Hexagonal Close Packing and Barlow Stackings.” Soft Matter. Royal Society of Chemistry , 2021. https://doi.org/10.1039/d1sm00774b.","mla":"Osang, Georg F., et al. “Topological Signatures and Stability of Hexagonal Close Packing and Barlow Stackings.” Soft Matter, vol. 17, no. 40, Royal Society of Chemistry , 2021, pp. 9107–15, doi:10.1039/d1sm00774b.","ama":"Osang GF, Edelsbrunner H, Saadatfar M. Topological signatures and stability of hexagonal close packing and Barlow stackings. Soft Matter. 2021;17(40):9107-9115. doi:10.1039/d1sm00774b","short":"G.F. Osang, H. Edelsbrunner, M. Saadatfar, Soft Matter 17 (2021) 9107–9115.","ista":"Osang GF, Edelsbrunner H, Saadatfar M. 2021. Topological signatures and stability of hexagonal close packing and Barlow stackings. Soft Matter. 17(40), 9107–9115."},"file":[{"relation":"main_file","content_type":"application/pdf","creator":"dernst","file_id":"14385","success":1,"access_level":"open_access","date_updated":"2023-10-03T09:21:42Z","file_size":4678788,"file_name":"2021_SoftMatter_acceptedversion_Osang.pdf","checksum":"b4da0c420530295e61b153960f6cb350","date_created":"2023-10-03T09:21:42Z"}],"date_created":"2021-10-31T23:01:30Z","has_accepted_license":"1","department":[{"_id":"HeEd"}],"publisher":"Royal Society of Chemistry ","scopus_import":"1","language":[{"iso":"eng"}],"month":"10","date_published":"2021-10-20T00:00:00Z","article_type":"original","issue":"40","publication":"Soft Matter","file_date_updated":"2023-10-03T09:21:42Z","page":"9107-9115","intvolume":" 17","status":"public","day":"20","type":"journal_article"},{"date_published":"2021-10-25T00:00:00Z","article_type":"original","month":"10","language":[{"iso":"eng"}],"scopus_import":"1","publisher":"Taylor and Francis","department":[{"_id":"HeEd"}],"has_accepted_license":"1","file":[{"success":1,"creator":"dernst","file_id":"14053","content_type":"application/pdf","relation":"main_file","date_created":"2023-08-14T11:55:10Z","checksum":"3514382e3a1eb87fa6c61ad622874415","file_name":"2023_ExperimentalMath_Akopyan.pdf","file_size":1966019,"date_updated":"2023-08-14T11:55:10Z","access_level":"open_access"}],"date_created":"2021-11-07T23:01:25Z","type":"journal_article","day":"25","status":"public","page":"1-15","file_date_updated":"2023-08-14T11:55:10Z","publication":"Experimental Mathematics","ec_funded":1,"doi":"10.1080/10586458.2021.1980459","year":"2021","title":"The beauty of random polytopes inscribed in the 2-sphere","external_id":{"isi":["000710893500001"],"arxiv":["2007.07783"]},"isi":1,"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)"},"ddc":["510"],"citation":{"short":"A. Akopyan, H. Edelsbrunner, A. Nikitenko, Experimental Mathematics (2021) 1–15.","ista":"Akopyan A, Edelsbrunner H, Nikitenko A. 2021. The beauty of random polytopes inscribed in the 2-sphere. Experimental Mathematics., 1–15.","ama":"Akopyan A, Edelsbrunner H, Nikitenko A. The beauty of random polytopes inscribed in the 2-sphere. Experimental Mathematics. 2021:1-15. doi:10.1080/10586458.2021.1980459","mla":"Akopyan, Arseniy, et al. “The Beauty of Random Polytopes Inscribed in the 2-Sphere.” Experimental Mathematics, Taylor and Francis, 2021, pp. 1–15, doi:10.1080/10586458.2021.1980459.","chicago":"Akopyan, Arseniy, Herbert Edelsbrunner, and Anton Nikitenko. “The Beauty of Random Polytopes Inscribed in the 2-Sphere.” Experimental Mathematics. Taylor and Francis, 2021. https://doi.org/10.1080/10586458.2021.1980459.","apa":"Akopyan, A., Edelsbrunner, H., & Nikitenko, A. (2021). The beauty of random polytopes inscribed in the 2-sphere. Experimental Mathematics. Taylor and Francis. https://doi.org/10.1080/10586458.2021.1980459","ieee":"A. Akopyan, H. Edelsbrunner, and A. Nikitenko, “The beauty of random polytopes inscribed in the 2-sphere,” Experimental Mathematics. Taylor and Francis, pp. 1–15, 2021."},"publication_status":"published","author":[{"last_name":"Akopyan","full_name":"Akopyan, Arseniy","orcid":"0000-0002-2548-617X","first_name":"Arseniy","id":"430D2C90-F248-11E8-B48F-1D18A9856A87"},{"id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","first_name":"Herbert","last_name":"Edelsbrunner","full_name":"Edelsbrunner, Herbert","orcid":"0000-0002-9823-6833"},{"id":"3E4FF1BA-F248-11E8-B48F-1D18A9856A87","first_name":"Anton","last_name":"Nikitenko","full_name":"Nikitenko, Anton","orcid":"0000-0002-0659-3201"}],"abstract":[{"lang":"eng","text":"Consider a random set of points on the unit sphere in ℝd, which can be either uniformly sampled or a Poisson point process. Its convex hull is a random inscribed polytope, whose boundary approximates the sphere. We focus on the case d = 3, for which there are elementary proofs and fascinating formulas for metric properties. In particular, we study the fraction of acute facets, the expected intrinsic volumes, the total edge length, and the distance to a fixed point. Finally we generalize the results to the ellipsoid with homeoid density."}],"article_processing_charge":"Yes (via OA deal)","oa":1,"date_updated":"2023-08-14T11:57:07Z","arxiv":1,"oa_version":"Published Version","quality_controlled":"1","project":[{"_id":"266A2E9E-B435-11E9-9278-68D0E5697425","name":"Alpha Shape Theory Extended","call_identifier":"H2020","grant_number":"788183"},{"name":"The Wittgenstein Prize","_id":"268116B8-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"Z00342"},{"grant_number":"I4887","_id":"0aa4bc98-070f-11eb-9043-e6fff9c6a316","name":"Discretization in Geometry and Dynamics"},{"grant_number":"I02979-N35","call_identifier":"FWF","name":"Persistence and stability of geometric complexes","_id":"2561EBF4-B435-11E9-9278-68D0E5697425"}],"acknowledgement":"This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme, grant no. 788183, from the Wittgenstein Prize, Austrian Science Fund (FWF), grant no. Z 342-N31, and from the DFG Collaborative Research Center TRR 109, ‘Discretization in Geometry and Dynamics’, Austrian Science Fund (FWF), grant no. I 02979-N35.\r\nWe are grateful to Dmitry Zaporozhets and Christoph Thäle for valuable comments and for directing us to relevant references. We also thank to Anton Mellit for a useful discussion on Bessel functions.","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication_identifier":{"eissn":["1944-950X"],"issn":["1058-6458"]},"_id":"10222"},{"quality_controlled":"1","project":[{"call_identifier":"FWF","_id":"268116B8-B435-11E9-9278-68D0E5697425","name":"The Wittgenstein Prize","grant_number":"Z00342"}],"oa_version":"Preprint","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","publication_identifier":{"eissn":["14320444"],"issn":["01795376"]},"_id":"7962","article_processing_charge":"No","volume":63,"date_updated":"2023-08-21T08:49:18Z","oa":1,"arxiv":1,"author":[{"id":"E62E3130-B088-11EA-B919-BF823C25FEA4","first_name":"János","last_name":"Pach","full_name":"Pach, János"},{"first_name":"Bruce","full_name":"Reed, Bruce","last_name":"Reed"},{"first_name":"Yelena","full_name":"Yuditsky, Yelena","last_name":"Yuditsky"}],"abstract":[{"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.","lang":"eng"}],"citation":{"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","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.","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.","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","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.","short":"J. Pach, B. Reed, Y. Yuditsky, Discrete and Computational Geometry 63 (2020) 888–917.","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."},"publication_status":"published","main_file_link":[{"url":"https://arxiv.org/abs/1803.06710","open_access":"1"}],"isi":1,"external_id":{"arxiv":["1803.06710"],"isi":["000538229000001"]},"title":"Almost all string graphs are intersection graphs of plane convex sets","doi":"10.1007/s00454-020-00213-z","year":"2020","page":"888-917","publication":"Discrete and Computational Geometry","issue":"4","status":"public","intvolume":" 63","type":"journal_article","day":"05","date_created":"2020-06-14T22:00:51Z","department":[{"_id":"HeEd"}],"language":[{"iso":"eng"}],"scopus_import":"1","publisher":"Springer Nature","date_published":"2020-06-05T00:00:00Z","article_type":"original","month":"06"},{"day":"24","type":"journal_article","intvolume":" 57","status":"public","issue":"2","publication":"Studia Scientiarum Mathematicarum Hungarica","page":"193-199","file_date_updated":"2020-07-24T07:09:06Z","month":"07","date_published":"2020-07-24T00:00:00Z","article_type":"original","publisher":"Akadémiai Kiadó","scopus_import":"1","language":[{"iso":"eng"}],"has_accepted_license":"1","department":[{"_id":"HeEd"}],"date_created":"2020-07-24T07:09:18Z","file":[{"file_name":"57-2-05_4214-1454Vegter-Wintraecken_OpenAccess_CC-BY-NC.pdf","file_size":1476072,"date_created":"2020-07-24T07:09:06Z","date_updated":"2020-07-24T07:09:06Z","access_level":"open_access","content_type":"application/pdf","relation":"main_file","file_id":"8164","creator":"mwintrae"}],"publication_status":"published","citation":{"chicago":"Vegter, Gert, and Mathijs Wintraecken. “Refutation of a Claim Made by Fejes Tóth on the Accuracy of Surface Meshes.” Studia Scientiarum Mathematicarum Hungarica. Akadémiai Kiadó, 2020. https://doi.org/10.1556/012.2020.57.2.1454.","ieee":"G. Vegter and M. Wintraecken, “Refutation of a claim made by Fejes Tóth on the accuracy of surface meshes,” Studia Scientiarum Mathematicarum Hungarica, vol. 57, no. 2. Akadémiai Kiadó, pp. 193–199, 2020.","apa":"Vegter, G., & Wintraecken, M. (2020). Refutation of a claim made by Fejes Tóth on the accuracy of surface meshes. Studia Scientiarum Mathematicarum Hungarica. Akadémiai Kiadó. https://doi.org/10.1556/012.2020.57.2.1454","short":"G. Vegter, M. Wintraecken, Studia Scientiarum Mathematicarum Hungarica 57 (2020) 193–199.","ista":"Vegter G, Wintraecken M. 2020. Refutation of a claim made by Fejes Tóth on the accuracy of surface meshes. Studia Scientiarum Mathematicarum Hungarica. 57(2), 193–199.","mla":"Vegter, Gert, and Mathijs Wintraecken. “Refutation of a Claim Made by Fejes Tóth on the Accuracy of Surface Meshes.” Studia Scientiarum Mathematicarum Hungarica, vol. 57, no. 2, Akadémiai Kiadó, 2020, pp. 193–99, doi:10.1556/012.2020.57.2.1454.","ama":"Vegter G, Wintraecken M. Refutation of a claim made by Fejes Tóth on the accuracy of surface meshes. Studia Scientiarum Mathematicarum Hungarica. 2020;57(2):193-199. doi:10.1556/012.2020.57.2.1454"},"abstract":[{"lang":"eng","text":"Fejes Tóth [3] studied approximations of smooth surfaces in three-space by piecewise flat triangular meshes with a given number of vertices on the surface that are optimal with respect to Hausdorff distance. He proves that this Hausdorff distance decreases inversely proportional with the number of vertices of the approximating mesh if the surface is convex. He also claims that this Hausdorff distance is inversely proportional to the square of the number of vertices for a specific non-convex surface, namely a one-sheeted hyperboloid of revolution bounded by two congruent circles. We refute this claim, and show that the asymptotic behavior of the Hausdorff distance is linear, that is the same as for convex surfaces."}],"author":[{"last_name":"Vegter","full_name":"Vegter, Gert","first_name":"Gert"},{"id":"307CFBC8-F248-11E8-B48F-1D18A9856A87","first_name":"Mathijs","full_name":"Wintraecken, Mathijs","last_name":"Wintraecken","orcid":"0000-0002-7472-2220"}],"oa":1,"volume":57,"date_updated":"2023-10-10T13:05:27Z","article_processing_charge":"No","_id":"8163","publication_identifier":{"eissn":["1588-2896"],"issn":["0081-6906"]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","acknowledgement":"The authors are greatly indebted to Dror Atariah, Günther Rote and John Sullivan for discussion and suggestions. The authors also thank Jean-Daniel Boissonnat, Ramsay Dyer, David de Laat and Rien van de Weijgaert for discussion. This work has been supported in part by the European Union’s Seventh Framework Programme for Research of the\r\nEuropean Commission, under FET-Open grant number 255827 (CGL Computational Geometry Learning) and ERC Grant Agreement number 339025 GUDHI (Algorithmic Foundations of Geometry Understanding in Higher Dimensions), the European Union’s Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreement number 754411,and the Austrian Science Fund (FWF): Z00342 N31.","quality_controlled":"1","oa_version":"Published Version","project":[{"grant_number":"754411","_id":"260C2330-B435-11E9-9278-68D0E5697425","name":"ISTplus - Postdoctoral Fellowships","call_identifier":"H2020"},{"grant_number":"Z00342","name":"The Wittgenstein Prize","_id":"268116B8-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"}],"year":"2020","doi":"10.1556/012.2020.57.2.1454","ec_funded":1,"title":"Refutation of a claim made by Fejes Tóth on the accuracy of surface meshes","external_id":{"isi":["000570978400005"]},"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by-nc/4.0/legalcode","image":"/images/cc_by_nc.png","name":"Creative Commons Attribution-NonCommercial 4.0 International (CC BY-NC 4.0)","short":"CC BY-NC (4.0)"},"isi":1,"ddc":["510"]},{"conference":{"start_date":"2020-09-16","end_date":"2020-09-18","location":"Virtual, Online","name":"GD: Graph Drawing and Network Visualization"},"date_created":"2021-03-28T22:01:44Z","department":[{"_id":"HeEd"}],"scopus_import":"1","publisher":"Springer Nature","language":[{"iso":"eng"}],"month":"09","date_published":"2020-09-20T00:00:00Z","publication":"28th International Symposium on Graph Drawing and Network Visualization","page":"359-371","intvolume":" 12590","status":"public","day":"20","series_title":"LNCS","type":"conference","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/2006.14908"}],"external_id":{"arxiv":["2006.14908"]},"title":"Crossings between non-homotopic edges","year":"2020","doi":"10.1007/978-3-030-68766-3_28","publication_identifier":{"eissn":["1611-3349"],"issn":["0302-9743"],"isbn":["9783030687656"]},"_id":"9299","project":[{"call_identifier":"FWF","_id":"268116B8-B435-11E9-9278-68D0E5697425","name":"The Wittgenstein Prize","grant_number":"Z00342"}],"oa_version":"Preprint","quality_controlled":"1","acknowledgement":"Supported by the National Research, Development and Innovation Office, NKFIH, KKP-133864, K-131529, K-116769, K-132696, by the Higher Educational Institutional Excellence Program 2019 NKFIH-1158-6/2019, the Austrian Science Fund (FWF), grant Z 342-N31, by the Ministry of Education and Science of the Russian Federation MegaGrant No. 075-15-2019-1926, and by the ERC Synergy Grant “Dynasnet” No. 810115. A full version can be found at https://arxiv.org/abs/2006.14908.","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","arxiv":1,"article_processing_charge":"No","date_updated":"2021-04-06T11:32:32Z","volume":12590,"oa":1,"abstract":[{"lang":"eng","text":"We call a multigraph non-homotopic if it can be drawn in the plane in such a way that no two edges connecting the same pair of vertices can be continuously transformed into each other without passing through a vertex, and no loop can be shrunk to its end-vertex in the same way. It is easy to see that a non-homotopic multigraph on n>1 vertices can have arbitrarily many edges. We prove that the number of crossings between the edges of a non-homotopic multigraph with n vertices and m>4n edges is larger than cm2n for some constant c>0 , and that this bound is tight up to a polylogarithmic factor. We also show that the lower bound is not asymptotically sharp as n is fixed and m⟶∞ ."}],"author":[{"id":"E62E3130-B088-11EA-B919-BF823C25FEA4","full_name":"Pach, János","last_name":"Pach","first_name":"János"},{"first_name":"Gábor","last_name":"Tardos","full_name":"Tardos, Gábor"},{"first_name":"Géza","last_name":"Tóth","full_name":"Tóth, Géza"}],"citation":{"ieee":"J. Pach, G. Tardos, and G. Tóth, “Crossings between non-homotopic edges,” in 28th International Symposium on Graph Drawing and Network Visualization, Virtual, Online, 2020, vol. 12590, pp. 359–371.","apa":"Pach, J., Tardos, G., & Tóth, G. (2020). Crossings between non-homotopic edges. In 28th International Symposium on Graph Drawing and Network Visualization (Vol. 12590, pp. 359–371). Virtual, Online: Springer Nature. https://doi.org/10.1007/978-3-030-68766-3_28","chicago":"Pach, János, Gábor Tardos, and Géza Tóth. “Crossings between Non-Homotopic Edges.” In 28th International Symposium on Graph Drawing and Network Visualization, 12590:359–71. LNCS. Springer Nature, 2020. https://doi.org/10.1007/978-3-030-68766-3_28.","ama":"Pach J, Tardos G, Tóth G. Crossings between non-homotopic edges. In: 28th International Symposium on Graph Drawing and Network Visualization. Vol 12590. LNCS. Springer Nature; 2020:359-371. doi:10.1007/978-3-030-68766-3_28","mla":"Pach, János, et al. “Crossings between Non-Homotopic Edges.” 28th International Symposium on Graph Drawing and Network Visualization, vol. 12590, Springer Nature, 2020, pp. 359–71, doi:10.1007/978-3-030-68766-3_28.","ista":"Pach J, Tardos G, Tóth G. 2020. Crossings between non-homotopic edges. 28th International Symposium on Graph Drawing and Network Visualization. GD: Graph Drawing and Network VisualizationLNCS vol. 12590, 359–371.","short":"J. Pach, G. Tardos, G. Tóth, in:, 28th International Symposium on Graph Drawing and Network Visualization, Springer Nature, 2020, pp. 359–371."},"publication_status":"published"}]