2025-02-07 | | Total: 3
In the preprocessing framework one is given a set of regions that one is allowed to preprocess to create some auxiliary structure such that when a realization of these regions is given, consisting of one point per region, this auxiliary structure can be used to reconstruct some desired output geometric structure more efficiently than would have been possible without preprocessing. Prior work showed that a set of $n$ unit disks of constant ply can be preprocessed in $O(n\log n)$ time such that the convex hull of any realization can be reconstructed in $O(n)$ time. (This prior work focused on triangulations and the convex hull was a byproduct.) In this work we show for the first time that we can reconstruct the convex hull in time proportional to the number of \emph{unstable} disks, which may be sublinear, and that such a running time is the best possible. Here a disk is called \emph{stable} if the combinatorial structure of the convex hull does not depend on the location of its realized point. The main tool by which we achieve our results is by using a supersequence as the auxiliary structure constructed in the preprocessing phase, that is we output a supersequence of the disks such that the convex hull of any realization is a subsequence. One advantage of using a supersequence as the auxiliary structure is that it allows us to decouple the preprocessing phase from the reconstruction phase in a stronger sense than was possible in previous work, resulting in two separate algorithmic problems which may be independent interest. Finally, in the process of obtaining our results for convex hulls, we solve the corresponding problem of creating such supersequences for intervals in one dimension, yielding corresponding results for that case.
We develop a theory of random flat-foldable origami. Given a crease pattern, we consider a uniformly random assignment of mountain and valley creases, conditioned on the assignment being flat-foldable at each vertex. A natural method to approximately sample from this distribution is via the face-flip Markov chain where one selects a face of the crease pattern uniformly at random and, if possible, flips all edges of that face from mountain to valley and vice-versa. We prove that this chain mixes rapidly for several natural families of origami tessellations -- the square twist, the square grid, and the Miura-ori -- as well as for the single-vertex crease pattern. We also compare local to global flat-foldability and show that on the square grid, a random locally flat-foldable configuration is exponentially unlikely to be globally flat-foldable.
Many practical applications in topological data analysis arise from data in the form of point clouds, which then yield simplicial complexes. The combinatorial structure of simplicial complexes captures the topological relationships between the elements of the complex. In addition to the combinatorial structure, simplicial complexes possess a geometric realization that provides a concrete way to visualize the complex and understand its geometric properties. This work presents an amended Hausdorff distance as an extended metric that integrates geometric proximity with the topological features of simplicial complexes. We also present a version of the simplicial Hausdorff metric for filtered complexes and show results on its computational complexity. In addition, we discuss concerns about the monotonicity of the measurement functions involved in the setup of the simplicial complexes.