3 papers
cs.DS2026
The Greedy Binary Search Tree is Non-trivially Competitive
Yuhao Guo, Seth Pettie, Daniel Skora +1
We prove that the binary search tree is -competitive. It is widely conjectured that is -competitive, but before…
cs.CG2025
The Squishy Grid Problem
Zixi Cai, Kuowen Chen, Shengquan Du +3
In this paper we consider the problem of approximating Euclidean distances by the infinite integer grid graph. Although the topology of the graph is fixed, we have control over the…
cs.CG2023
Delaunay Triangulations in the Hilbert Metric
Auguste Gezalyan, Soo Kim, Carlos Lopez +3
The Hilbert metric is a distance function defined for points lying within the interior of a convex body. It arises in the analysis and processing of convex bodies, machine learning…