@article{12086, abstract = {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.}, author = {Edelsbrunner, Herbert and Osang, Georg F}, issn = {1432-0541}, journal = {Algorithmica}, pages = {277--295}, publisher = {Springer Nature}, title = {{A simple algorithm for higher-order Delaunay mosaics and alpha shapes}}, doi = {10.1007/s00453-022-01027-6}, volume = {85}, year = {2023}, } @article{12709, abstract = {Given a finite set A ⊂ ℝ^d, let Cov_{r,k} denote the set of all points within distance r to at least k points of A. Allowing r and k to vary, we obtain a 2-parameter family of spaces that grow larger when r increases or k decreases, called the multicover bifiltration. Motivated by the problem of computing the homology of this bifiltration, we introduce two closely related combinatorial bifiltrations, one polyhedral and the other simplicial, which are both topologically equivalent to the multicover bifiltration and far smaller than a Čech-based model considered in prior work of Sheehy. Our polyhedral construction is a bifiltration of the rhomboid tiling of Edelsbrunner and Osang, and can be efficiently computed using a variant of an algorithm given by these authors as well. Using an implementation for dimension 2 and 3, we provide experimental results. Our simplicial construction is useful for understanding the polyhedral construction and proving its correctness.}, author = {Corbet, René and Kerber, Michael and Lesnick, Michael and Osang, Georg F}, issn = {1432-0444}, journal = {Discrete and Computational Geometry}, pages = {376--405}, publisher = {Springer Nature}, title = {{Computing the multicover bifiltration}}, doi = {10.1007/s00454-022-00476-8}, volume = {70}, year = {2023}, } @phdthesis{9056, abstract = {In this thesis we study persistence of multi-covers of Euclidean balls and the geometric structures underlying their computation, in particular Delaunay mosaics and Voronoi tessellations. The k-fold cover for some discrete input point set consists of the space where at least k balls of radius r around the input points overlap. Persistence is a notion that captures, in some sense, the topology of the shape underlying the input. While persistence is usually computed for the union of balls, the k-fold cover is of interest as it captures local density, and thus might approximate the shape of the input better if the input data is noisy. To compute persistence of these k-fold covers, we need a discretization that is provided by higher-order Delaunay mosaics. We present and implement a simple and efficient algorithm for the computation of higher-order Delaunay mosaics, and use it to give experimental results for their combinatorial properties. The algorithm makes use of a new geometric structure, the rhomboid tiling. It contains the higher-order Delaunay mosaics as slices, and by introducing a filtration function on the tiling, we also obtain higher-order α-shapes as slices. These allow us to compute persistence of the multi-covers for varying radius r; the computation for varying k is less straight-foward and involves the rhomboid tiling directly. We apply our algorithms to experimental sphere packings to shed light on their structural properties. Finally, inspired by periodic structures in packings and materials, we propose and implement an algorithm for periodic Delaunay triangulations to be integrated into the Computational Geometry Algorithms Library (CGAL), and discuss the implications on persistence for periodic data sets.}, author = {Osang, Georg F}, issn = {2663-337X}, pages = {134}, publisher = {Institute of Science and Technology Austria}, title = {{Multi-cover persistence and Delaunay mosaics}}, doi = {10.15479/AT:ISTA:9056}, year = {2021}, } @article{9317, abstract = {Given a locally finite X⊆Rd and a radius r≥0, the k-fold cover of X and r consists of all points in Rd 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 Rd+1 whose horizontal integer slices are the order-k Delaunay mosaics of X, and construct a zigzag module of Delaunay mosaics that is isomorphic to the persistence module of the multi-covers.}, author = {Edelsbrunner, Herbert and Osang, Georg F}, issn = {1432-0444}, journal = {Discrete and Computational Geometry}, pages = {1296–1313}, publisher = {Springer Nature}, title = {{The multi-cover persistence of Euclidean balls}}, doi = {10.1007/s00454-021-00281-9}, volume = {65}, year = {2021}, } @article{9465, abstract = {Given a locally finite set 𝑋⊆ℝ𝑑 and an integer 𝑘≥0, we consider the function 𝐰𝑘:Del𝑘(𝑋)→ℝ on the dual of the order-k Voronoi tessellation, whose sublevel sets generalize the notion of alpha shapes from order-1 to order-k (Edelsbrunner et al. in IEEE Trans Inf Theory IT-29:551–559, 1983; Krasnoshchekov and Polishchuk in Inf Process Lett 114:76–83, 2014). While this function is not necessarily generalized discrete Morse, in the sense of Forman (Adv Math 134:90–145, 1998) and Freij (Discrete Math 309:3821–3829, 2009), we prove that it satisfies similar properties so that its increments can be meaningfully classified into critical and non-critical steps. This result extends to the case of weighted points and sheds light on k-fold covers with balls in Euclidean space.}, author = {Edelsbrunner, Herbert and Nikitenko, Anton and Osang, Georg F}, issn = {14208997}, journal = {Journal of Geometry}, number = {1}, publisher = {Springer Nature}, title = {{A step in the Delaunay mosaic of order k}}, doi = {10.1007/s00022-021-00577-4}, volume = {112}, year = {2021}, } @inproceedings{9605, abstract = {Given a finite set A ⊂ ℝ^d, let Cov_{r,k} denote the set of all points within distance r to at least k points of A. Allowing r and k to vary, we obtain a 2-parameter family of spaces that grow larger when r increases or k decreases, called the multicover bifiltration. Motivated by the problem of computing the homology of this bifiltration, we introduce two closely related combinatorial bifiltrations, one polyhedral and the other simplicial, which are both topologically equivalent to the multicover bifiltration and far smaller than a Čech-based model considered in prior work of Sheehy. Our polyhedral construction is a bifiltration of the rhomboid tiling of Edelsbrunner and Osang, and can be efficiently computed using a variant of an algorithm given by these authors as well. Using an implementation for dimension 2 and 3, we provide experimental results. Our simplicial construction is useful for understanding the polyhedral construction and proving its correctness. }, author = {Corbet, René and Kerber, Michael and Lesnick, Michael and Osang, Georg F}, booktitle = {Leibniz International Proceedings in Informatics}, isbn = {9783959771849}, issn = {18688969}, location = {Online}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Computing the multicover bifiltration}}, doi = {10.4230/LIPIcs.SoCG.2021.27}, volume = {189}, year = {2021}, } @article{10204, abstract = {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 = {Osang, Georg F and Edelsbrunner, Herbert and Saadatfar, Mohammad}, issn = {1744-6848}, journal = {Soft Matter}, number = {40}, pages = {9107--9115}, publisher = {Royal Society of Chemistry }, title = {{Topological signatures and stability of hexagonal close packing and Barlow stackings}}, doi = {10.1039/d1sm00774b}, volume = {17}, year = {2021}, } @inproceedings{10367, abstract = {How information is created, shared and consumed has changed rapidly in recent decades, in part thanks to new social platforms and technologies on the web. With ever-larger amounts of unstructured and limited labels, organizing and reconciling information from different sources and modalities is a central challenge in machine learning. This cutting-edge tutorial aims to introduce the multimodal entailment task, which can be useful for detecting semantic alignments when a single modality alone does not suffice for a whole content understanding. Starting with a brief overview of natural language processing, computer vision, structured data and neural graph learning, we lay the foundations for the multimodal sections to follow. We then discuss recent multimodal learning literature covering visual, audio and language streams, and explore case studies focusing on tasks which require fine-grained understanding of visual and linguistic semantics question answering, veracity and hatred classification. Finally, we introduce a new dataset for recognizing multimodal entailment, exploring it in a hands-on collaborative section. Overall, this tutorial gives an overview of multimodal learning, introduces a multimodal entailment dataset, and encourages future research in the topic.}, author = {Ilharco, Cesar and Shirazi, Afsaneh and Gopalan, Arjun and Nagrani, Arsha and Bratanič, Blaž and Bregler, Chris and Liu, Christina and Ferreira, Felipe and Barcik, Gabriek and Ilharco, Gabriel and Osang, Georg F and Bulian, Jannis and Frank, Jared and Smaira, Lucas and Cao, Qin and Marino, Ricardo and Patel, Roma and Leung, Thomas and Imbrasaite, Vaiva}, booktitle = {59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing, Tutorial Abstracts}, isbn = {9-781-9540-8557-2}, location = {Bangkok, Thailand}, pages = {29--30}, publisher = {Association for Computational Linguistics}, title = {{Recognizing multimodal entailment}}, doi = {10.18653/v1/2021.acl-tutorials.6}, year = {2021}, } @inproceedings{8703, abstract = {Even though Delaunay originally introduced his famous triangulations in the case of infinite point sets with translational periodicity, a software that computes such triangulations in the general case is not yet available, to the best of our knowledge. Combining and generalizing previous work, we present a practical algorithm for computing such triangulations. The algorithm has been implemented and experiments show that its performance is as good as the one of the CGAL package, which is restricted to cubic periodicity. }, author = {Osang, Georg F and Rouxel-Labbé, Mael and Teillaud, Monique}, booktitle = {28th Annual European Symposium on Algorithms}, isbn = {9783959771627}, issn = {18688969}, location = {Virtual, Online; Pisa, Italy}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Generalizing CGAL periodic Delaunay triangulations}}, doi = {10.4230/LIPIcs.ESA.2020.75}, volume = {173}, year = {2020}, } @inproceedings{7216, abstract = {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.}, author = {Osang, Georg F and Cook, James and Fabrikant, Alex and Gruteser, Marco}, booktitle = {2019 IEEE Intelligent Transportation Systems Conference}, isbn = {9781538670248}, location = {Auckland, New Zealand}, publisher = {IEEE}, title = {{LiveTraVeL: Real-time matching of transit vehicle trajectories to transit routes at scale}}, doi = {10.1109/ITSC.2019.8917514}, year = {2019}, } @inproceedings{187, abstract = {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. }, author = {Edelsbrunner, Herbert and Osang, Georg F}, location = {Budapest, Hungary}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{The multi-cover persistence of Euclidean balls}}, doi = {10.4230/LIPIcs.SoCG.2018.34}, volume = {99}, year = {2018}, } @inproceedings{193, abstract = {We show attacks on five data-independent memory-hard functions (iMHF) that were submitted to the password hashing competition (PHC). Informally, an MHF is a function which cannot be evaluated on dedicated hardware, like ASICs, at significantly lower hardware and/or energy cost than evaluating a single instance on a standard single-core architecture. Data-independent means the memory access pattern of the function is independent of the input; this makes iMHFs harder to construct than data-dependent ones, but the latter can be attacked by various side-channel attacks. Following [Alwen-Blocki'16], we capture the evaluation of an iMHF as a directed acyclic graph (DAG). The cumulative parallel pebbling complexity of this DAG is a measure for the hardware cost of evaluating the iMHF on an ASIC. Ideally, one would like the complexity of a DAG underlying an iMHF to be as close to quadratic in the number of nodes of the graph as possible. Instead, we show that (the DAGs underlying) the following iMHFs are far from this bound: Rig.v2, TwoCats and Gambit each having an exponent no more than 1.75. Moreover, we show that the complexity of the iMHF modes of the PHC finalists Pomelo and Lyra2 have exponents at most 1.83 and 1.67 respectively. To show this we investigate a combinatorial property of each underlying DAG (called its depth-robustness. By establishing upper bounds on this property we are then able to apply the general technique of [Alwen-Block'16] for analyzing the hardware costs of an iMHF.}, author = {Alwen, Joel F and Gazi, Peter and Kamath Hosdurg, Chethan and Klein, Karen and Osang, Georg F and Pietrzak, Krzysztof Z and Reyzin, Lenoid and Rolinek, Michal and Rybar, Michal}, booktitle = {Proceedings of the 2018 on Asia Conference on Computer and Communication Security}, location = {Incheon, Republic of Korea}, pages = {51 -- 65}, publisher = {ACM}, title = {{On the memory hardness of data independent password hashing functions}}, doi = {10.1145/3196494.3196534}, year = {2018}, } @article{1065, abstract = {We consider the problem of reachability in pushdown graphs. We study the problem for pushdown graphs with constant treewidth. Even for pushdown graphs with treewidth 1, for the reachability problem we establish the following: (i) the problem is PTIME-complete, and (ii) any subcubic algorithm for the problem would contradict the k-clique conjecture and imply faster combinatorial algorithms for cliques in graphs.}, author = {Chatterjee, Krishnendu and Osang, Georg F}, issn = {00200190}, journal = {Information Processing Letters}, pages = {25 -- 29}, publisher = {Elsevier}, title = {{Pushdown reachability with constant treewidth}}, doi = {10.1016/j.ipl.2017.02.003}, volume = {122}, year = {2017}, }