Theory & Algorithms · Computer Science & AI
Computational Geometry
The newest papers in Computational Geometry that ReadSearch has read, newest first. Each links to its own page, with its authors, date, where it was published and the original.
90 papers, from 7 September 2026 to 4 November 2026: 90 arXiv preprints.
Get the few papers worth your time in Computational Geometry every morning.
Follow Computational Geometry and ReadSearch reads its new papers each day, then brings you the few worth reading, each with its key finding in a sentence.
Newest papers, page 2
Dimension Reduction and Coresets for Min-Sum $k$-Clustering
The min-sum $k$-clustering problem asks to partition an input of $n$ points into $k$ clusters so as to minimize the total pairwise distance within clusters.DUET4D: Self-Corrective Coupled Guidance for Sparse-View 4D Reconstruction
Sparse-view 4D reconstruction is highly under-constrained when only a few cameras are available.Query Complexity of Learning Axis-Aligned Partitions
This work establishes the query complexity of learning high-dimensional boxes in the exact query learning setting.Tight Coreset Bounds for Euclidean $(k,z)$-Clustering
We study the optimal coreset size for Euclidean $(k,z)$-clustering, where $z\ge1$ is fixed.A Linear Lower Bound for Convex Body Chasing in Every $\ell_p$ Norm
We establish an $Ω(d)$ lower bound on the competitive ratio of convex body chasing in $\mathbb{R}^d$ with $\ell_p$ movement costs for any $p \in [1, \infty)$.Low-Crossing Spanning Paths via Quasi-Uniform Sampling and their Applications
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…Coresets for $k$-Means: When Does Uniform Sampling Suffice?
Data summarization techniques, such as coresets, are essential for scaling clustering algorithms to massive datasets.VisFlow: Interpretable Flow Matching for Visibility Reconstruction, Characterization, and Recognition
Methods for learning continuous representations, such as latent manifolds, are fundamental and ubiquitous in modern machine learning.How to Walk a Dog in Parallel: On Parallel Computation of the Discrete Frechet Distance
The Fréchet distance (also known as the dog-leash distance) is a well-studied and prevalent distance measure for polygonal curves.CyberHull: Deterministic Malicious URL Isolation via Convex Hull
The emergence of increasingly sophisticated and evasion-resistant phishing attack strategies represents a significant threat to modern cybersecurity, particularly in cyber-physical systems and…Splitting Planar Necklaces with Few Straight Cuts
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…A Bochner Weitzenböck Decomposition for Cellular Sheaf Laplacians, Curvature and Neural Sheaf Diffusion
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…Two $\operatorname{ReLU}$ Layers is All You Need
We prove that every $\operatorname{ReLU}$ network can be exactly simulated by a $\operatorname{ReLU}$ network with two hidden layers.The Optimal Sampler for Diverse TSP Solutions: Characterization, Limits, and Learning
We address the Diverse Traveling Salesman Problem (D-TSP) that seeks a set of $k$ distinct TSP tours.Near-Linear Time Maximum Clique in Circular Arc Graphs
We present a near-linear time algorithm to find a maximum clique in circular arc graphs, the intersection graphs of arcs on the circumference of a circle, answering a 30-year-old open question posed…Navigable Graphs for Low-Dimensional Hyperbolic Spaces
A directed graph on a point set $P$ in a metric space $(X,d)$ is navigable if for every ordered pair of distinct points $s,t \in P$, $s$ has an out-neighbor $v$ with $d(v,t) < d(s,t)$, so greedy…Online geometric matching and segments block points
Given a sequence of online points in general position in the plane, the geometric matching problem asks to match as many points as possible, subject to segment crossing constraints.Boundary Detection for High-Dimensional Point Clouds
We introduce two new methods for boundary detection in high-dimensional point cloud data, intended to work in situations with non-uniform density, high ambient dimension, and substantial noise.Geometric Hashing in MPC with Applications to Clustering and Stochastic Embeddings
In this paper we study consistent hashing (a.k.a. sparse partitions) for doubling metrics in the Massively Parallel Computation (MPC) model.Restless Guards: Robust Guarding of Polyominoes
The art gallery problem is a fundamental problem whose practical applications have inspired numerous variants.