Computational Geometry

New submissions

• New submissions
• Cross-lists

New submissions for Fri, 7 Jun 24

[1]  arXiv:2406.03632 [pdf, other]

Title: Finding maximum matchings in RDV graphs efficiently

Authors: Therese Biedl, Prashant Gokhale

Subjects: Computational Geometry (cs.CG); Data Structures and Algorithms (cs.DS)

In this paper, we study the maximum matching problem in RDV graphs, i.e., graphs that are vertex-intersection graphs of downward paths in a rooted tree. We show that this problem can be reduced to a problem of testing (repeatedly) whether a vertical segment intersects one of a dynamically changing set of horizontal segments, which in turn reduces to an orthogonal ray shooting query. Using a suitable data structure, we can therefore find a maximum matching in $O(n\log n)$ time (presuming a linear-sized representation of the graph is given), i.e., without even looking at all edges.

[2]  arXiv:2406.03756 [pdf, other]

Title: High-Order Continuous Geometrical Validity

Authors: Federico Sichetti, Zizhou Huang, Marco Attene, Denis Zorin, Enrico Puppo, Daniele Panozzo

Subjects: Computational Geometry (cs.CG); Graphics (cs.GR)

We propose a conservative algorithm to test the geometrical validity of simplicial (triangles, tetrahedra), tensor product (quadrilaterals, hexahedra), and mixed (prisms) elements of arbitrary polynomial order as they deform over a piecewise-linear trajectory.
Our algorithm uses a combination of adaptive B\'ezier refinement and bisection search to determine if, when, and where the Jacobian determinant of an element's polynomial geometric map becomes negative in the transition from one configuration to another.
Unlike previous approaches, our method preserves its properties also when implemented using floating point arithmetic: This feature comes at a small additional runtime cost compared to existing inexact methods, making it a drop-in replacement for current validity tests, while providing superior robustness and generality.
To prove the practical effectiveness of our algorithm, we demonstrate its use in a high-order Incremental Potential Contact (IPC) elastodynamic simulator, and we experimentally show that it prevents invalid, simulation-breaking configurations that would otherwise occur using inexact methods, without the need for manual parameter tuning.

[3]  arXiv:2406.04102 [pdf, other]

Title: Chromatic Topological Data Analysis

Authors: Sebastiano Cultrera di Montesano, Ondrej Draganov, Herbert Edelsbrunner, Morteza Saghafian

Subjects: Computational Geometry (cs.CG)

Exploring the shape of point configurations has been a key driver in the evolution of TDA (short for topological data analysis) since its infancy. This survey illustrates the recent efforts to broaden these ideas to model spatial interactions among multiple configurations, each distinguished by a color. It describes advances in this area and prepares the ground for further exploration by mentioning unresolved questions and promising research avenues while focusing on the overlap with discrete geometry.

Cross-lists for Fri, 7 Jun 24

[4]  arXiv:2406.04259 (cross-list from math.AT) [pdf, other]

Title: Topological Stability and Latschev-type Reconstruction Theorems for $\boldsymbol{\mathrm{CAT}(κ)}$ Spaces

Authors: Rafal Komendarczyk, Sushovan Majhi, Will Tran

Subjects: Algebraic Topology (math.AT); Computational Geometry (cs.CG); Metric Geometry (math.MG)

We consider the problem of homotopy-type reconstruction of compact shapes $X\subset\mathbb{R}^N$ that are $\mathrm{CAT}(\kappa)$ in the intrinsic length metric. The reconstructed spaces are in the form of Vietoris--Rips complexes computed from a compact sample $S$, Hausdorff--close to the unknown shape $X$. Instead of the Euclidean metric on the sample, our reconstruction technique leverages a path-based metric to compute these complexes. As naturally emerging in the framework of reconstruction, we also study the Gromov--Hausdorff topological stability and finiteness problem for general compact $\mathrm{CAT}(\kappa)$ spaces. Our techniques provide novel sampling conditions alternative to the existing and commonly used techniques using weak feature size and $\mu$--reach. In particular, we introduce a new parameter, called the {\em restricted distortion}, which is a generalization of the well-known global distortion of embedding. We show examples of Euclidean subspaces, for which the known parameters such as the reach, $\mu$--reach and weak features size vanish, whereas the restricted distortion is finite, making our reconstruction results applicable for such spaces.

• New submissions
• Cross-lists