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 -