Showing cs.CGShow all
3 papers · 1 filter
cs.CG2026
Towards Lower Bounds for Geometric Spanners in High Dimension
Robert Krauthgamer, Nir Petruschka
We study the stretch--size tradeoff for geometric spanners in high-dimensional spaces. Our main contribution is a simple proof of a lower bound shown by Har-Peled, Indyk,…
cs.CG2025
The Power of Recursive Embeddings for Metrics
Robert Krauthgamer, Nir Petruschka, Shay Sapir
Metric embedding is a powerful tool used extensively in mathematics and computer science. We devise a new method of using metric embeddings recursively, which turns out to be parti…
cs.CG2025
Lipschitz Decompositions of Finite Metrics
Robert Krauthgamer, Nir Petruschka
Lipschitz decomposition is a useful tool in the design of efficient algorithms involving metric spaces. While many bounds are known for different families of finite metrics, the op…