Exact count of curve types by word length found
Formula uses a finite sum of totient-like functions plus a small periodic correction, ending a conjecture from 2016.
· “Exact curve counting of given word length on the once-punctured torus”
cs.CG
Computational Geometry
Roughly includes material in ACM Subject Classes I.3.5 and F.2.2.
sort pith recommended most recent
O~(n^{14/15}) approximation for minimum dilation trees
Polynomial-time algorithm resolves a 1996 open problem on spanning tree dilation.
· “A Sublinear Approximation Algorithm for Minimum Dilation Trees in the Plane”
Longest-edge bisection can degenerate in 3D and 4D
Open set of 4-simplices degenerate; random high-dimensional simplices almost surely degenerate.
· “Degenerating orbits of the Longest Edge Bisection process”
Delaunay stretch factor drops to 1.65
A potential-function proof narrows the gap to the known 1.5932 lower bound more than sevenfold.
· “The Stretch Factor of Planar Delaunay Triangulations Is Less Than 1.65”
First sub-4 approximation for fair k-means
New algorithm exploits LP integrality gap and shifted instances to reach 3.8427+O(ε), improving previous 5+O(ε).
First explicit mono-monostatic polyhedron constructed and certified
Exact rational arithmetic verifies one stable, one unstable equilibrium; solves a long-standing geometric existence question.
Structured model yields uniform power for persistence diagram testing
By translating latent template separation into population mean signal, the framework enables two-sample tests with matching minimax rates.
Tight quantum bounds for graph persistence stats
An identity turns nonlinear barcode summaries into easy averages, yielding optimal query complexity for quantum and classical algorithms.
· “Quantum Query Complexity of Persistence Statistics in Graph Zigzags”
First FPTAS for CDTW distance on algebraic curves
Combins Pontryagin's principle, quadratic approximation, and Cebysev interpolation to achieve polynomial time.
· “Approximating CDTW Distance of Piecewise Algebraic Curves”
Gaussian splats become 3D meshes in under a minute
A feed-forward transformer matches slow optimization methods on DTU and Tanks and Temples.
Point sets with (p,q)-splitting condition require bounded flats
Helly-type theorem extends to flats of any dimension, using VC-dimension to control splitting.
A fractal curve makes 2-Wasserstein comparisons up to 2000x faster
The SK-Wasserstein distance sorts persistence-diagram codes instead of solving planar matchings, staying faithful to W2 in tests.
Minimal line set yields O(log n + m) k-visibility queries
A new cell decomposition using only horizon lines and hinge lines achieves optimal query time with O(n⁴) storage for any visibility depth k.
Albertson’s Conjecture proven up to r=26
Every graph with chromatic number at most 26 has crossing number at least that of the corresponding complete graph.
One point is the optimal insertion spot for any quadrilateral
It is independent of the corner values and Möbius-covariant, so mesh algorithms can use it without knowing the data.
Fréchet simplification on a query line in O(k^2 log^3 n) time
A near-linear-size structure returns an exact optimal at-most-k-vertex curve on any query line in polylogarithmic time.
Reuleaux polygons lift universal cover bound to 0.8344
Using constant-width test sets and a certified 60 MB computation improves the 1914 problem's best known lower bound by 0.14%.
· “Curves of constant width and Lebesgue's covering problem”
Curved capacitive fabric infers shape from proximity
Multi-view feedforward model aggregates non-planar capacitive fields for robot near-field 3D awareness.
· “Proximity3D: Shape from Capacitive Proximity on Sensing Manifold”
Three exceptional 4D polytopes fail the all-net test
Overlapping ridge unfoldings for the 24-cell, 120-cell and 600-cell complete the classification of regular polytopes.
One framework designs kirigami for 2D and 3D morphing
A companion inertia law fixes the compact rectangle's aspect ratio straight from the target shape.
· “A unified geometric design framework for kirigami structures”
Topology data makes spline level-set extraction 10x faster
A combinatorial map for hierarchical spline meshes gives watertight surfaces, up to 50x fewer evaluations.
An elastic kernel makes triangle splats converge to cleaner surfaces
A single kernel change — a boundary value that adapts to softness — improves both shape and novel-view synthesis.
Online hyperplane search value is computable in any dimension
N-COMP theorem proves the minimax competitive ratio C*_D can be approximated to any precision, despite an infinite-dimensional Bellman…
The optimal shoreline-search ratio is provably computable
At any requested precision, a terminating algorithm certifies the optimal value inside an interval of that width.
ℓ₀ isoperimetry gets factor-n boost
Mass-transport proof improves coordinate hit-and-run mixing bound by a factor of n.
· “Improved ell₀-Isoperimetry for Convex Bodies via Mass Transport”
Phase diagram for optimal memory in sequential networks
Explicit scaling transitions determine when to use short or long memory near power one.
Three voters beat any challenger in planar distance votes
A new piercing result shows three chosen peers defeat every rival under Manhattan and maximum-coordinate metrics.
· “Condorcet-Winning Sets and Peer Selection in Planar Metric Elections”
Barcode approximation hits a phase transition at log n doubling dimension
Linear-time algorithms when dimension grows slowly; matrix-rank hardness otherwise.
Lunar EMST expected cost scales as constant times √n
New generalization of minimum spanning trees to colored points proves asymptotic growth, extending a classic 1959 result.
· “Lunar Generalizations of the Euclidean Minimum Spanning Tree in the Plane and their Expected Costs”
Lines on a hyperboloid yield quadratic Voronoi complexity
Nearest and farthest diagrams for a ruling of a regulus achieve Θ(n²) vertices, with an O(n²) enumeration algorithm.
· “Quadratic Complexity of Voronoi Diagrams in mathbb{R}³ for Lines in a Single Ruling of a Regulus”
CLIPPER cuts planning time 28× with near-optimal coverage
A new method enables rapid, replayable comparison of spatial coverage plans under changing municipal policies.
· “CLIPPER: Replayable Shortlisted Optimization for Repeated Spatial Coverage Planning”
Canopies generalize vines by tracking simplex pairs instead of diagram points
Different pair choices on the same filtered complex yield homeomorphic canopies, allowing vines with multiplicity and monodromy analysis.
· “Canopies: A Generalization of Vines and Vineyards for Parameterized Persistence”
Monotiles create deployable kirigami across all symmetries
Explicit constructions show single-tile patterns support every wallpaper group plus quasicrystal and polykite variants.
Distance metric decides when triangle badness ranks match
Two of three triangle-quality measures stay consistent across most datasets; the third measures something else.
· “An Approach to Study the Structural Consistency of Triangle Badness Functions and Distance Metrics”
Hexagonal-lattice circles beat eight rivals on convex-region coverage
IQPD reports top coverage and node-utilization rates, with runtime second only to VGSOK.
This paper proves that every 2-connected apex cubic graph admits a three-edge-coloring
Every 2-connected apex cubic graph is three-edge-colorable, and this completes the proof of Tutte's three-edge-coloring conjecture.
Near-linear metric decompositions for high-dimensional ℓ∞ and ℓ2
New algorithms split high-dimensional point sets with near-optimal quality in near-linear time.
Connectivity maintenance is points spreading in disguise
Moving sensors to keep them connected costs the same as moving them apart, up to a known factor, on lines and cycles.
Sorting with lies costs Θ(n log n + nk) queries
Even when the oracle may return k false counterexamples, a deterministic learner needs no prior knowledge of k.
One GNN predicts tissue deformation and force at 100 Hz
Calibrated simulation data give sub-millimeter deformation at 100 Hz, and force errors track calibration fit.
· “Generalizing Soft Tissue Deformation and Force Prediction Across Material Stiffness and Geometry”
All partial Wasserstein costs on the line in near-linear time
A shift-decomposition plus FFT turns the p-Wasserstein partial-transport profile into an O(p n log^2 n) computation.
· “Computing All Optimal Partial p-Wasserstein Matchings on the Line”
Ridge-front sweep recovers 4D mesh boundaries
A cavity-based advancing-front method turns over 99% of missing boundary tetrahedra into pentatope faces, reaching 100% on simple domains.
· “An advancing-ridge approach for recovering boundary (d-1)-simplices in d-dimensional meshes”
Edge-by-edge odds for Jacobi sets under Gaussian uncertainty
Analytic per-edge probabilities match 10,000-run Monte Carlo within 1.8 percent, no sampling.
Three trees give constant-stretch covers for every H-minor-free graph
A dimension-to-cover conversion matches the known lower bound for toroidal grids.
· “Three trees suffice for a constant stretch in minor-free graphs”
Unions of convex sets: piercing number pinned to p−q+1 plus small error
For logarithmic q, the extra piercing points are few; for unions of s intervals, the additive term sits between s and 2s+1.
· “New Quantitative Bounds for the (p,q)-Theorem for Unions of Convex Sets”
Monotone edges guarantee meshes keep a field's critical points
A proof plus edge-refinement lets implicit 2D fields yield Morse–Smale complexes without dense uniform sampling.
· “Topology-Preserving Meshing of Implicit Scalar Fields via Monotonicity Constraints”
Worst-case circle treasure hunt solved exactly
The hardest k-treasure layout is a 'double then even' family, giving exact minimax times and sharp search bounds.
· “Going in Circles: Collaborative Multi-Robot Treasure Hunting”
Ball Mapper overlaps become a joint probability law
A new probabilistic reading lets Ball Mapper graphs of different sizes be compared by optimal transport.
GW clustering matches k-means' optimal compression rate
Proves geometry-preserving clustering hits classical quantization's n^{-1/d} rate.
· “Gromov-Wasserstein Quantization and Clustering: Structure, Rates, and Algorithms”
For convex points, greedy triangulation is an 18-spanner
The new proof shrinks the old 11,739 constant to an explicit bound below 17.814.
· “On the Spanning Ratio of the Greedy Triangulation for Convex Point Sets”
Convex-obstacle path queries answered with near-linear preprocessing
A sketch of the domain plus interval successors yields (1+eps) stretch with only a small additive term.
· “Two-point Approximate Shortest Path Queries among Convex Polygonal Obstacles in the Plane”
Metric graph length capped by diameter
The bound is tight, and equality holds exactly for the Medusa graphs.
Hamming cube 2-hop spanners need (2^d)^{1+Ω(1/t)} edges
The bound survives Steiner vertices and follows from a direct reduction to locality-sensitive hashing.
· “Towards Lower Bounds for Geometric Spanners in High Dimension”
Mapping solids: target shape becomes part of the optimization
One energy, three self-adjusting targets: fixed ellipsoid, adaptive ellipsoid, and a sea-buffered free boundary.
· “Adaptive Volumetric Parameterization of Simply Connected 3-Manifolds with Applications”
Packets find routes amid convex obstacles with (7+ε) log h stretch
Compact routing tables from a recursive splitter construction; headers stay at 2 log n bits after O(n^2 log n) preprocessing.
· “A Recursive Algorithm for Routing amid Convex Polygonal Obstacles”
Smoothing min and max yields a differentiable signed distance
Closed-form and GPU-ready metric for convex polyhedra targets the kinks that make robot controllers chatter.
· “H\"older Signed Distance: A Differentiable, Signed, Parallelizable Metric for Robotics”
The kissing number sets the cost of learning hidden point sets
In any normed space, 2nκ queries suffice and some domains force Ω(nκ); the sphere takes O(1), the ball exponential.
Exact trait-induced merge trees from a linear-size graph
Vertex-sampled approximations miss zero-valued features; this graph method is exact and runs in linear time.
· “Exact Computation of Trait-induced Merge Trees for Bivariate Fields”
One matrix update tracks every bar in a Conley-Morse barcode
Split, merge, and transposition edits keep the barcode current, replacing repeated zigzag persistence runs.
· “Computing Conley-Morse Persistence Barcode Efficiently by Updating Matrix Decompositions”
Non-crossing Hamiltonian paths are NP-complete in non-planar graphs
The hardness comes from forbidding crossings on the path itself, not from planarity gadgets.
· “NP-Hardness of Non-Crossing Hamiltonian Path and Cycle in Non-Planar Graphs”
Interaction of point clouds reduces to one forced integer curve
The overlap's Euler characteristic is the unique symmetric, stable interaction profile, computable in near-optimal time.
Bend-distance sector cycles are bounded by holes
A precise endpoint fix turns grid bend distance into a Reeb multigraph; two-port treewidth on disks is exactly 3.
First sparse non-crossing spanners for hyperbolic surfaces
An O(g^4 log g) decomposition yields sparse (1+ε)-spanners linear in genus, matching Euclidean edge counts.
· “Fast Thick-Thin Decomposition for Sparse Spanners on Hyperbolic Surfaces”
Pseudoinverse metric exceeds 1-WL and improves neuron typing
A closed-form matrix inverse gives a training-free graph signature that beats standard message passing on 3D neuron data.
129 seconds: H4 of the Greene sphere is zero
A new algorithm skips 6.4 trillion cubes, making discrete homology faster than simplicial on noisy data.
· “Discrete homology computations by reduction to zero differentials”
Dense geometric graphs get near-linear BFS
New decision procedures let reachability and bottleneck paths run fast in dense antenna and terrain visibility graphs.
· “Efficient Algorithms for the Bottleneck Path Problem in Geometric Graphs”
Self-aligning lattice modules snap together into structures
The module's geometry handles grip, alignment, and connection; robots just place the parts.
Shallow-light trees beat the 2/ε barrier in every Euclidean space
The 1993 2/ε claim is beaten in every dimension; in the plane lightness drops to 0.987/ε.
Link barcode pairs deaths with births across dimensions
A small twist on the persistence reduction adds cross-dimensional links—stably and in near-linear time for graphs.
Closed-cycle connectivity fixed in O(n) with minimal moves
The same algorithm gives a lexicographically optimal solution and covers closed-border barrier coverage.
· “Algorithms for Connectivity Maintenance and Barrier Coverage on a Closed Cycle”
Exact Steiner-point tree algorithm ignores the explosion of k
A deterministic n^{O(n)} method separates branching structure from subdivision points in any fixed L_p metric.
Five convexity invariants collapse into one
VC, strong Helly, Carathéodory, comatching, and strong Radon bounds coincide—unlocking linear Tverberg growth.
· “Strong invariants and Tverberg numbers in convexity spaces”
One search counts every triangle-maximal pseudoline arrangement to n=27
Proves the enumeration is complete, recovers each arrangement's symmetry group, and pins the final open case to n=91
· “Enumeration and Classification of Triangle-Maximal Pseudoline Arrangements”
Coverage beats 1-1/e for disks
LP rounding plus a packing prelude yields strictly better than 1-1/e in unweighted and budgeted settings.
Smooth distance queries match ANN speed and space
A (1+ε)-accurate distance with gradient now costs the same as approximate nearest-neighbor search.
Hilbert metric yields optimal polytope membership queries
Walking the query ray through Macbeath ellipsoids matches optimal space and speeds successive queries.
UGC locks three geometric stabbing problems at tight thresholds
Cubes and d-intervals hit factor d; interval stabbing hits e/(e-1), matching the best algorithms.
ECT yields isometry-invariant shape distances with no cutoff
Centering at an ECT Steiner point recovers perimeter and beats raw ECT on noisy or misaligned data
· “The Euler Characteristic Transform from a Convex Geometric Perspective”
Reordering siblings cuts tree drawing width ~20%
Finding the narrowest tidy layout is NP-hard, yet a fast heuristic stays near optimal
One adaptive sampler sizes streaming unions of sets
Linear-in-dimension updates for box volumes, plus free algorithms for coverage and DNF counting