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 3
Geometric Graph Representations via Compact SAT Encodings
We present compact SAT encodings and certifying exact solvers for boxicity and cubicity.Geometric Kernel Diversity: An Axiomatic Diversity Measure in Euclidean Space
Quantifying the diversity of a set of objects is a fundamental problem in machine learning and statistics.FPTAS for Polygonal Multi-Robot Motion Planning
We study multi-robot motion planning in a polygonal environment with polygonal robots.On the Parameterized Complexity of Capacitated Stack and Queue Layouts with Colored Edges
Stack and queue layouts are two extensively studied and complementary linear representations of graphs.Ellipsoids from Tangents
This paper presents an algorithm for detecting and fitting multiple ellipsoids in 2D, 3D and higher-dimensional data.The Geometry of Hierarchical Navigation: Accuracy and Query Cost for Point Process Input
Large-scale information retrieval systems, including retrieval-augmented generation (RAG) and recommendation engines, widely use multi-layered hierarchical data structures for ultra-fast approximate…Rubix: Global Correspondence-Free Point Set Alignment through Assignment Geometry
Procrustes-Wasserstein alignment jointly estimates a matching and rotation without supplied correspondences, but alternating minimization can stop at suboptimal solutions.Deterministic Distance Selection in $O(n^{4/3})$ Time
Let $P$ be a set of $n$ points in the plane.Peeling Half the Onion: Embedding $k$-Outerplanar Graphs into $\ell_1$ and Trees with a Polynomial Distortion (in $k$)
Chekuri, Gupta, Newman, Rabinovich, and Sinclair [SODA'03] showed that $k$-outerplanar graphs can be embedded into trees and $\ell_1$ with distortion $2^{O(k)}$.Improved Upper and Lower Bounds for Quantum Convex-Body Volume Estimation
Estimating the volume of a high-dimensional convex body is a fundamental problem in theoretical computer science.Min-Max Uniform Circle Formation by Asynchronous Mobile Robots
Given a set of point robots $\mathcal{R}$ in the Euclidean plane and a target circle $\mathbf C$ enclosing all robot positions, the \textsc{Min-Max Uniform Circle Formation (MMUCF)} problem requires…Locality Sensitive Hashing for p-Exponential Kernels with Applications to Density Estimation
A kernel $k(x,y)$ is LSHable if there exists a locality sensitive hashing scheme $H$ such that $k(x,y)=\Pr_{h\sim H}[h(x)=h(y)]$ for all $x,y$.The sublevel Flood bifiltration: towards scalable 2-parameter persistent homology
Multiparameter persistent homology is a rapidly developing branch of topological data analysis that improves the robustness of single-parameter persistent homology to outliers, while still capturing…Adaptive Bregman Alternating Projections for Feasible Gromov-Wasserstein Learning
The Gromov-Wasserstein (GW) problem compares structured distributions without requiring a shared feature space or known correspondences, but its nonconvex objective and coupled marginal constraints…Budget-Constrained Fault-Tolerant Mutual Visibility for Autonomous Robots under the Mobility Fault Model
We investigate the mutual visibility problem for a swarm of $n\ge3$ autonomous mobile robots under the budget-constrained mobility fault model.Fair Diversity Maximization via Local Search
Diversity maximization is a fundamental optimization problem with applications in machine learning, data summarization, information retrieval, and recommendation systems.When Robots Crash: Optimal Asynchronous Gathering at Weber Meeting Nodes
We study the \textit{optimal gathering} problem over a finite set of designated \textit{meeting nodes} for \textit{asynchronous, anonymous,} and \textit{oblivious} mobile robots on an infinite grid…A differentiability framework for zigzag persistent homology via linear interpolation
Persistent homology can be differentiated and incorporated into learning pipelines, but no analogous framework exists for zigzag persistence, which is needed when the underlying topological…Polynomial-time algorithm for exact $(1,2)$-center problem under continuous Fréchet distance
In this paper, we explore the $(1,2)$-center problem for polygonal curves under continuous Fréchet distance.A Unified Dual Method for Matching Problems
Matching problems are ubiquitous in data science as they enable the alignment of structured objects and distributions.