TY - JOUR
AB - Generalizing the decomposition of a connected planar graph into a tree and a dual tree, we prove a combinatorial analog of the classic Helmholtz–Hodge decomposition of a smooth vector field. Specifically, we show that for every polyhedral complex, K, and every dimension, p, there is a partition of the set of p-cells into a maximal p-tree, a maximal p-cotree, and a collection of p-cells whose cardinality is the p-th reduced Betti number of K. Given an ordering of the p-cells, this tri-partition is unique, and it can be computed by a matrix reduction algorithm that also constructs canonical bases of cycle and boundary groups.
AU - Edelsbrunner, Herbert
AU - Ölsböck, Katharina
ID - 7666
JF - Discrete and Computational Geometry
SN - 01795376
TI - Tri-partitions and bases of an ordered complex
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
JF - European Journal of Mathematics
SN - 2199675X
TI - When different norms lead to same billiard trajectories?
ER -
TY - JOUR
AB - We investigate a sheaf-theoretic interpretation of stratification learning from geometric and topological perspectives. Our main result is the construction of stratification learning algorithms framed in terms of a sheaf on a partially ordered set with the Alexandroff topology. We prove that the resulting decomposition is the unique minimal stratification for which the strata are homogeneous and the given sheaf is constructible. In particular, when we choose to work with the local homology sheaf, our algorithm gives an alternative to the local homology transfer algorithm given in Bendich et al. (Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1355–1370, ACM, New York, 2012), and the cohomology stratification algorithm given in Nanda (Found. Comput. Math. 20(2), 195–222, 2020). Additionally, we give examples of stratifications based on the geometric techniques of Breiding et al. (Rev. Mat. Complut. 31(3), 545–593, 2018), illustrating how the sheaf-theoretic approach can be used to study stratifications from both topological and geometric perspectives. This approach also points toward future applications of sheaf theory in the study of topological data analysis by illustrating the utility of the language of sheaf theory in generalizing existing algorithms.
AU - Brown, Adam
AU - Wang, Bei
ID - 7905
JF - Discrete & Computational Geometry
SN - 0179-5376
TI - Sheaf-theoretic stratification learning from geometric and topological perspectives
ER -
TY - THES
AB - This thesis considers two examples of reconfiguration problems: flipping edges in edge-labelled triangulations of planar point sets and swapping labelled tokens placed on vertices of a graph. In both cases the studied structures – all the triangulations of a given point set or all token placements on a given graph – can be thought of as vertices of the so-called reconfiguration graph, in which two vertices are adjacent if the corresponding structures differ by a single elementary operation – by a flip of a diagonal in a triangulation or by a swap of tokens on adjacent vertices, respectively. We study the reconfiguration of one instance of a structure into another via (shortest) paths in the reconfiguration graph.
For triangulations of point sets in which each edge has a unique label and a flip transfers the label from the removed edge to the new edge, we prove a polynomial-time testable condition, called the Orbit Theorem, that characterizes when two triangulations of the same point set lie in the same connected component of the reconfiguration graph. The condition was first conjectured by Bose, Lubiw, Pathak and Verdonschot. We additionally provide a polynomial time algorithm that computes a reconfiguring flip sequence, if it exists. Our proof of the Orbit Theorem uses topological properties of a certain high-dimensional cell complex that has the usual reconfiguration graph as its 1-skeleton.
In the context of token swapping on a tree graph, we make partial progress on the problem of finding shortest reconfiguration sequences. We disprove the so-called Happy Leaf Conjecture and demonstrate the importance of swapping tokens that are already placed at the correct vertices. We also prove that a generalization of the problem to weighted coloured token swapping is NP-hard on trees but solvable in polynomial time on paths and stars.
AU - Masárová, Zuzana
ID - 7944
KW - reconfiguration
KW - reconfiguration graph
KW - triangulations
KW - flip
KW - constrained triangulations
KW - shellability
KW - piecewise-linear balls
KW - token swapping
KW - trees
KW - coloured weighted token swapping
SN - 978-3-99078-005-3
TI - Reconfiguration problems
ER -
TY - CONF
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: ℝ^d → ℝ^(d-n). A natural (and efficient) way to approximate an isomanifold is to consider its Piecewise-Linear (PL) approximation based on a triangulation 𝒯 of the ambient space ℝ^d. 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 𝒯. 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 - 7952
SN - 1868-8969
T2 - 36th International Symposium on Computational Geometry
TI - The topological correctness of PL-approximations of isomanifolds
VL - 164
ER -