More Like this

1. Discrete Fréchet Distance Oracles

   https://doi.org/10.4230/LIPIcs.SoCG.2024.10  

   Aronov, Boris; Farhana, Tsuri; Katz, Matthew J; Ramesh, Indu (June 2024, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Mulzer, Wolfgang; Phillips, Jeff M (Ed.)

   It is unlikely that the discrete Fréchet distance between two curves of length n can be computed in strictly subquadratic time. We thus consider the setting where one of the curves, P, is known in advance. In particular, we wish to construct data structures (distance oracles) of near-linear size that support efficient distance queries with respect to P in sublinear time. Since there is evidence that this is impossible for query curves of length Θ(n^α), for any α > 0, we focus on query curves of (small) constant length, for which we are able to devise distance oracles with the desired bounds. We extend our tools to handle subcurves of the given curve, and even arbitrary vertex-to-vertex subcurves of a given geometric tree. That is, we construct an oracle that can quickly compute the distance between a short polygonal path (the query) and a path in the preprocessed tree between two query-specified vertices. Moreover, we define a new family of geometric graphs, t-local graphs (which strictly contains the family of geometric spanners with constant stretch), for which a similar oracle exists: we can preprocess a graph G in the family, so that, given a query segment and a pair u,v of vertices in G, one can quickly compute the smallest discrete Fréchet distance between the segment and any (u,v)-path in G. The answer is exact, if t = 1, and approximate if t > 1. 

   more » « less
2. Shape-Graph Matching Network (SGM-net): Registration for Statistical Shape Analysis

   https://doi.org/10.1109/ISBI56570.2024.10635203  

   Liang, Shenyuan; Srivastava, Anuj; Segundo, Mauricio Pamplona; Sarkar, Sudeep; Aakur, Sathyanarayanan N (May 2024, IEEE)

   This paper focuses on the registration problem of shape graphs, where a shape graph is a set of nodes connected by articulated curves with arbitrary shapes. This registration requires optimization over the permutation group, made challenging by differences in nodes (in terms of numbers, locations) and edges (in terms of shapes, placements, and sizes) across graphs. We tackle this registration problem using a neuralnetwork architecture with an unsupervised loss function based on the elastic shape metric for curves. This architecture results in (1) state-of-the-art matching performance and (2) an order of magnitude reduction in the computational cost relative to baseline approaches. We demonstrate the effectiveness of the proposed approach using both simulated data and real-world 2D retinal blood vessels and 3D microglia graphs. 

   more » « less
3. Constant spacing in filament bundles

   https://doi.org/10.1088/1367-2630/ab1c2d  

   Atkinson, Daria W.; Santangelo, Christian D.; Grason, Gregory M. (June 2019, New Journal of Physics)

   Abstract Assemblies of one-dimensional filaments appear in a wide range of physical systems: from biopolymer bundles, columnar liquid crystals, and superconductor vortex arrays; to familiar macroscopic materials, like ropes, cables, and textiles. Interactions between the constituent filaments in such systems are most sensitive to thedistance of closest approachbetween the central curves which approximate their configuration, subjecting these distinct assemblies to common geometric constraints. In this paper, we consider two distinct notions of constant spacing in multi-filament packings in ${\mathbb{R}}^3$:equidistance, where the distance of closest approach is constant along the length of filament pairs; andisometry, where the distances of closest approach between all neighboring filaments are constant and equal. We show that, although any smooth curve in ${\mathbb{R}}^3$permits one dimensional families of collinear equidistant curves belonging to a ruled surface, there are only two families of tangent fields with mutually equidistant integral curves in ${\mathbb{R}}^3$. The relative shapes and configurations of curves in these families are highly constrained: they must be either (isometric) developable domains, which can bend, but not twist; or (non-isometric) constant-pitch helical bundles, which can twist, but not bend. Thus, filament textures that are simultaneously bent and twisted, such as twisted toroids of condensed DNA plasmids or wire ropes, are doubly frustrated: twist frustrates constant neighbor spacing in the cross-section, while non-equidistance requires additional longitudinal variations of spacing along the filaments. To illustrate the consequences of the failure of equidistance, we compare spacing in three ‘almost equidistant’ ansatzes for twisted toroidal bundles and use our formulation of equidistance to construct upper bounds on the growth of longitudinal variations of spacing with bundle thickness. 

   more » « less
4. Parallelized Topological Relaxation Algorithm

   https://doi.org/10.1109/BigData47090.2019.9006309  

   Ruan, Guangchen; Zhang, Hui (December 2019, 2019 IEEE International Conference on Big Data (Big Data))

   Geometric problems of interest to mathematical visualization applications involve changing structures, such as the moves that transform one knot into an equivalent knot. In this paper, we describe mathematical entities (curves and surfaces) as link-node graphs, and make use of energy-driven relaxation algorithms to optimize their geometric shapes by moving knots and surfaces to their simplified equivalence. Furthermore, we design and conFigure parallel functional units in the relaxation algorithms to accelerate the computation these mathematical deformations require. Results show that we can achieve significant performance optimization via the proposed threading model and level of parallelization. 

   more » « less
5. Induced Subgraphs and Tree Decompositions IV. (Even Hole, Diamond, Pyramid)-Free Graphs

   https://doi.org/10.37236/11623  

   Abrishami, Tara; Chudnovsky, Maria; Hajebi, Sepehr; Spirkl, Sophie (April 2023, The Electronic Journal of Combinatorics)

   A hole in a graph $$G$$ is an induced cycle of length at least four, and an even hole is a hole of even length. The diamond is the graph obtained from the complete graph $$K_4$$ by removing an edge. A pyramid is a graph consisting of a vertex $$a$$ called the apex and a triangle $$\{b_1, b_2, b_3\}$$ called the base, and three paths $$P_i$$ from $$a$$ to $$b_i$$ for $$1 \leq i \leq 3$$, all of length at least one, such that for $$i \neq j$$, the only edge between $$P_i \setminus \{a\}$$ and $$P_j \setminus \{a\}$$ is $$b_ib_j$$, and at most one of $$P_1$$, $$P_2$$, and $$P_3$$ has length exactly one. For a family $$\mathcal{H}$$ of graphs, we say a graph $$G$$ is $$\mathcal{H}$$-free if no induced subgraph of $$G$$ is isomorphic to a member of $$\mathcal{H}$$. Cameron, da Silva, Huang, and Vušković proved that (even hole, triangle)-free graphs have treewidth at most five, which motivates studying the treewidth of even-hole-free graphs of larger clique number. Sintiari and Trotignon provided a construction of (even hole, pyramid, $$K_4$$)-free graphs of arbitrarily large treewidth. Here, we show that for every $$t$$, (even hole, pyramid, diamond, $$K_t$$)-free graphs have bounded treewidth. The graphs constructed by Sintiari and Trotignon contain diamonds, so our result is sharp in the sense that it is false if we do not exclude diamonds. Our main result is in fact more general, that treewidth is bounded in graphs excluding certain wheels and three-path-configurations, diamonds, and a fixed complete graph. The proof uses “non-crossing decompositions” methods similar to those in previous papers in this series. In previous papers, however, bounded degree was a necessary condition to prove bounded treewidth. The result of this paper is the first to use the method of “non-crossing decompositions” to prove bounded treewidth in a graph class of unbounded maximum degree. 

   more » « less