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.

ALT Given a finite planar point set X={x₁,…,x_n}, let a₁<a₂< ⋯ < a_s denote the s ≤ n choose 2 different (Euclidean) distances between points in X. The aim is to retain as many of the points as possible such that certain imposed inter-pair distances are avoided. For example, we show that: (A) Given a set X of n points in the plane, an independent set of size 0.2293 n in the unit distance graph determined by X can be found in O(n²) time. For any fixed k ∈ N there exists a constant c_k>0 such that for any set X of n points in the plane, and set D of size k, there exists a subset X' ⊆ X of size |X'|≥ c_k |X| in which no pair of points is at some distance in D (we say that X' avoids distances in D). Such a set can be found efficiently. (B) (i) There is a subset of X of size n/2 that avoids the maximum distance; this bound cannot be improved. (ii) There is a subset of X of size 8n/47 that avoids both the minimum and maximum distance; on the other hand, there exists X such that at most 5n/16 poi

ALT The shortest vector problem (SVP) under the infinity norm (ℓ∞-norm) is an important lattice problem with applications in lattice-based cryptography. In particular, the security analysis of the post-quantum signature standard ML-DSA highlights the importance of finding short solutions satisfying infinity-norm constraints, rather than only Euclidean norm bounds. However, most existing lattice reduction algorithms are developed for the Euclidean norm, while dedicated studies under the infinity norm remain limited. In this work, we focus on rank-two lattices in ℝⁿ and introduce a new notion of reduced basis under the infinity norm. Based on this definition, we propose an efficient lattice basis reduction algorithm that performs a multi-dimensional analogue of Euclidean division using a dominant coordinate of the basis vectors. Each non-terminal iteration guarantees a factor-two decrease of the maximum infinity norm of the basis vectors. We prove that the algorithm terminates and achieves a

ALT We study the geometric set cover problems of covering and partitioning a polygon into a minimum number of triangles. While the decision version of the covering problem is known to be APX-hard and ∃ℝ-complete (even for polygons without holes and vertices in general position), the computational complexity of partitioning a simple polygon into a minimum number of triangles is open. Our main result refutes a 40 year old conjecture by Asano, Asano, and Pinter stating that the triangle vertices of a minimum partition lie on intersection points of special lines, which are iteratively generated by the polygon vertices and the intersection points. In particular, we show that there exist polygons where all minimum triangle partitions need Steiner points with irrational coordinates. This indicates that the problem might be more complex than previously expected. Complementarily, we provide a simple constant factor approximation to compute a minimum triangle partition of a given polygon (possibly w

ALT We present compact SAT encodings and certifying exact solvers for boxicity and cubicity. The boxicity of a graph is the minimum dimension in which it is the intersection graph of axis-aligned boxes; cubicity is defined analogously using unit cubes. Grid-based formulations face a geometric discretization bottleneck, growing rapidly with the target dimension. We avoid this bottleneck by encoding the total order of interval endpoints in each coordinate. For an n-vertex graph and target dimension d, our boxicity encoding uses O(n²d) variables and O(n³d) clauses, both linear in d. Requiring the left- and right-endpoint orders to agree yields a cubicity encoding of the same asymptotic size. Satisfying models are decoded into independently checked geometric representations, while unsatisfiable instances used as lower-bound evidence carry mechanically verified DRAT certificates. In a controlled evaluation with 186 trials per encoding on standard and structured graph families, the order encodin

ALT 3D Voronoi diagrams provide a powerful mathematical framework for representing volumetric functions and geometry with applications to Materials Science, Biology, Simulation and Astrophysics. However, accurately resolving fine structures often requires millions of cells, imposing severe computational and memory constraints. Traditional mesh decimation or point cloud simplification techniques fail to account for the effects re-meshing has on neighbouring cells. In this work, we formalize the Voronoi reduction problem and propose a greedy edge-collapsing algorithm on the dual Delaunay tetrahedralisation that accounts for changes in the local geometry. Further, we demonstrate a novel volumetric error approximation technique that models convex cell intersections as truncated prismatoids, circumventing computationally prohibitive exact volume calculations and enabling massive GPU parallelization. Evaluations across Synthetic, Medicine and Material Science data demonstrate that VoroDuce decim

ALT The art gallery problem is a fundamental problem whose practical applications have inspired numerous variants. In this work, we investigate a setting in which full coverage of the gallery shall be ensured despite locational uncertainty of the guards. We study this problem for polyominoes under rectangular visibility, where a k-restless guard assigned to a cell may move to any cell within distance at most k. While all polyominoes are guardable for k∈{0, 1}, the same is not true for all k≥ 2. However, for a given polyomino P and integer k, we present an algorithm that identifies a k-restless guard set of P in polynomial time, or decides that no such set exists. For the cases k∈{0,1}, where k-restless guard sets always exist, we provide tight worst-case bounds on the number of k-restless guards that are always sufficient and sometimes necessary to guard a hole-free polyomino with n vertices or m cells. Moreover, we show that computing a minimum guard set is NP-hard. Complementing the hard

ALT We study the problem of testing membership of the origin in the convex hull of n unit vectors in ℝᵐ, seeking a convex combination of norm at most ε or a strict separating hyperplane. The Spherical Triangle Algorithm (STA) uses nearest-point updates on pivot segments. We first establish a conditional O(1/ε) iteration bound from accumulated geometric progress, allowing deeper pivots to compensate for shallow ones. A three-point example shows that ordinary STA can require Θ(ε⁻²) iterations. We show that the same conditional bound holds for STA with Wolfe minimum-norm correction (STA–WMC), provided the averaged geometric progress condition holds for the STA steps taken within this corrected method. We then combine STA, WMC, and the Nemirovski weighted-pivot method (NWP) in a hybrid with unconditional bounds of O(√(log n)/ε) matrix–vector products with the input matrix or its transpose and O(mn√(log n)/ε) arithmetic operations, including corrections. We also give a self-contained derivation

ALT We study multi-robot motion planning in a polygonal environment with polygonal robots. The setting of the problem consists of a polygonal domain W with n vertices and k robots R₁,…,Rₖ translating in W each of which is represented by a polygon of constant complexity. Given a source configuration s and a target configuration t of the robots in W, the goal of the problem is to find a collision-free motion plan from s to t that is shortest with respect to some cost function. We present the first fully polynomial-time approximation schemes (FPTAS) for motion planning with any fixed number k of robots, under the min-sum objective, the min-max objective, and the min-makespan objective. Here, the min-sum variant aims to minimize the total traveling distance of all robots, the min-max variant aims to minimize the maximum traveling distance of a single robot, and the min-makespan variant aims to minimize the total time cost under the assumption that all robots move with a maximum speed 1. The al

ALT Extremal constructions play a central role in the design and analysis of algorithms. Integrality-gap instances expose the limitations of relaxations, while hard configurations reveal structural sources of computational difficulty. Such constructions, however, are still typically discovered through a slow, manual process. This paper investigates how machine learning can accelerate their discovery to support algorithm design and analysis. We build on PatternBoost, a framework alternating local search with generation from a trained transformer, using its Axplorer implementation to investigate three problems: integrality gaps for maximum independent set of rectangles, integrality gaps for stabbing unit squares with axis-parallel lines, and hard instances for recursive guillotine cutting. By exploring candidate representations, local search operations, and surrogate models used to rank candidates before exact verification, we carefully adapt the framework to these combinatorial geometry pro

ALT Quantifying the diversity of a set of objects is a fundamental problem in machine learning and statistics. Mironov and Prokhorenkova (2025) recently showed that three axioms-monotonicity, uniqueness, and continuity-are crucial for a reliable diversity measure and that none of the standard metrics in the literature satisfy all three. They also constructed two measures that do satisfy the axioms, but both are NP-hard to compute, leaving open the question of whether efficient axiomatic diversity measures can exist. We study a Euclidean-restricted version of this question. We introduce Geometric Kernel Diversity (GKD), which associates a radial kernel solid with each point and measures the volume of their union. We show that canonical GKD satisfies all three Mironov-Prokhorenkova axioms on Euclidean-realizable inputs. For canonical GKD, we give exact polynomial-time algorithms in dimensions d ≤ 3. In arbitrary dimensions, we give a randomized algorithm that returns a (1 ± ε)-approximation