[{"type":"conference","article_number":"8917514","abstract":[{"lang":"eng","text":"We present LiveTraVeL (Live Transit Vehicle Labeling), a real-time system to label a stream of noisy observations of transit vehicle trajectories with the transit routes they are serving (e.g., northbound bus #5). In order to scale efficiently to large transit networks, our system first retrieves a small set of candidate routes from a geometrically indexed data structure, then applies a fine-grained scoring step to choose the best match. Given that real-time data remains unavailable for the majority of the world’s transit agencies, these inferences can help feed a real-time map of a transit system’s trips, infer transit trip delays in real time, or measure and correct noisy transit tracking data. This system can run on vehicle observations from a variety of sources that don’t attach route information to vehicle observations, such as public imagery streams or user-contributed transit vehicle sightings.We abstract away the specifics of the sensing system and demonstrate the effectiveness of our system on a \"semisynthetic\" dataset of all New York City buses, where we simulate sensed trajectories by starting with fully labeled vehicle trajectories reported via the GTFS-Realtime protocol, removing the transit route IDs, and perturbing locations with synthetic noise. Using just the geometric shapes of the trajectories, we demonstrate that our system converges on the correct route ID within a few minutes, even after a vehicle switches from serving one trip to the next."}],"year":"2019","_id":"7216","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","department":[{"_id":"HeEd"}],"publisher":"IEEE","status":"public","title":"LiveTraVeL: Real-time matching of transit vehicle trajectories to transit routes at scale","publication_status":"published","author":[{"orcid":"0000-0002-8882-5116","id":"464B40D6-F248-11E8-B48F-1D18A9856A87","last_name":"Osang","first_name":"Georg F","full_name":"Osang, Georg F"},{"first_name":"James","last_name":"Cook","full_name":"Cook, James"},{"full_name":"Fabrikant, Alex","first_name":"Alex","last_name":"Fabrikant"},{"full_name":"Gruteser, Marco","first_name":"Marco","last_name":"Gruteser"}],"oa_version":"None","date_updated":"2023-09-06T14:50:28Z","date_created":"2019-12-29T23:00:47Z","scopus_import":"1","article_processing_charge":"No","publication_identifier":{"isbn":["9781538670248"]},"month":"11","day":"28","external_id":{"isi":["000521238102050"]},"citation":{"ieee":"G. F. Osang, J. Cook, A. Fabrikant, and M. Gruteser, “LiveTraVeL: Real-time matching of transit vehicle trajectories to transit routes at scale,” in 2019 IEEE Intelligent Transportation Systems Conference, Auckland, New Zealand, 2019.","apa":"Osang, G. F., Cook, J., Fabrikant, A., & Gruteser, M. (2019). LiveTraVeL: Real-time matching of transit vehicle trajectories to transit routes at scale. In 2019 IEEE Intelligent Transportation Systems Conference. Auckland, New Zealand: IEEE. https://doi.org/10.1109/ITSC.2019.8917514","ista":"Osang GF, Cook J, Fabrikant A, Gruteser M. 2019. LiveTraVeL: Real-time matching of transit vehicle trajectories to transit routes at scale. 2019 IEEE Intelligent Transportation Systems Conference. ITSC: Intelligent Transportation Systems Conference, 8917514.","ama":"Osang GF, Cook J, Fabrikant A, Gruteser M. LiveTraVeL: Real-time matching of transit vehicle trajectories to transit routes at scale. In: 2019 IEEE Intelligent Transportation Systems Conference. IEEE; 2019. doi:10.1109/ITSC.2019.8917514","chicago":"Osang, Georg F, James Cook, Alex Fabrikant, and Marco Gruteser. “LiveTraVeL: Real-Time Matching of Transit Vehicle Trajectories to Transit Routes at Scale.” In 2019 IEEE Intelligent Transportation Systems Conference. IEEE, 2019. https://doi.org/10.1109/ITSC.2019.8917514.","short":"G.F. Osang, J. Cook, A. Fabrikant, M. Gruteser, in:, 2019 IEEE Intelligent Transportation Systems Conference, IEEE, 2019.","mla":"Osang, Georg F., et al. “LiveTraVeL: Real-Time Matching of Transit Vehicle Trajectories to Transit Routes at Scale.” 2019 IEEE Intelligent Transportation Systems Conference, 8917514, IEEE, 2019, doi:10.1109/ITSC.2019.8917514."},"publication":"2019 IEEE Intelligent Transportation Systems Conference","quality_controlled":"1","isi":1,"date_published":"2019-11-28T00:00:00Z","doi":"10.1109/ITSC.2019.8917514","conference":{"end_date":"2019-10-30","start_date":"2019-10-27","location":"Auckland, New Zealand","name":"ITSC: Intelligent Transportation Systems Conference"},"language":[{"iso":"eng"}]},{"license":"https://creativecommons.org/licenses/by/4.0/","file_date_updated":"2020-07-14T12:47:10Z","ec_funded":1,"date_updated":"2023-09-07T12:07:12Z","date_created":"2018-12-16T22:59:20Z","volume":62,"author":[{"full_name":"Edelsbrunner, Herbert","last_name":"Edelsbrunner","first_name":"Herbert","orcid":"0000-0002-9823-6833","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Nikitenko, Anton","last_name":"Nikitenko","first_name":"Anton","orcid":"0000-0002-0659-3201","id":"3E4FF1BA-F248-11E8-B48F-1D18A9856A87"}],"related_material":{"record":[{"id":"6287","relation":"dissertation_contains","status":"public"}]},"publication_status":"published","department":[{"_id":"HeEd"}],"publisher":"Springer","year":"2019","month":"12","publication_identifier":{"issn":["01795376"],"eissn":["14320444"]},"language":[{"iso":"eng"}],"doi":"10.1007/s00454-018-0049-2","quality_controlled":"1","isi":1,"project":[{"name":"Alpha Shape Theory Extended","call_identifier":"H2020","grant_number":"788183","_id":"266A2E9E-B435-11E9-9278-68D0E5697425"},{"call_identifier":"FWF","name":"Persistence and stability of geometric complexes","_id":"2561EBF4-B435-11E9-9278-68D0E5697425","grant_number":"I02979-N35"},{"_id":"B67AFEDC-15C9-11EA-A837-991A96BB2854","name":"IST Austria Open Access Fund"}],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"oa":1,"external_id":{"arxiv":["1709.09380"],"isi":["000494042900008"]},"abstract":[{"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.","lang":"eng"}],"issue":"4","type":"journal_article","oa_version":"Published Version","file":[{"file_id":"5932","relation":"main_file","date_created":"2019-02-06T10:10:46Z","date_updated":"2020-07-14T12:47:10Z","checksum":"f9d00e166efaccb5a76bbcbb4dcea3b4","file_name":"2018_DiscreteCompGeometry_Edelsbrunner.pdf","access_level":"open_access","creator":"dernst","content_type":"application/pdf","file_size":599339}],"status":"public","title":"Poisson–Delaunay Mosaics of Order k","ddc":["516"],"intvolume":" 62","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","_id":"5678","day":"01","article_processing_charge":"Yes (via OA deal)","has_accepted_license":"1","scopus_import":"1","date_published":"2019-12-01T00:00:00Z","article_type":"original","page":"865–878","publication":"Discrete and Computational Geometry","citation":{"short":"H. Edelsbrunner, A. Nikitenko, Discrete and Computational Geometry 62 (2019) 865–878.","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.","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.","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","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.","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","ista":"Edelsbrunner H, Nikitenko A. 2019. Poisson–Delaunay Mosaics of Order k. Discrete and Computational Geometry. 62(4), 865–878."}},{"ec_funded":1,"file_date_updated":"2020-07-14T12:47:34Z","license":"https://creativecommons.org/licenses/by-nc-nd/4.0/","related_material":{"record":[{"relation":"dissertation_contains","status":"public","id":"7460"}]},"author":[{"full_name":"Edelsbrunner, Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9823-6833","first_name":"Herbert","last_name":"Edelsbrunner"},{"full_name":"Ölsböck, Katharina","last_name":"Ölsböck","first_name":"Katharina","orcid":"0000-0002-4672-8297","id":"4D4AA390-F248-11E8-B48F-1D18A9856A87"}],"volume":73,"date_updated":"2023-09-07T13:15:29Z","date_created":"2019-07-07T21:59:20Z","year":"2019","publisher":"Elsevier","department":[{"_id":"HeEd"}],"publication_status":"published","month":"08","doi":"10.1016/j.cagd.2019.06.003","language":[{"iso":"eng"}],"external_id":{"isi":["000485207800001"]},"tmp":{"name":"Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0)","legal_code_url":"https://creativecommons.org/licenses/by-nc-nd/4.0/legalcode","short":"CC BY-NC-ND (4.0)","image":"/images/cc_by_nc_nd.png"},"oa":1,"project":[{"call_identifier":"H2020","name":"Alpha Shape Theory Extended","grant_number":"788183","_id":"266A2E9E-B435-11E9-9278-68D0E5697425"},{"call_identifier":"FWF","name":"Persistence and stability of geometric complexes","grant_number":"I02979-N35","_id":"2561EBF4-B435-11E9-9278-68D0E5697425"}],"isi":1,"quality_controlled":"1","abstract":[{"text":"We use the canonical bases produced by the tri-partition algorithm in (Edelsbrunner and Ölsböck, 2018) to open and close holes in a polyhedral complex, K. In a concrete application, we consider the Delaunay mosaic of a finite set, we let K be an Alpha complex, and we use the persistence diagram of the distance function to guide the hole opening and closing operations. The dependences between the holes define a partial order on the cells in K that characterizes what can and what cannot be constructed using the operations. The relations in this partial order reveal structural information about the underlying filtration of complexes beyond what is expressed by the persistence diagram.","lang":"eng"}],"type":"journal_article","oa_version":"Published Version","file":[{"access_level":"open_access","file_name":"Elsevier_2019_Edelsbrunner.pdf","creator":"kschuh","content_type":"application/pdf","file_size":2665013,"file_id":"6624","relation":"main_file","checksum":"7c99be505dc7533257d42eb1830cef04","date_created":"2019-07-08T15:24:26Z","date_updated":"2020-07-14T12:47:34Z"}],"_id":"6608","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","intvolume":" 73","ddc":["000"],"status":"public","title":"Holes and dependences in an ordered complex","has_accepted_license":"1","article_processing_charge":"No","day":"01","scopus_import":"1","date_published":"2019-08-01T00:00:00Z","citation":{"ieee":"H. Edelsbrunner and K. Ölsböck, “Holes and dependences in an ordered complex,” Computer Aided Geometric Design, vol. 73. Elsevier, pp. 1–15, 2019.","apa":"Edelsbrunner, H., & Ölsböck, K. (2019). Holes and dependences in an ordered complex. Computer Aided Geometric Design. Elsevier. https://doi.org/10.1016/j.cagd.2019.06.003","ista":"Edelsbrunner H, Ölsböck K. 2019. Holes and dependences in an ordered complex. Computer Aided Geometric Design. 73, 1–15.","ama":"Edelsbrunner H, Ölsböck K. Holes and dependences in an ordered complex. Computer Aided Geometric Design. 2019;73:1-15. doi:10.1016/j.cagd.2019.06.003","chicago":"Edelsbrunner, Herbert, and Katharina Ölsböck. “Holes and Dependences in an Ordered Complex.” Computer Aided Geometric Design. Elsevier, 2019. https://doi.org/10.1016/j.cagd.2019.06.003.","short":"H. Edelsbrunner, K. Ölsböck, Computer Aided Geometric Design 73 (2019) 1–15.","mla":"Edelsbrunner, Herbert, and Katharina Ölsböck. “Holes and Dependences in an Ordered Complex.” Computer Aided Geometric Design, vol. 73, Elsevier, 2019, pp. 1–15, doi:10.1016/j.cagd.2019.06.003."},"publication":"Computer Aided Geometric Design","page":"1-15"},{"day":"16","month":"03","article_processing_charge":"No","language":[{"iso":"eng"}],"date_published":"2019-03-16T00:00:00Z","publication":"arXiv","citation":{"short":"A. Biniaz, K. Jain, A. Lubiw, Z. Masárová, T. Miltzow, D. Mondal, A.M. Naredla, J. Tkadlec, A. Turcotte, ArXiv (n.d.).","mla":"Biniaz, Ahmad, et al. “Token Swapping on Trees.” ArXiv, 1903.06981.","chicago":"Biniaz, Ahmad, Kshitij Jain, Anna Lubiw, Zuzana Masárová, Tillmann Miltzow, Debajyoti Mondal, Anurag Murty Naredla, Josef Tkadlec, and Alexi Turcotte. “Token Swapping on Trees.” ArXiv, n.d.","ama":"Biniaz A, Jain K, Lubiw A, et al. Token swapping on trees. arXiv.","ieee":"A. Biniaz et al., “Token swapping on trees,” arXiv. .","apa":"Biniaz, A., Jain, K., Lubiw, A., Masárová, Z., Miltzow, T., Mondal, D., … Turcotte, A. (n.d.). Token swapping on trees. arXiv.","ista":"Biniaz A, Jain K, Lubiw A, Masárová Z, Miltzow T, Mondal D, Naredla AM, Tkadlec J, Turcotte A. Token swapping on trees. arXiv, 1903.06981."},"external_id":{"arxiv":["1903.06981"]},"main_file_link":[{"url":"https://arxiv.org/abs/1903.06981","open_access":"1"}],"oa":1,"abstract":[{"lang":"eng","text":"The input to the token swapping problem is a graph with vertices v1, v2, . . . , vn, and n tokens with labels 1,2, . . . , n, one on each vertex. The goal is to get token i to vertex vi for all i= 1, . . . , n using a minimum number of swaps, where a swap exchanges the tokens on the endpoints of an edge.Token swapping on a tree, also known as “sorting with a transposition tree,” is not known to be in P nor NP-complete. We present some partial results:\r\n1. An optimum swap sequence may need to perform a swap on a leaf vertex that has the correct token (a “happy leaf”), disproving a conjecture of Vaughan.\r\n2. Any algorithm that fixes happy leaves—as all known approximation algorithms for the problem do—has approximation factor at least 4/3. Furthermore, the two best-known 2-approximation algorithms have approximation factor exactly 2.\r\n3. A generalized problem—weighted coloured token swapping—is NP-complete on trees, but solvable in polynomial time on paths and stars. In this version, tokens and vertices have colours, and colours have weights. The goal is to get every token to a vertex of the same colour, and the cost of a swap is the sum of the weights of the two tokens involved."}],"article_number":"1903.06981","type":"preprint","date_created":"2020-06-08T12:25:25Z","date_updated":"2024-01-04T12:42:08Z","oa_version":"Preprint","author":[{"last_name":"Biniaz","first_name":"Ahmad","full_name":"Biniaz, Ahmad"},{"first_name":"Kshitij","last_name":"Jain","full_name":"Jain, Kshitij"},{"full_name":"Lubiw, Anna","first_name":"Anna","last_name":"Lubiw"},{"full_name":"Masárová, Zuzana","last_name":"Masárová","first_name":"Zuzana","orcid":"0000-0002-6660-1322","id":"45CFE238-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Miltzow","first_name":"Tillmann","full_name":"Miltzow, Tillmann"},{"full_name":"Mondal, Debajyoti","first_name":"Debajyoti","last_name":"Mondal"},{"first_name":"Anurag Murty","last_name":"Naredla","full_name":"Naredla, Anurag Murty"},{"last_name":"Tkadlec","first_name":"Josef","orcid":"0000-0002-1097-9684","id":"3F24CCC8-F248-11E8-B48F-1D18A9856A87","full_name":"Tkadlec, Josef"},{"full_name":"Turcotte, Alexi","first_name":"Alexi","last_name":"Turcotte"}],"related_material":{"record":[{"relation":"dissertation_contains","status":"public","id":"7944"},{"status":"public","relation":"later_version","id":"12833"}]},"status":"public","title":"Token swapping on trees","publication_status":"submitted","department":[{"_id":"HeEd"},{"_id":"UlWa"},{"_id":"KrCh"}],"year":"2019","_id":"7950","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87"},{"publist_id":"7733","file_date_updated":"2020-07-14T12:45:20Z","acknowledgement":"This research is partially supported by the Office of Naval Research, through grant no. N62909-18-1-2038, and the DFG Collaborative Research Center TRR 109, ‘Discretization in Geometry and Dynamics’, through grant no. I02979-N35 of the Austrian Science Fund","year":"2018","department":[{"_id":"HeEd"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","publication_status":"published","author":[{"last_name":"Edelsbrunner","first_name":"Herbert","orcid":"0000-0002-9823-6833","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","full_name":"Edelsbrunner, Herbert"},{"full_name":"Virk, Ziga","last_name":"Virk","first_name":"Ziga"},{"last_name":"Wagner","first_name":"Hubert","id":"379CA8B8-F248-11E8-B48F-1D18A9856A87","full_name":"Wagner, Hubert"}],"volume":99,"date_created":"2018-12-11T11:45:05Z","date_updated":"2021-01-12T06:53:48Z","month":"06","oa":1,"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"project":[{"name":"Persistence and stability of geometric complexes","call_identifier":"FWF","grant_number":"I02979-N35","_id":"2561EBF4-B435-11E9-9278-68D0E5697425"}],"quality_controlled":"1","doi":"10.4230/LIPIcs.SoCG.2018.35","conference":{"location":"Budapest, Hungary","start_date":"2018-06-11","end_date":"2018-06-14","name":"SoCG: Symposium on Computational Geometry"},"language":[{"iso":"eng"}],"type":"conference","alternative_title":["Leibniz International Proceedings in Information, LIPIcs"],"abstract":[{"lang":"eng","text":"Smallest enclosing spheres of finite point sets are central to methods in topological data analysis. Focusing on Bregman divergences to measure dissimilarity, we prove bounds on the location of the center of a smallest enclosing sphere. These bounds depend on the range of radii for which Bregman balls are convex."}],"_id":"188","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","intvolume":" 99","status":"public","ddc":["000"],"title":"Smallest enclosing spheres and Chernoff points in Bregman geometry","oa_version":"Published Version","file":[{"relation":"main_file","file_id":"5724","checksum":"7509403803b3ac1aee94bbc2ad293d21","date_created":"2018-12-17T16:31:31Z","date_updated":"2020-07-14T12:45:20Z","access_level":"open_access","file_name":"2018_LIPIcs_Edelsbrunner.pdf","content_type":"application/pdf","file_size":489080,"creator":"dernst"}],"scopus_import":1,"has_accepted_license":"1","day":"11","citation":{"mla":"Edelsbrunner, Herbert, et al. Smallest Enclosing Spheres and Chernoff Points in Bregman Geometry. Vol. 99, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018, p. 35:1-35:13, doi:10.4230/LIPIcs.SoCG.2018.35.","short":"H. Edelsbrunner, Z. Virk, H. Wagner, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018, p. 35:1-35:13.","chicago":"Edelsbrunner, Herbert, Ziga Virk, and Hubert Wagner. “Smallest Enclosing Spheres and Chernoff Points in Bregman Geometry,” 99:35:1-35:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. https://doi.org/10.4230/LIPIcs.SoCG.2018.35.","ama":"Edelsbrunner H, Virk Z, Wagner H. Smallest enclosing spheres and Chernoff points in Bregman geometry. In: Vol 99. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2018:35:1-35:13. doi:10.4230/LIPIcs.SoCG.2018.35","ista":"Edelsbrunner H, Virk Z, Wagner H. 2018. Smallest enclosing spheres and Chernoff points in Bregman geometry. SoCG: Symposium on Computational Geometry, Leibniz International Proceedings in Information, LIPIcs, vol. 99, 35:1-35:13.","ieee":"H. Edelsbrunner, Z. Virk, and H. Wagner, “Smallest enclosing spheres and Chernoff points in Bregman geometry,” presented at the SoCG: Symposium on Computational Geometry, Budapest, Hungary, 2018, vol. 99, p. 35:1-35:13.","apa":"Edelsbrunner, H., Virk, Z., & Wagner, H. (2018). Smallest enclosing spheres and Chernoff points in Bregman geometry (Vol. 99, p. 35:1-35:13). Presented at the SoCG: Symposium on Computational Geometry, Budapest, Hungary: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2018.35"},"page":"35:1 - 35:13","date_published":"2018-06-11T00:00:00Z"},{"month":"06","publication_identifier":{"issn":["2663-337X"]},"oa":1,"supervisor":[{"full_name":"Edelsbrunner, Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9823-6833","first_name":"Herbert","last_name":"Edelsbrunner"}],"degree_awarded":"PhD","language":[{"iso":"eng"}],"doi":"10.15479/AT:ISTA:th_1026","file_date_updated":"2020-07-14T12:45:24Z","publist_id":"7712","publication_status":"published","publisher":"Institute of Science and Technology Austria","department":[{"_id":"HeEd"}],"year":"2018","date_created":"2018-12-11T11:45:10Z","date_updated":"2023-09-07T12:25:32Z","author":[{"full_name":"Iglesias Ham, Mabel","last_name":"Iglesias Ham","first_name":"Mabel","id":"41B58C0C-F248-11E8-B48F-1D18A9856A87"}],"day":"11","article_processing_charge":"No","has_accepted_license":"1","page":"171","citation":{"short":"M. Iglesias Ham, Multiple Covers with Balls, Institute of Science and Technology Austria, 2018.","mla":"Iglesias Ham, Mabel. Multiple Covers with Balls. Institute of Science and Technology Austria, 2018, doi:10.15479/AT:ISTA:th_1026.","chicago":"Iglesias Ham, Mabel. “Multiple Covers with Balls.” Institute of Science and Technology Austria, 2018. https://doi.org/10.15479/AT:ISTA:th_1026.","ama":"Iglesias Ham M. Multiple covers with balls. 2018. doi:10.15479/AT:ISTA:th_1026","apa":"Iglesias Ham, M. (2018). Multiple covers with balls. Institute of Science and Technology Austria. https://doi.org/10.15479/AT:ISTA:th_1026","ieee":"M. Iglesias Ham, “Multiple covers with balls,” Institute of Science and Technology Austria, 2018.","ista":"Iglesias Ham M. 2018. Multiple covers with balls. Institute of Science and Technology Austria."},"date_published":"2018-06-11T00:00:00Z","alternative_title":["ISTA Thesis"],"type":"dissertation","abstract":[{"text":"We describe arrangements of three-dimensional spheres from a geometrical and topological point of view. Real data (fitting this setup) often consist of soft spheres which show certain degree of deformation while strongly packing against each other. In this context, we answer the following questions: If we model a soft packing of spheres by hard spheres that are allowed to overlap, can we measure the volume in the overlapped areas? Can we be more specific about the overlap volume, i.e. quantify how much volume is there covered exactly twice, three times, or k times? What would be a good optimization criteria that rule the arrangement of soft spheres while making a good use of the available space? Fixing a particular criterion, what would be the optimal sphere configuration? The first result of this thesis are short formulas for the computation of volumes covered by at least k of the balls. The formulas exploit information contained in the order-k Voronoi diagrams and its closely related Level-k complex. The used complexes lead to a natural generalization into poset diagrams, a theoretical formalism that contains the order-k and degree-k diagrams as special cases. In parallel, we define different criteria to determine what could be considered an optimal arrangement from a geometrical point of view. Fixing a criterion, we find optimal soft packing configurations in 2D and 3D where the ball centers lie on a lattice. As a last step, we use tools from computational topology on real physical data, to show the potentials of higher-order diagrams in the description of melting crystals. The results of the experiments leaves us with an open window to apply the theories developed in this thesis in real applications.","lang":"eng"}],"title":"Multiple covers with balls","ddc":["514","516"],"status":"public","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","_id":"201","oa_version":"Published Version","file":[{"file_id":"5918","relation":"source_file","date_updated":"2020-07-14T12:45:24Z","date_created":"2019-02-05T07:43:31Z","checksum":"dd699303623e96d1478a6ae07210dd05","file_name":"IST-2018-1025-v2+5_ist-thesis-iglesias-11June2018(1).zip","access_level":"closed","creator":"kschuh","file_size":11827713,"content_type":"application/zip"},{"creator":"kschuh","content_type":"application/pdf","file_size":4783846,"file_name":"IST-2018-1025-v2+4_ThesisIglesiasFinal11June2018.pdf","access_level":"open_access","date_updated":"2020-07-14T12:45:24Z","date_created":"2019-02-05T07:43:45Z","checksum":"ba163849a190d2b41d66fef0e4983294","file_id":"5919","relation":"main_file"}],"pubrep_id":"1026"},{"scopus_import":1,"has_accepted_license":"1","day":"11","citation":{"mla":"Edelsbrunner, Herbert, and Georg F. Osang. The Multi-Cover Persistence of Euclidean Balls. Vol. 99, 34, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018, doi:10.4230/LIPIcs.SoCG.2018.34.","short":"H. Edelsbrunner, G.F. Osang, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018.","chicago":"Edelsbrunner, Herbert, and Georg F Osang. “The Multi-Cover Persistence of Euclidean Balls,” Vol. 99. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. https://doi.org/10.4230/LIPIcs.SoCG.2018.34.","ama":"Edelsbrunner H, Osang GF. The multi-cover persistence of Euclidean balls. In: Vol 99. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2018. doi:10.4230/LIPIcs.SoCG.2018.34","ista":"Edelsbrunner H, Osang GF. 2018. The multi-cover persistence of Euclidean balls. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 99, 34.","apa":"Edelsbrunner, H., & Osang, G. F. (2018). The multi-cover persistence of Euclidean balls (Vol. 99). Presented at the SoCG: Symposium on Computational Geometry, Budapest, Hungary: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2018.34","ieee":"H. Edelsbrunner and G. F. Osang, “The multi-cover persistence of Euclidean balls,” presented at the SoCG: Symposium on Computational Geometry, Budapest, Hungary, 2018, vol. 99."},"date_published":"2018-06-11T00:00:00Z","alternative_title":["LIPIcs"],"type":"conference","abstract":[{"lang":"eng","text":"Given a locally finite X ⊆ ℝd and a radius r ≥ 0, the k-fold cover of X and r consists of all points in ℝd that have k or more points of X within distance r. We consider two filtrations - one in scale obtained by fixing k and increasing r, and the other in depth obtained by fixing r and decreasing k - and we compute the persistence diagrams of both. While standard methods suffice for the filtration in scale, we need novel geometric and topological concepts for the filtration in depth. In particular, we introduce a rhomboid tiling in ℝd+1 whose horizontal integer slices are the order-k Delaunay mosaics of X, and construct a zigzag module from Delaunay mosaics that is isomorphic to the persistence module of the multi-covers. "}],"intvolume":" 99","status":"public","ddc":["516"],"title":"The multi-cover persistence of Euclidean balls","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"187","file":[{"access_level":"open_access","file_name":"2018_LIPIcs_Edelsbrunner_Osang.pdf","file_size":528018,"content_type":"application/pdf","creator":"dernst","relation":"main_file","file_id":"5738","checksum":"d8c0533ad0018eb4ed1077475eb8fc18","date_created":"2018-12-18T09:27:22Z","date_updated":"2020-07-14T12:45:19Z"}],"oa_version":"Published Version","month":"06","project":[{"name":"Persistence and stability of geometric complexes","call_identifier":"FWF","_id":"2561EBF4-B435-11E9-9278-68D0E5697425","grant_number":"I02979-N35"}],"quality_controlled":"1","oa":1,"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"language":[{"iso":"eng"}],"doi":"10.4230/LIPIcs.SoCG.2018.34","conference":{"location":"Budapest, Hungary","start_date":"2018-06-11","end_date":"2018-06-14","name":"SoCG: Symposium on Computational Geometry"},"article_number":"34","publist_id":"7732","file_date_updated":"2020-07-14T12:45:19Z","department":[{"_id":"HeEd"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","publication_status":"published","acknowledgement":"This work is 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).","year":"2018","volume":99,"date_created":"2018-12-11T11:45:05Z","date_updated":"2023-09-07T13:29:00Z","related_material":{"record":[{"id":"9317","relation":"later_version","status":"public"},{"relation":"dissertation_contains","status":"public","id":"9056"}]},"author":[{"orcid":"0000-0002-9823-6833","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","last_name":"Edelsbrunner","first_name":"Herbert","full_name":"Edelsbrunner, Herbert"},{"full_name":"Osang, Georg F","last_name":"Osang","first_name":"Georg F","orcid":"0000-0002-8882-5116","id":"464B40D6-F248-11E8-B48F-1D18A9856A87"}]},{"month":"06","doi":"10.1007/s10711-017-0265-6","language":[{"iso":"eng"}],"oa":1,"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"external_id":{"isi":["000431418800004"]},"project":[{"_id":"25681D80-B435-11E9-9278-68D0E5697425","grant_number":"291734","call_identifier":"FP7","name":"International IST Postdoc Fellowship Programme"}],"isi":1,"quality_controlled":"1","publist_id":"7014","ec_funded":1,"file_date_updated":"2020-07-14T12:47:44Z","author":[{"first_name":"Arseniy","last_name":"Akopyan","id":"430D2C90-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-2548-617X","full_name":"Akopyan, Arseniy"}],"volume":194,"date_created":"2018-12-11T11:47:57Z","date_updated":"2023-09-08T11:40:29Z","year":"2018","publisher":"Springer","department":[{"_id":"HeEd"}],"publication_status":"published","has_accepted_license":"1","article_processing_charge":"Yes (via OA deal)","day":"01","scopus_import":"1","date_published":"2018-06-01T00:00:00Z","citation":{"short":"A. Akopyan, Geometriae Dedicata 194 (2018) 55–64.","mla":"Akopyan, Arseniy. “3-Webs Generated by Confocal Conics and Circles.” Geometriae Dedicata, vol. 194, no. 1, Springer, 2018, pp. 55–64, doi:10.1007/s10711-017-0265-6.","chicago":"Akopyan, Arseniy. “3-Webs Generated by Confocal Conics and Circles.” Geometriae Dedicata. Springer, 2018. https://doi.org/10.1007/s10711-017-0265-6.","ama":"Akopyan A. 3-Webs generated by confocal conics and circles. Geometriae Dedicata. 2018;194(1):55-64. doi:10.1007/s10711-017-0265-6","ieee":"A. Akopyan, “3-Webs generated by confocal conics and circles,” Geometriae Dedicata, vol. 194, no. 1. Springer, pp. 55–64, 2018.","apa":"Akopyan, A. (2018). 3-Webs generated by confocal conics and circles. Geometriae Dedicata. Springer. https://doi.org/10.1007/s10711-017-0265-6","ista":"Akopyan A. 2018. 3-Webs generated by confocal conics and circles. Geometriae Dedicata. 194(1), 55–64."},"publication":"Geometriae Dedicata","page":"55 - 64","article_type":"original","issue":"1","abstract":[{"text":"We consider families of confocal conics and two pencils of Apollonian circles having the same foci. We will show that these families of curves generate trivial 3-webs and find the exact formulas describing them.","lang":"eng"}],"type":"journal_article","file":[{"file_id":"7222","relation":"main_file","date_created":"2020-01-03T11:35:08Z","date_updated":"2020-07-14T12:47:44Z","checksum":"1febcfc1266486053a069e3425ea3713","file_name":"2018_Springer_Akopyan.pdf","access_level":"open_access","creator":"kschuh","file_size":1140860,"content_type":"application/pdf"}],"oa_version":"Published Version","_id":"692","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","intvolume":" 194","ddc":["510"],"title":"3-Webs generated by confocal conics and circles","status":"public"},{"scopus_import":"1","article_processing_charge":"No","day":"06","citation":{"ama":"Akopyan A, Segal Halevi E. Counting blanks in polygonal arrangements. SIAM Journal on Discrete Mathematics. 2018;32(3):2242-2257. doi:10.1137/16M110407X","apa":"Akopyan, A., & Segal Halevi, E. (2018). Counting blanks in polygonal arrangements. SIAM Journal on Discrete Mathematics. Society for Industrial and Applied Mathematics . https://doi.org/10.1137/16M110407X","ieee":"A. Akopyan and E. Segal Halevi, “Counting blanks in polygonal arrangements,” SIAM Journal on Discrete Mathematics, vol. 32, no. 3. Society for Industrial and Applied Mathematics , pp. 2242–2257, 2018.","ista":"Akopyan A, Segal Halevi E. 2018. Counting blanks in polygonal arrangements. SIAM Journal on Discrete Mathematics. 32(3), 2242–2257.","short":"A. Akopyan, E. Segal Halevi, SIAM Journal on Discrete Mathematics 32 (2018) 2242–2257.","mla":"Akopyan, Arseniy, and Erel Segal Halevi. “Counting Blanks in Polygonal Arrangements.” SIAM Journal on Discrete Mathematics, vol. 32, no. 3, Society for Industrial and Applied Mathematics , 2018, pp. 2242–57, doi:10.1137/16M110407X.","chicago":"Akopyan, Arseniy, and Erel Segal Halevi. “Counting Blanks in Polygonal Arrangements.” SIAM Journal on Discrete Mathematics. Society for Industrial and Applied Mathematics , 2018. https://doi.org/10.1137/16M110407X."},"publication":"SIAM Journal on Discrete Mathematics","page":"2242 - 2257","date_published":"2018-09-06T00:00:00Z","type":"journal_article","issue":"3","abstract":[{"lang":"eng","text":"Inside a two-dimensional region (``cake""), there are m nonoverlapping tiles of a certain kind (``toppings""). We want to expand the toppings while keeping them nonoverlapping, and possibly add some blank pieces of the same ``certain kind,"" such that the entire cake is covered. How many blanks must we add? We study this question in several cases: (1) The cake and toppings are general polygons. (2) The cake and toppings are convex figures. (3) The cake and toppings are axis-parallel rectangles. (4) The cake is an axis-parallel rectilinear polygon and the toppings are axis-parallel rectangles. In all four cases, we provide tight bounds on the number of blanks."}],"_id":"58","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","intvolume":" 32","title":"Counting blanks in polygonal arrangements","status":"public","oa_version":"Preprint","month":"09","oa":1,"main_file_link":[{"url":"https://arxiv.org/abs/1604.00960","open_access":"1"}],"external_id":{"isi":["000450810500036"],"arxiv":["1604.00960"]},"project":[{"call_identifier":"FP7","name":"International IST Postdoc Fellowship Programme","_id":"25681D80-B435-11E9-9278-68D0E5697425","grant_number":"291734"}],"isi":1,"quality_controlled":"1","doi":"10.1137/16M110407X","language":[{"iso":"eng"}],"publist_id":"7996","ec_funded":1,"year":"2018","department":[{"_id":"HeEd"}],"publisher":"Society for Industrial and Applied Mathematics ","publication_status":"published","author":[{"full_name":"Akopyan, Arseniy","orcid":"0000-0002-2548-617X","id":"430D2C90-F248-11E8-B48F-1D18A9856A87","last_name":"Akopyan","first_name":"Arseniy"},{"full_name":"Segal Halevi, Erel","first_name":"Erel","last_name":"Segal Halevi"}],"volume":32,"date_updated":"2023-09-11T12:48:39Z","date_created":"2018-12-11T11:44:24Z"},{"month":"04","language":[{"iso":"eng"}],"doi":"10.1090/tran/7292","project":[{"name":"International IST Postdoc Fellowship Programme","call_identifier":"FP7","_id":"25681D80-B435-11E9-9278-68D0E5697425","grant_number":"291734"}],"isi":1,"quality_controlled":"1","oa":1,"external_id":{"isi":["000423197800019"]},"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1602.04637"}],"ec_funded":1,"publist_id":"7363","volume":370,"date_updated":"2023-09-11T14:19:12Z","date_created":"2018-12-11T11:46:35Z","author":[{"full_name":"Akopyan, Arseniy","id":"430D2C90-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-2548-617X","first_name":"Arseniy","last_name":"Akopyan"},{"full_name":"Bobenko, Alexander","first_name":"Alexander","last_name":"Bobenko"}],"department":[{"_id":"HeEd"}],"publisher":"American Mathematical Society","publication_status":"published","acknowledgement":"DFG Collaborative Research Center TRR 109 “Discretization in Geometry and Dynamics”; People Programme (Marie Curie Actions) of the European Union’s Seventh Framework Programme (FP7/2007-2013) REA grant agreement n◦[291734]","year":"2018","article_processing_charge":"No","day":"01","scopus_import":"1","date_published":"2018-04-01T00:00:00Z","page":"2825 - 2854","citation":{"ama":"Akopyan A, Bobenko A. Incircular nets and confocal conics. Transactions of the American Mathematical Society. 2018;370(4):2825-2854. doi:10.1090/tran/7292","ista":"Akopyan A, Bobenko A. 2018. Incircular nets and confocal conics. Transactions of the American Mathematical Society. 370(4), 2825–2854.","ieee":"A. Akopyan and A. Bobenko, “Incircular nets and confocal conics,” Transactions of the American Mathematical Society, vol. 370, no. 4. American Mathematical Society, pp. 2825–2854, 2018.","apa":"Akopyan, A., & Bobenko, A. (2018). Incircular nets and confocal conics. Transactions of the American Mathematical Society. American Mathematical Society. https://doi.org/10.1090/tran/7292","mla":"Akopyan, Arseniy, and Alexander Bobenko. “Incircular Nets and Confocal Conics.” Transactions of the American Mathematical Society, vol. 370, no. 4, American Mathematical Society, 2018, pp. 2825–54, doi:10.1090/tran/7292.","short":"A. Akopyan, A. Bobenko, Transactions of the American Mathematical Society 370 (2018) 2825–2854.","chicago":"Akopyan, Arseniy, and Alexander Bobenko. “Incircular Nets and Confocal Conics.” Transactions of the American Mathematical Society. American Mathematical Society, 2018. https://doi.org/10.1090/tran/7292."},"publication":"Transactions of the American Mathematical Society","issue":"4","abstract":[{"text":"We consider congruences of straight lines in a plane with the combinatorics of the square grid, with all elementary quadrilaterals possessing an incircle. It is shown that all the vertices of such nets (we call them incircular or IC-nets) lie on confocal conics. Our main new results are on checkerboard IC-nets in the plane. These are congruences of straight lines in the plane with the combinatorics of the square grid, combinatorially colored as a checkerboard, such that all black coordinate quadrilaterals possess inscribed circles. We show how this larger class of IC-nets appears quite naturally in Laguerre geometry of oriented planes and spheres and leads to new remarkable incidence theorems. Most of our results are valid in hyperbolic and spherical geometries as well. We present also generalizations in spaces of higher dimension, called checkerboard IS-nets. The construction of these nets is based on a new 9 inspheres incidence theorem.","lang":"eng"}],"type":"journal_article","oa_version":"Preprint","intvolume":" 370","status":"public","title":"Incircular nets and confocal conics","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","_id":"458"}]