ALT Given a set system (X, S), we consider the problems of constructing perfect matchings and spanning paths (also known as Welzl orders) of X with low crossing numbers with respect to S. Matchings with low crossing numbers were originally introduced in the late 1980s in the seminal works of Welzl [29, 30] and Chazelle-Welzl [7], who showed that any set system (X, S) with bounded dual VC-dimension d has a matching with crossing number O |X| 1-1/d, which is optimal. Low-crossing matchings and spanning paths have found several applications outside of their initial realm of computational geometry, including algorithmic graph theory, model checking, and game theory. In many of these applications, |S| is near-linear in |X|, which motivated the search for an improved construction for this regime. However, the proposed new algorithms provided only average-case bounds or sub-optimal crossing number guarantees for d ≥ 2 [5, 12]. We propose a new quasi-uniform sampling based framework. This allows u

ALT Methods for learning continuous representations, such as latent manifolds, are fundamental and ubiquitous in modern machine learning. Yet many geometric objects combine continuous shape information with discrete combinatorial structure. This combination presents a fundamental challenge for representation learning because small geometric perturbations can induce abrupt changes in the underlying discrete representation. As a result, the smoothness assumptions that make continuous representations effective no longer hold. Polygons provide a canonical example. Their vertex locations vary continuously, but infinitesimal changes in geometry can dramatically alter the associated visibility graph. Existing methods address the inverse mapping from visibility graphs to polygon geometry using vertex-, triangulation-, or signed-distance-function (SDF)-based representations. Vertex- and triangulation-based approaches construct polygons through explicit geometric operations. However, they are less e

ALT Topological deep learning (TDL) architectures are typically evaluated on synthetic complex pairs that differ in a target invariant. Yet, whether a model recovers that invariant or an artifact of the chosen discretization is seldom audited. To examine this, we design and test pairs of complexes that look identical to standard homological and local message-passing tests, have the same Hasse graphs, yet differ in the target invariant. We study two beyond-homology regimes: nonAbelian fundamental-group structure and homotopy-matched orientability. For the former, we construct genus-2 pairs that match homology, cell statistics, local incidence profiles, and rank-colored Hasse 1-WL behavior while differing in their fundamental groups. For the latter, we evaluate punctured torus-Klein bottle pairs and show that distance, boundary, cycle, and spectral signals can confound apparent orientability detection, motivating stronger matched controls. Under the tested settings, subcomplex-lifted archite

ALT The Mapper algorithm is a popular graphical tool for data visualization and exploration in topological data analysis (TDA). It takes as input a data set X and returns a graph that aims to capture the underlying topological features of these data. The Mapper algorithm has several parameters that need to be specified by the user: a filter function f:X→ Y where X is often a point cloud data set in ℝⁿ and Y is the reference space that is often a lower dimensional Euclidean space, a cover of f(X), and a clustering algorithm that is applied to the pre-image of each element in the cover. In this paper, we consider the following question: What graphs can occur as the output of the Mapper algorithm? It is known that when Y=ℝ³, any graph can be a Mapper graph. In this work, we focus on a more practical case where the filter function is f:ℝ²→ℝ. We consider two different scenarios. In the first scenario, we fix the parameters of the Mapper algorithm, but vary the data. This way we characterize exa

ALT We study lattice-based collective construction of a target polyomino on the integer grid, where robots place unit square blocks subject to two physical constraints: the partial structure must remain connected at all times, and no placement may create an unfillable one-cell gap. We present a wavefront sweep algorithm that computes a dependency structure satisfying the local conditions required for safe assembly. Given a list of n cells sorted lexicographically by coordinates, the orientation can be computed in O(n) time using O(n) auxiliary space.

ALT We address the Diverse Traveling Salesman Problem (D-TSP) that seeks a set of k distinct TSP tours. Each selected tour must not exceed a prescribed multiple of the optimal tour length, while the maximum pairwise Jaccard similarity within the selected set is minimized. This formulation is important for applications requiring both solution quality and fault tolerance, such as logistics planning, robotics, and strategic patrolling. We propose a novel hybrid framework that decomposes D-TSP into a sampling stage and a selection stage. The selection stage is a max-min dispersion problem, for which any approximation better than a factor of two is NP-hard; we therefore focus on the sampling stage. Our contributions are both theoretical and empirical. Theoretically, we give two end-to-end guarantees for the optimal sampling distribution, from two perspectives: including an optimal set in the sampled pool, or having at least k mutually distant tours in the pool. The second reduces the number of

ALT We extend the Bochner-Weitzenböck decomposition to cellular sheaf Laplacians, splitting it into a positive semidefinite term, the Bochner sheaf Laplacian, and a block diagonal term, the Forman curvature. We show that the Bochner Laplacians form a class of cellular sheaves that extends both connection and matrix-weighted Laplacians, and generalizes signed graphs to d dimensions. We give a holonomy characterization of their kernel, prove the related Cheeger inequalities, and attach to them a random walk that generalizes the Gremban expansion. For the Forman term, we prove a discrete Bochner theorem, which bounds the first cohomology of a cellular sheaf with nonnegative curvature, and we read the whole decomposition as an opinion-dynamics model. We then apply this machinery to Sheaf Neural Networks, whose learnt Laplacian is otherwise unobserved. The Bochner interpretation yields a node-level conviction score that acts as an operational importance measure under frozen-model interventions,

ALT This study compares ten digital 3D acquisition techniques applied to violin family instrument plates, assessing their accuracy and relevance for scientific and cultural heritage applications. Evaluated methods include two photogrammetric workflows, medical and industrial computed tomography, terrestrial laser scanning, two structured-light configurations (blue light and infrared), and three consumer-grade iPad Pro approaches: TrueDepth scanning and LiDAR using two different applications. The methods were applied to five historical instruments from the "Musical Instruments Museum" (Brussels) and the "Musée de la Musique" (Paris). Since no geometric ground truth is available, accuracy is assessed through systematic pairwise point-to-plane comparisons of the resulting point clouds. These comparisons are jointly analysed to estimate the intrinsic error of each technique (i.e. the expected discrepancy between the model and the true but unknown geometry) without designating any technique as

ALT In the classical necklace splitting problem, beads of different colors lie on a line, and the goal is to divide them among k agents using as few cuts as possible so that every agent receives the same number of beads of each color. We study the planar analog in which a cut is a full straight line and the objective is minimizing the number of lines: m points colored red and blue must be separated by straight-line cuts into regions that can be allocated to k agents so that each agent receives the same number of points of each color. Projection to a line gives 2(k-1) cuts, and k-1 are sometimes necessary; we give algorithms, static and dynamic, that provably close part of this gap. We develop several approaches that capitalize on the extra degree of freedom: a “star” search that produces solutions with as few as ⌈ᵏ⁄₂⌉ cuts and never more than k whenever a fair contiguous circular partition exists, with further guarantees for evenly spaced input, and a general algorithm that produces at mos

ALT We consider the problem of calculating the volume of the union of translates of a strictly convex body K⊂ℝᵈ. When K is a ball, it is possible to simplify the inclusion-exclusion formula by summing over only a small subset of all terms. This subset corresponds to intersecting cells in the Voronoi diagram of the ball centers. We prove that the same simplification is valid for every strictly convex K if and only if d≤ 2. Moreover, in three dimensions and when K is C⁴, we use the Fubini-Pick affine invariant to show that the topological identity underlying this technique holds if and only if K is an ellipsoid.