TY - CONF AB - A face in a curve arrangement is called popular if it is bounded by the same curve multiple times. Motivated by the automatic generation of curved nonogram puzzles, we investigate possibilities to eliminate the popular faces in an arrangement by inserting a single additional curve. This turns out to be NP-hard; however, it becomes tractable when the number of popular faces is small: We present a probabilistic FPT-approach in the number of popular faces. AU - De Nooijer, Phoebe AU - Terziadis, Soeren AU - Weinberger, Alexandra AU - Masárová, Zuzana AU - Mchedlidze, Tamara AU - Löffler, Maarten AU - Rote, Günter ID - 14888 SN - 0302-9743 T2 - 31st International Symposium on Graph Drawing and Network Visualization TI - Removing popular faces in curve arrangements VL - 14466 ER - TY - CONF AB - 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. AU - Pach, János AU - Saghafian, Morteza AU - Schnider, Patrick ID - 15012 SN - 03029743 T2 - 31st International Symposium on Graph Drawing and Network Visualization TI - Decomposition of geometric graphs into star-forests VL - 14465 ER - TY - THES AB - Point sets, geometric networks, and arrangements of hyperplanes are fundamental objects in discrete geometry that have captivated mathematicians for centuries, if not millennia. This thesis seeks to cast new light on these structures by illustrating specific instances where a topological perspective, specifically through discrete Morse theory and persistent homology, provides valuable insights. At first glance, the topology of these geometric objects might seem uneventful: point sets essentially lack of topology, arrangements of hyperplanes are a decomposition of Rd, which is a contractible space, and the topology of a network primarily involves the enumeration of connected components and cycles within the network. However, beneath this apparent simplicity, there lies an array of intriguing structures, a small subset of which will be uncovered in this thesis. Focused on three case studies, each addressing one of the mentioned objects, this work will showcase connections that intertwine topology with diverse fields such as combinatorial geometry, algorithms and data structures, and emerging applications like spatial biology. AU - Cultrera di Montesano, Sebastiano ID - 15094 SN - 2663 - 337X TI - Persistence and Morse theory for discrete geometric structures ER - TY - CONF AB - We present a dynamic data structure for maintaining the persistent homology of a time series of real numbers. The data structure supports local operations, including the insertion and deletion of an item and the cutting and concatenating of lists, each in time O(log n + k), in which n counts the critical items and k the changes in the augmented persistence diagram. To achieve this, we design a tailor-made tree structure with an unconventional representation, referred to as banana tree, which may be useful in its own right. AU - Cultrera di Montesano, Sebastiano AU - Edelsbrunner, Herbert AU - Henzinger, Monika H AU - Ost, Lara ED - Woodruff, David P. ID - 15093 T2 - Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) TI - Dynamically maintaining the persistent homology of time series ER - TY - GEN AB - Motivated by applications in the medical sciences, we study finite chromatic sets in Euclidean space from a topological perspective. Based on the persistent homology for images, kernels and cokernels, we design provably stable homological quantifiers that describe the geometric micro- and macro-structure of how the color classes mingle. These can be efficiently computed using chromatic variants of Delaunay and alpha complexes, and code that does these computations is provided. AU - Cultrera di Montesano, Sebastiano AU - Draganov, Ondrej AU - Edelsbrunner, Herbert AU - Saghafian, Morteza ID - 15091 T2 - arXiv TI - Chromatic alpha complexes ER - TY - CONF AB - In this paper we introduce a pruning of the medial axis called the (λ,α)-medial axis (axλα). We prove that the (λ,α)-medial axis of a set K is stable in a Gromov-Hausdorff sense under weak assumptions. More formally we prove that if K and K′ are close in the Hausdorff (dH) sense then the (λ,α)-medial axes of K and K′ are close as metric spaces, that is the Gromov-Hausdorff distance (dGH) between the two is 1/4-Hölder in the sense that dGH (axλα(K),axλα(K′)) ≲ dH(K,K′)1/4. The Hausdorff distance between the two medial axes is also bounded, by dH (axλα(K),λα(K′)) ≲ dH(K,K′)1/2. These quantified stability results provide guarantees for practical computations of medial axes from approximations. Moreover, they provide key ingredients for studying the computability of the medial axis in the context of computable analysis. AU - Lieutier, André AU - Wintraecken, Mathijs ID - 13048 SN - 9781450399135 T2 - Proceedings of the 55th Annual ACM Symposium on Theory of Computing TI - Hausdorff and Gromov-Hausdorff stable subsets of the medial axis ER - TY - JOUR AB - 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. AU - Edelsbrunner, Herbert AU - Osang, Georg F ID - 12086 JF - Algorithmica SN - 0178-4617 TI - A simple algorithm for higher-order Delaunay mosaics and alpha shapes VL - 85 ER - TY - JOUR AB - We present criteria for establishing a triangulation of a manifold. Given a manifold M, a simplicial complex A, and a map H from the underlying space of A to M, our criteria are presented in local coordinate charts for M, and ensure that H is a homeomorphism. These criteria do not require a differentiable structure, or even an explicit metric on M. No Delaunay property of A is assumed. The result provides a triangulation guarantee for algorithms that construct a simplicial complex by working in local coordinate patches. Because the criteria are easily verified in such a setting, they are expected to be of general use. AU - Boissonnat, Jean-Daniel AU - Dyer, Ramsay AU - Ghosh, Arijit AU - Wintraecken, Mathijs ID - 12287 JF - Discrete & Computational Geometry KW - Computational Theory and Mathematics KW - Discrete Mathematics and Combinatorics KW - Geometry and Topology KW - Theoretical Computer Science SN - 0179-5376 TI - Local criteria for triangulating general manifolds VL - 69 ER - TY - CONF AB - The limited exchange between human communities is a key factor in preventing the spread of COVID-19. This paper introduces a digital framework that combines an integration of real mobility data at the country scale with a series of modeling techniques and visual capabilities that highlight mobility patterns before and during the pandemic. The findings not only significantly exhibit mobility trends and different degrees of similarities at regional and local levels but also provide potential insight into the emergence of a pandemic on human behavior patterns and their likely socio-economic impacts. AU - Forghani, Mohammad AU - Claramunt, Christophe AU - Karimipour, Farid AU - Heiler, Georg ID - 12548 T2 - 2022 IEEE International Conference on Data Mining Workshops TI - Visual analytics of mobility network changes observed using mobile phone data during COVID-19 pandemic ER - TY - JOUR AB - 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. AU - Koehl, Patrice AU - Akopyan, Arseniy AU - Edelsbrunner, Herbert ID - 12544 IS - 3 JF - Journal of Chemical Information and Modeling SN - 1549-9596 TI - Computing the volume, surface area, mean, and Gaussian curvatures of molecules and their derivatives VL - 63 ER - TY - JOUR AB - We study a new discretization of the Gaussian curvature for polyhedral surfaces. This discrete Gaussian curvature is defined on each conical singularity of a polyhedral surface as the quotient of the angle defect and the area of the Voronoi cell corresponding to the singularity. We divide polyhedral surfaces into discrete conformal classes using a generalization of discrete conformal equivalence pioneered by Feng Luo. We subsequently show that, in every discrete conformal class, there exists a polyhedral surface with constant discrete Gaussian curvature. We also provide explicit examples to demonstrate that this surface is in general not unique. AU - Kourimska, Hana ID - 12764 JF - Discrete and Computational Geometry SN - 0179-5376 TI - Discrete yamabe problem for polyhedral surfaces VL - 70 ER - TY - JOUR AB - 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. AU - Corbet, René AU - Kerber, Michael AU - Lesnick, Michael AU - Osang, Georg F ID - 12709 JF - Discrete and Computational Geometry SN - 0179-5376 TI - Computing the multicover bifiltration VL - 70 ER - TY - JOUR AB - Kleinjohann (Archiv der Mathematik 35(1):574–582, 1980; Mathematische Zeitschrift 176(3), 327–344, 1981) and Bangert (Archiv der Mathematik 38(1):54–57, 1982) extended the reach rch(S) from subsets S of Euclidean space to the reach rchM(S) of subsets S of Riemannian manifolds M, where M is smooth (we’ll assume at least C3). Bangert showed that sets of positive reach in Euclidean space and Riemannian manifolds are very similar. In this paper we introduce a slight variant of Kleinjohann’s and Bangert’s extension and quantify the similarity between sets of positive reach in Euclidean space and Riemannian manifolds in a new way: Given p∈M and q∈S, we bound the local feature size (a local version of the reach) of its lifting to the tangent space via the inverse exponential map (exp−1p(S)) at q, assuming that rchM(S) and the geodesic distance dM(p,q) are bounded. These bounds are motivated by the importance of the reach and local feature size to manifold learning, topological inference, and triangulating manifolds and the fact that intrinsic approaches circumvent the curse of dimensionality. AU - Boissonnat, Jean Daniel AU - Wintraecken, Mathijs ID - 12763 JF - Journal of Applied and Computational Topology SN - 2367-1726 TI - The reach of subsets of manifolds VL - 7 ER - TY - JOUR AB - Isomanifolds are the generalization of isosurfaces to arbitrary dimension and codimension, i.e., submanifolds of Rd defined as the zero set of some multivariate multivalued smooth function f:Rd→Rd−n, where n is the intrinsic dimension of the manifold. A natural way to approximate a smooth isomanifold M=f−1(0) is to consider its piecewise linear (PL) approximation M^ based on a triangulation T of the ambient space Rd. In this paper, we describe a simple algorithm to trace isomanifolds from a given starting point. The algorithm works for arbitrary dimensions n and d, and any precision D. Our main result is that, when f (or M) has bounded complexity, the complexity of the algorithm is polynomial in d and δ=1/D (and unavoidably exponential in n). Since it is known that for δ=Ω(d2.5), M^ is O(D2)-close and isotopic to M , our algorithm produces a faithful PL-approximation of isomanifolds of bounded complexity in time polynomial in d. Combining this algorithm with dimensionality reduction techniques, the dependency on d in the size of M^ can be completely removed with high probability. We also show that the algorithm can handle isomanifolds with boundary and, more generally, isostratifolds. The algorithm for isomanifolds with boundary has been implemented and experimental results are reported, showing that it is practical and can handle cases that are far ahead of the state-of-the-art. AU - Boissonnat, Jean Daniel AU - Kachanovich, Siargey AU - Wintraecken, Mathijs ID - 12960 IS - 2 JF - SIAM Journal on Computing SN - 0097-5397 TI - Tracing isomanifolds in Rd in time polynomial in d using Coxeter–Freudenthal–Kuhn triangulations VL - 52 ER - TY - JOUR AB - We propose a characterization of discrete analytical spheres, planes and lines in the body-centered cubic (BCC) grid, both in the Cartesian and in the recently proposed alternative compact coordinate system, in which each integer triplet addresses some voxel in the grid. We define spheres and planes through double Diophantine inequalities and investigate their relevant topological features, such as functionality or the interrelation between the thickness of the objects and their connectivity and separation properties. We define lines as the intersection of planes. The number of the planes (up to six) is equal to the number of the pairs of faces of a BCC voxel that are parallel to the line. AU - Čomić, Lidija AU - Largeteau-Skapin, Gaëlle AU - Zrour, Rita AU - Biswas, Ranita AU - Andres, Eric ID - 13134 IS - 10 JF - Pattern Recognition SN - 0031-3203 TI - Discrete analytical objects in the body-centered cubic grid VL - 142 ER - TY - JOUR AB - Motivated by a problem posed in [10], we investigate the closure operators of the category SLatt of join semilattices and its subcategory SLattO of join semilattices with bottom element. In particular, we show that there are only finitely many closure operators of both categories, and provide a complete classification. We use this result to deduce the known fact that epimorphisms of SLatt and SLattO are surjective. We complement the paper with two different proofs of this result using either generators or Isbell’s zigzag theorem. AU - Dikranjan, D. AU - Giordano Bruno, A. AU - Zava, Nicolò ID - 14557 IS - S1 JF - Quaestiones Mathematicae SN - 1607-3606 TI - Epimorphisms and closure operators of categories of semilattices VL - 46 ER - TY - JOUR AB - 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)). AU - Edelsbrunner, Herbert AU - Garber, Alexey AU - Ghafari, Mohadese AU - Heiss, Teresa AU - Saghafian, Morteza ID - 14345 JF - Discrete and Computational Geometry SN - 0179-5376 TI - On angles in higher order Brillouin tessellations and related tilings in the plane ER - TY - JOUR AB - Given a triangle Δ, we study the problem of determining the smallest enclosing and largest embedded isosceles triangles of Δ with respect to area and perimeter. This problem was initially posed by Nandakumar [17, 22] and was first studied by Kiss, Pach, and Somlai [13], who showed that if Δ′ is the smallest area isosceles triangle containing Δ, then Δ′ and Δ share a side and an angle. In the present paper, we prove that for any triangle Δ, every maximum area isosceles triangle embedded in Δ and every maximum perimeter isosceles triangle embedded in Δ shares a side and an angle with Δ. Somewhat surprisingly, the case of minimum perimeter enclosing triangles is different: there are infinite families of triangles Δ whose minimum perimeter isosceles containers do not share a side and an angle with Δ. AU - Ambrus, Áron AU - Csikós, Mónika AU - Kiss, Gergely AU - Pach, János AU - Somlai, Gábor ID - 14464 IS - 7 JF - International Journal of Foundations of Computer Science SN - 0129-0541 TI - Optimal embedded and enclosing isosceles triangles VL - 34 ER - TY - JOUR AB - 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: 1. 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. 2. 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. 3. 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. AU - Biniaz, Ahmad AU - Jain, Kshitij AU - Lubiw, Anna AU - Masárová, Zuzana AU - Miltzow, Tillmann AU - Mondal, Debajyoti AU - Naredla, Anurag Murty AU - Tkadlec, Josef AU - Turcotte, Alexi ID - 12833 IS - 2 JF - Discrete Mathematics and Theoretical Computer Science SN - 1462-7264 TI - Token swapping on trees VL - 24 ER - TY - JOUR AB - Attempts to incorporate topological information in supervised learning tasks have resulted in the creation of several techniques for vectorizing persistent homology barcodes. In this paper, we study thirteen such methods. Besides describing an organizational framework for these methods, we comprehensively benchmark them against three well-known classification tasks. Surprisingly, we discover that the best-performing method is a simple vectorization, which consists only of a few elementary summary statistics. Finally, we provide a convenient web application which has been designed to facilitate exploration and experimentation with various vectorization methods. AU - Ali, Dashti AU - Asaad, Aras AU - Jimenez, Maria-Jose AU - Nanda, Vidit AU - Paluzo-Hidalgo, Eduardo AU - Soriano Trigueros, Manuel ID - 14739 IS - 12 JF - IEEE Transactions on Pattern Analysis and Machine Intelligence KW - Applied Mathematics KW - Artificial Intelligence KW - Computational Theory and Mathematics KW - Computer Vision and Pattern Recognition KW - Software SN - 0162-8828 TI - A survey of vectorization methods in topological data analysis VL - 45 ER - TY - JOUR AB - A graph G=(V, E) is called fully regular if for every independent set I c V, the number of vertices in V\I that are not connected to any element of I depends only on the size of I. A linear ordering of the vertices of G is called successive if for every i, the first i vertices induce a connected subgraph of G. We give an explicit formula for the number of successive vertex orderings of a fully regular graph. As an application of our results, we give alternative proofs of two theorems of Stanley and Gao & Peng, determining the number of linear edge orderings of complete graphs and complete bipartite graphs, respectively, with the property that the first i edges induce a connected subgraph. As another application, we give a simple product formula for the number of linear orderings of the hyperedges of a complete 3-partite 3-uniform hypergraph such that, for every i, the first i hyperedges induce a connected subgraph. We found similar formulas for complete (non-partite) 3-uniform hypergraphs and in another closely related case, but we managed to verify them only when the number of vertices is small. AU - Fang, Lixing AU - Huang, Hao AU - Pach, János AU - Tardos, Gábor AU - Zuo, Junchi ID - 13165 IS - 10 JF - Journal of Combinatorial Theory. Series A SN - 0097-3165 TI - Successive vertex orderings of fully regular graphs VL - 199 ER - TY - JOUR AB - Motivated by recent applications to entropy theory in dynamical systems, we generalise notions introduced by Matthews and define weakly weighted and componentwise weakly weighted (generalised) quasi-metrics. We then systematise and extend to full generality the correspondences between these objects and other structures arising in theoretical computer science and dynamics. In particular, we study the correspondences with weak partial metrics and, if the underlying space is a semilattice, with invariant (generalised) quasi-metrics satisfying the descending path condition, and with strictly monotone semi(-co-)valuations. We conclude discussing, for endomorphisms of generalised quasi-metric semilattices, a generalisation of both the known intrinsic semilattice entropy and the semigroup entropy. AU - Castellano, Ilaria AU - Giordano Bruno, Anna AU - Zava, Nicolò ID - 14362 JF - Theoretical Computer Science SN - 0304-3975 TI - Weakly weighted generalised quasi-metric spaces and semilattices VL - 977 ER - TY - JOUR AB - 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 a collection of sorted lists together with its persistence diagram. AU - Biswas, Ranita AU - Cultrera Di Montesano, Sebastiano AU - Edelsbrunner, Herbert AU - Saghafian, Morteza ID - 13182 JF - Journal of Applied and Computational Topology SN - 2367-1726 TI - Geometric characterization of the persistence of 1D maps ER - TY - THES AB - We introduce the notion of a Faustian interchange in a 1-parameter family of smooth functions to generalize the medial axis to critical points of index larger than 0. We construct and implement a general purpose algorithm for approximating such generalized medial axes. AU - Stephenson, Elizabeth R ID - 14226 SN - 2791-4585 TI - Generalizing medial axes with homology switches ER - TY - CONF AB - The medial axis of a set consists of the points in the ambient space without a unique closest point on the original set. Since its introduction, the medial axis has been used extensively in many applications as a method of computing a topologically equivalent skeleton. Unfortunately, one limiting factor in the use of the medial axis of a smooth manifold is that it is not necessarily topologically stable under small perturbations of the manifold. To counter these instabilities various prunings of the medial axis have been proposed. Here, we examine one type of pruning, called burning. Because of the good experimental results, it was hoped that the burning method of simplifying the medial axis would be stable. In this work we show a simple example that dashes such hopes based on Bing’s house with two rooms, demonstrating an isotopy of a shape where the medial axis goes from collapsible to non-collapsible. AU - Chambers, Erin AU - Fillmore, Christopher D AU - Stephenson, Elizabeth R AU - Wintraecken, Mathijs ED - Goaoc, Xavier ED - Kerber, Michael ID - 11428 SN - 1868-8969 T2 - 38th International Symposium on Computational Geometry TI - A cautionary tale: Burning the medial axis is unstable VL - 224 ER - TY - BOOK AB - This book constitutes the refereed proceedings of the 18th International Symposium on Web and Wireless Geographical Information Systems, W2GIS 2022, held in Konstanz, Germany, in April 2022. The 7 full papers presented together with 6 short papers in the volume were carefully reviewed and selected from 16 submissions. The papers cover topics that range from mobile GIS and Location-Based Services to Spatial Information Retrieval and Wireless Sensor Networks. ED - Karimipour, Farid ED - Storandt, Sabine ID - 11429 SN - 0302-9743 TI - Web and Wireless Geographical Information Systems VL - 13238 ER - TY - CHAP AB - To compute the persistent homology of a grayscale digital image one needs to build a simplicial or cubical complex from it. For cubical complexes, the two commonly used constructions (corresponding to direct and indirect digital adjacencies) can give different results for the same image. The two constructions are almost dual to each other, and we use this relationship to extend and modify the cubical complexes to become dual filtered cell complexes. We derive a general relationship between the persistent homology of two dual filtered cell complexes, and also establish how various modifications to a filtered complex change the persistence diagram. Applying these results to images, we derive a method to transform the persistence diagram computed using one type of cubical complex into a persistence diagram for the other construction. This means software for computing persistent homology from images can now be easily adapted to produce results for either of the two cubical complex constructions without additional low-level code implementation. AU - Bleile, Bea AU - Garin, Adélie AU - Heiss, Teresa AU - Maggs, Kelly AU - Robins, Vanessa ED - Gasparovic, Ellen ED - Robins, Vanessa ED - Turner, Katharine ID - 11440 SN - 9783030955182 T2 - Research in Computational Topology 2 TI - The persistent homology of dual digital image constructions VL - 30 ER - TY - JOUR AB - Point-set topology is among the most abstract branches of mathematics in that it lacks tangible notions of distance, length, magnitude, order, and size. There is no shape, no geometry, no algebra, and no direction. Everything we are used to visualizing is gone. In the teaching and learning of mathematics, this can present a conundrum. Yet, this very property makes point set topology perfect for teaching and learning abstract mathematical concepts. It clears our minds of preconceived intuitions and expectations and forces us to think in new and creative ways. In this paper, we present guided investigations into topology through questions and thinking strategies that open up fascinating problems. They are intended for faculty who already teach or are thinking about teaching a class in topology or abstract mathematical reasoning for undergraduates. They can be used to build simple to challenging projects in topology, proofs, honors programs, and research experiences. AU - Shipman, Barbara A. AU - Stephenson, Elizabeth R ID - 12307 IS - 5 JF - PRIMUS KW - Education KW - General Mathematics SN - 1051-1970 TI - Tangible topology through the lens of limits VL - 32 ER - TY - JOUR AB - 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. AU - Aichholzer, Oswin AU - Arroyo Guevara, Alan M AU - Masárová, Zuzana AU - Parada, Irene AU - Perz, Daniel AU - Pilz, Alexander AU - Tkadlec, Josef AU - Vogtenhuber, Birgit ID - 11938 IS - 2 JF - Journal of Graph Algorithms and Applications SN - 1526-1719 TI - On compatible matchings VL - 26 ER - TY - JOUR AB - Isomanifolds are the generalization of isosurfaces to arbitrary dimension and codimension, i.e. manifolds defined as the zero set of some multivariate vector-valued smooth function f : Rd → Rd−n. A natural (and efficient) way to approximate an isomanifold is to consider its Piecewise-Linear (PL) approximation based on a triangulation T of the ambient space Rd. In this paper, we give conditions under which the PL-approximation of an isomanifold is topologically equivalent to the isomanifold. The conditions are easy to satisfy in the sense that they can always be met by taking a sufficiently fine triangulation T . This contrasts with previous results on the triangulation of manifolds where, in arbitrary dimensions, delicate perturbations are needed to guarantee topological correctness, which leads to strong limitations in practice. We further give a bound on the Fréchet distance between the original isomanifold and its PL-approximation. Finally we show analogous results for the PL-approximation of an isomanifold with boundary. AU - Boissonnat, Jean-Daniel AU - Wintraecken, Mathijs ID - 9649 JF - Foundations of Computational Mathematics TI - The topological correctness of PL approximations of isomanifolds VL - 22 ER - TY - JOUR AB - Motivated by the recent introduction of the intrinsic semilattice entropy, we study generalized quasi-metric semilattices and their categories. We investigate the relationship between these objects and generalized semivaluations, extending Nakamura and Schellekens' approach. Finally, we use this correspondence to compare the intrinsic semilattice entropy and the semigroup entropy induced in particular situations, like sets, torsion abelian groups and vector spaces. AU - Dikranjan, Dikran AU - Giordano Bruno, Anna AU - Künzi, Hans Peter AU - Zava, Nicolò AU - Toller, Daniele ID - 10413 JF - Topology and its Applications SN - 0166-8641 TI - Generalized quasi-metric semilattices VL - 309 ER - TY - JOUR AB - The Voronoi tessellation in Rd is defined by locally minimizing the power distance to given weighted points. Symmetrically, the Delaunay mosaic can be defined by locally maximizing the negative power distance to other such points. We prove that the average of the two piecewise quadratic functions is piecewise linear, and that all three functions have the same critical points and values. Discretizing the two piecewise quadratic functions, we get the alpha shapes as sublevel sets of the discrete function on the Delaunay mosaic, and analogous shapes as superlevel sets of the discrete function on the Voronoi tessellation. For the same non-critical value, the corresponding shapes are disjoint, separated by a narrow channel that contains no critical points but the entire level set of the piecewise linear function. AU - Biswas, Ranita AU - Cultrera Di Montesano, Sebastiano AU - Edelsbrunner, Herbert AU - Saghafian, Morteza ID - 10773 JF - Discrete and Computational Geometry SN - 0179-5376 TI - Continuous and discrete radius functions on Voronoi tessellations and Delaunay mosaics VL - 67 ER - TY - CONF AB - Digital images enable quantitative analysis of material properties at micro and macro length scales, but choosing an appropriate resolution when acquiring the image is challenging. A high resolution means longer image acquisition and larger data requirements for a given sample, but if the resolution is too low, significant information may be lost. This paper studies the impact of changes in resolution on persistent homology, a tool from topological data analysis that provides a signature of structure in an image across all length scales. Given prior information about a function, the geometry of an object, or its density distribution at a given resolution, we provide methods to select the coarsest resolution yielding results within an acceptable tolerance. We present numerical case studies for an illustrative synthetic example and samples from porous materials where the theoretical bounds are unknown. AU - Heiss, Teresa AU - Tymochko, Sarah AU - Story, Brittany AU - Garin, Adélie AU - Bui, Hoa AU - Bleile, Bea AU - Robins, Vanessa ID - 10828 SN - 9781665439022 T2 - 2021 IEEE International Conference on Big Data TI - The impact of changes in resolution on the persistent homology of images ER - TY - JOUR AB - We classify contravariant pairings between standard Whittaker modules and Verma modules over a complex semisimple Lie algebra. These contravariant pairings are useful in extending several classical techniques for category O to the Miličić–Soergel category N . We introduce a class of costandard modules which generalize dual Verma modules, and describe canonical maps from standard to costandard modules in terms of contravariant pairings. We show that costandard modules have unique irreducible submodules and share the same composition factors as the corresponding standard Whittaker modules. We show that costandard modules give an algebraic characterization of the global sections of costandard twisted Harish-Chandra sheaves on the associated flag variety, which are defined using holonomic duality of D-modules. We prove that with these costandard modules, blocks of category N have the structure of highest weight categories and we establish a BGG reciprocity theorem for N . AU - Brown, Adam AU - Romanov, Anna ID - 11545 IS - 11 JF - Journal of Algebra KW - Algebra and Number Theory SN - 0021-8693 TI - Contravariant pairings between standard Whittaker modules and Verma modules VL - 609 ER - TY - JOUR AB - Targeting dysregulated Ca2+ signaling in cancer cells is an emerging chemotherapy approach. We previously reported that store-operated Ca2+ entry (SOCE) blockers, such as RP4010, are promising antitumor drugs for esophageal cancer. As a tyrosine kinase inhibitor (TKI), afatinib received FDA approval to be used in targeted therapy for patients with EGFR mutation-positive cancers. While preclinical studies and clinical trials have shown that afatinib has benefits for esophageal cancer patients, it is not known whether a combination of afatinib and RP4010 could achieve better anticancer effects. Since TKI can alter intracellular Ca2+ dynamics through EGFR/phospholipase C-γ pathway, in this study, we evaluated the inhibitory effect of afatinib and RP4010 on intracellular Ca2+ oscillations in KYSE-150, a human esophageal squamous cell carcinoma cell line, using both experimental and mathematical simulations. Our mathematical simulation of Ca2+ oscillations could fit well with experimental data responding to afatinib or RP4010, both separately or in combination. Guided by simulation, we were able to identify a proper ratio of afatinib and RP4010 for combined treatment, and such a combination presented synergistic anticancer-effect evidence by experimental measurement of intracellular Ca2+ and cell proliferation. This intracellular Ca2+ dynamic-based mathematical simulation approach could be useful for a rapid and cost-effective evaluation of combined targeting therapy drugs. AU - Chang, Yan AU - Funk, Marah AU - Roy, Souvik AU - Stephenson, Elizabeth R AU - Choi, Sangyong AU - Kojouharov, Hristo V. AU - Chen, Benito AU - Pan, Zui ID - 10754 IS - 3 JF - International Journal of Molecular Sciences SN - 16616596 TI - Developing a mathematical model of intracellular Calcium dynamics for evaluating combined anticancer effects of afatinib and RP4010 in esophageal cancer VL - 23 ER - TY - JOUR AB - Extending a result of Milena Radnovic and Serge Tabachnikov, we establish conditionsfor two different non-symmetric norms to define the same billiard reflection law. AU - Akopyan, Arseniy AU - Karasev, Roman ID - 7791 IS - 4 JF - European Journal of Mathematics SN - 2199-675X TI - When different norms lead to same billiard trajectories? VL - 8 ER - TY - JOUR AB - 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. AU - Biswas, Ranita AU - Cultrera di Montesano, Sebastiano AU - Edelsbrunner, Herbert AU - Saghafian, Morteza ID - 11660 JF - LIPIcs TI - A window to the persistence of 1D maps. I: Geometric characterization of critical point pairs ER - TY - JOUR AB - 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. AU - Biswas, Ranita AU - Cultrera di Montesano, Sebastiano AU - Edelsbrunner, Herbert AU - Saghafian, Morteza ID - 11658 JF - Leibniz International Proceedings on Mathematics TI - Depth in arrangements: Dehn–Sommerville–Euler relations with applications ER - TY - GEN AB - Given a locally finite set A⊆Rd and a coloring χ:A→{0,1,…,s}, we introduce the chromatic Delaunay mosaic of χ, which is a Delaunay mosaic in Rs+d that represents how points of different colors mingle. Our main results are bounds on the size of the chromatic Delaunay mosaic, in which we assume that d and s are constants. For example, if A is finite with n=#A, and the coloring is random, then the chromatic Delaunay mosaic has O(n⌈d/2⌉) cells in expectation. In contrast, for Delone sets and Poisson point processes in Rd, the expected number of cells within a closed ball is only a constant times the number of points in this ball. Furthermore, in R2 all colorings of a dense set of n points have chromatic Delaunay mosaics of size O(n). This encourages the use of chromatic Delaunay mosaics in applications. AU - Biswas, Ranita AU - Cultrera di Montesano, Sebastiano AU - Draganov, Ondrej AU - Edelsbrunner, Herbert AU - Saghafian, Morteza ID - 15090 T2 - arXiv TI - On the size of chromatic Delaunay mosaics ER - TY - JOUR AB - 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. AU - Goudarzi, Samira AU - Sharif, Mohammad AU - Karimipour, Farid ID - 10208 JF - Journal of Ambient Intelligence and Humanized Computing KW - general computer science SN - 1868-5137 TI - A context-aware dimension reduction framework for trajectory and health signal analyses VL - 13 ER - TY - JOUR AU - Adams, Henry AU - Kourimska, Hana AU - Heiss, Teresa AU - Percival, Sarah AU - Ziegelmeier, Lori ID - 10071 IS - 9 JF - Notices of the American Mathematical Society SN - 0002-9920 TI - How to tutorial-a-thon VL - 68 ER - TY - CONF AB - 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. AU - Ilharco, Cesar AU - Shirazi, Afsaneh AU - Gopalan, Arjun AU - Nagrani, Arsha AU - Bratanič, Blaž AU - Bregler, Chris AU - Liu, Christina AU - Ferreira, Felipe AU - Barcik, Gabriek AU - Ilharco, Gabriel AU - Osang, Georg F AU - Bulian, Jannis AU - Frank, Jared AU - Smaira, Lucas AU - Cao, Qin AU - Marino, Ricardo AU - Patel, Roma AU - Leung, Thomas AU - Imbrasaite, Vaiva ID - 10367 SN - 9-781-9540-8557-2 T2 - 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing, Tutorial Abstracts TI - Recognizing multimodal entailment ER - TY - JOUR AB - We consider infinite-dimensional properties in coarse geometry for hyperspaces consisting of finite subsets of metric spaces with the Hausdorff metric. We see that several infinite-dimensional properties are preserved by taking the hyperspace of subsets with at most n points. On the other hand, we prove that, if a metric space contains a sequence of long intervals coarsely, then its hyperspace of finite subsets is not coarsely embeddable into any uniformly convex Banach space. As a corollary, the hyperspace of finite subsets of the real line is not coarsely embeddable into any uniformly convex Banach space. It is also shown that every (not necessarily bounded geometry) metric space with straight finite decomposition complexity has metric sparsification property. AU - Weighill, Thomas AU - Yamauchi, Takamitsu AU - Zava, Nicolò ID - 10608 JF - European Journal of Mathematics SN - 2199-675X TI - Coarse infinite-dimensionality of hyperspaces of finite subsets ER - TY - CONF AB - 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. AU - Aichholzer, Oswin AU - Arroyo Guevara, Alan M AU - Masárová, Zuzana AU - Parada, Irene AU - Perz, Daniel AU - Pilz, Alexander AU - Tkadlec, Josef AU - Vogtenhuber, Birgit ID - 9296 SN - 03029743 T2 - 15th International Conference on Algorithms and Computation TI - On compatible matchings VL - 12635 ER - TY - JOUR AB - 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. AU - Edelsbrunner, Herbert AU - Nikitenko, Anton AU - Osang, Georg F ID - 9465 IS - 1 JF - Journal of Geometry SN - 00472468 TI - A step in the Delaunay mosaic of order k VL - 112 ER - TY - CONF AB - Modeling a crystal as a periodic point set, we present a fingerprint consisting of density functionsthat facilitates the efficient search for new materials and material properties. We prove invarianceunder isometries, continuity, and completeness in the generic case, which are necessary featuresfor the reliable comparison of crystals. The proof of continuity integrates methods from discretegeometry and lattice theory, while the proof of generic completeness combines techniques fromgeometry with analysis. The fingerprint has a fast algorithm based on Brillouin zones and relatedinclusion-exclusion formulae. We have implemented the algorithm and describe its application tocrystal structure prediction. AU - Edelsbrunner, Herbert AU - Heiss, Teresa AU - Kurlin , Vitaliy AU - Smith, Philip AU - Wintraecken, Mathijs ID - 9345 SN - 1868-8969 T2 - 37th International Symposium on Computational Geometry (SoCG 2021) TI - The density fingerprint of a periodic point set VL - 189 ER - TY - CONF AB - 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. AU - Biswas, Ranita AU - Cultrera di Montesano, Sebastiano AU - Edelsbrunner, Herbert AU - Saghafian, Morteza ID - 9604 SN - 18688969 T2 - Leibniz International Proceedings in Informatics TI - Counting cells of order-k voronoi tessellations in ℝ3 with morse theory VL - 189 ER - TY - CONF AB - We define a new compact coordinate system in which each integer triplet addresses a voxel in the BCC grid, and we investigate some of its properties. We propose a characterization of 3D discrete analytical planes with their topological features (in the Cartesian and in the new coordinate system) such as the interrelation between the thickness of the plane and the separability constraint we aim to obtain. AU - Čomić, Lidija AU - Zrour, Rita AU - Largeteau-Skapin, Gaëlle AU - Biswas, Ranita AU - Andres, Eric ID - 9824 SN - 03029743 T2 - Discrete Geometry and Mathematical Morphology TI - Body centered cubic grid - coordinate system and discrete analytical plane definition VL - 12708 ER - TY - JOUR AB - 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. AU - Aichholzer, Oswin AU - Akitaya, Hugo A. AU - Cheung, Kenneth C. AU - Demaine, Erik D. AU - Demaine, Martin L. AU - Fekete, Sándor P. AU - Kleist, Linda AU - Kostitsyna, Irina AU - Löffler, Maarten AU - Masárová, Zuzana AU - Mundilova, Klara AU - Schmidt, Christiane ID - 8317 JF - Computational Geometry: Theory and Applications SN - 09257721 TI - Folding polyominoes with holes into a cube VL - 93 ER - TY - JOUR AB - Let g be a complex semisimple Lie algebra. We give a classification of contravariant forms on the nondegenerate Whittaker g-modules Y(χ,η) introduced by Kostant. We prove that the set of all contravariant forms on Y(χ,η) forms a vector space whose dimension is given by the cardinality of the Weyl group of g. We also describe a procedure for parabolically inducing contravariant forms. As a corollary, we deduce the existence of the Shapovalov form on a Verma module, and provide a formula for the dimension of the space of contravariant forms on the degenerate Whittaker modules M(χ,η) introduced by McDowell. AU - Brown, Adam AU - Romanov, Anna ID - 8773 IS - 1 JF - Proceedings of the American Mathematical Society KW - Applied Mathematics KW - General Mathematics SN - 0002-9939 TI - Contravariant forms on Whittaker modules VL - 149 ER -