math.GN

arXiv:2412.16962v1 Announce Type: new Abstract: The 2x2 space-filling curve is a type of generalized space-filling curve characterized by a basic unit is in a "U-shape" that traverses a 2x2 grid. In this work, we propose a universal framework for constructing general 2x2 curves where self-similarity is not strictly required. The construction is based on a novel set of grammars that define the expansion of curves from level 0 (a single point) to level 1 (units in U-shapes), which ultimately determines all $36 \times 2^k$ possible forms of curves on any level $k$ initialized from single points. We further developed an encoding system in which each unique form of the curve is associated with a specific combination of an initial seed and a sequence of codes that sufficiently describes both the global and local structures of the curve. We demonstrated that this encoding system is a powerful tool for studying 2x2 curves and we established comprehensive theoretical foundations from the following three key perspectives: 1) We provided a determinstic encoding for any unit on any level and position on the curve, enabling the study of curve generation across arbitrary parts on the curve and ranges of iterations; 2) We gave determinstic encodings for various curve transformations, including rotations, reflections and reversals; 3) We provided deterministic forms of families of curves exhibiting specific structures, including homogeneous curves, curves with identical shapes, with partially identical shapes and with completely distinct shapes. We also explored families of recursive curves, subunit identically shaped curves, symmetric curves and closed curves. Finally, we proposed a method to calculate the location of any point on the curve arithmetically, within a time complexity linear to the level of the curve.

arXiv:2307.15130v5 Announce Type: replace Abstract: Data consisting of a graph with a function mapping into $\mathbb{R}^d$ arise in many data applications, encompassing structures such as Reeb graphs, geometric graphs, and knot embeddings. As such, the ability to compare and cluster such objects is required in a data analysis pipeline, leading to a need for distances between them. In this work, we study the interleaving distance on discretization of these objects, called mapper graphs when $d=1$, where functor representations of the data can be compared by finding pairs of natural transformations between them. However, in many cases, computation of the interleaving distance is NP-hard. For this reason, we take inspiration from recent work by Robinson to find quality measures for families of maps that do not rise to the level of a natural transformation, called assignments. We then endow the functor images with the extra structure of a metric space and define a loss function which measures how far an assignment is from making the required diagrams of an interleaving commute. Finally we show that the computation of the loss function is polynomial with a given assignment. We believe this idea is both powerful and translatable, with the potential to provide approximations and bounds on interleavings in a broad array of contexts.