cs.CG

Papers

• Faster Goal-Oriented Shortest Path Search for Bulk and Incremental Detailed Routing (2026)
  Markus Ahrens et al.
  6.81
• The Power of Recursive Embeddings for $\ell_p$ Metrics (2025)
  Robert Krauthgamer et al.
  5.24
• Fast Cross-Polytope Locality-Sensitive Hashing (2016)
  Christopher Kennedy et al.
  —
• Local Search Yields a PTAS for k-Means in Doubling Metrics (2017)
  Zachary Friggstad et al.
  —
• Local search yields approximation schemes for k-means and k-median in Euclidean and minor-free metrics (2016)
  Vincent Cohen-Addad and Philip N. Klein and Claire Mathieu
  —
• Simultaneous Nearest Neighbor Search (2016)
  Piotr Indyk et al.
  —
• Dynamic Planar Voronoi Diagrams for General Distance Functions and their Algorithmic Applications (2020)
  Haim Kaplan et al.
  —
• Lower Bounds on Time-Space Trade-Offs for Approximate Near Neighbors (2016)
  Alexandr Andoni et al.
  —
• Geometric Near-neighbor Access Tree (GNAT) revisited (2016)
  Kimmo Fredriksson
  —
• An Optimal Algorithm for Range Search on Multidimensional Points (2016)
  T. Hema and K.S. Easwarakumar
  —
• Local Search for Max-Sum Diversification (2016)
  Alfonso Cevallos et al.
  —
• Optimal Hashing-based Time-Space Trade-offs for Approximate Near Neighbors (2019)
  Alexandr Andoni and Thijs Laarhoven and Ilya Razenshteyn and Erik Waingarten
  —
• Large Margin Nearest Neighbor Classification using Curved Mahalanobis Distances (2016)
  Frank Nielsen and Boris Muzellec and Richard Nock
  —
• A Refined Analysis of LSH for Well-dispersed Data Points (2016)
  Wenlong Mou et al.
  —
• Hypercube LSH for approximate near neighbors (2017)
  Thijs Laarhoven
  —
• Locality-sensitive hashing of curves (2017)
  Anne Driemel and Francesco Silvestri
  —
• An $O(n\log n)$-Time Algorithm for the k-Center Problem in Trees (2018)
  Haitao Wang and Jingru Zhang
  —
• Approximate nearest neighbors search without false negatives for $l_2$ for $c>\sqrt{\log\log{n}}$ (2017)
  Piotr Sankowski and Piotr Wygocki
  —
• A Fast Approximation Scheme for Low-Dimensional $k$-Means (2017)
  Vincent Cohen-Addad
  —
• Graph-based time-space trade-offs for approximate near neighbors (2019)
  Thijs Laarhoven
  —
• Onion Curve: A Space Filling Curve with Near-Optimal Clustering (2018)
  Pan Xu et al.
  —
• Approximate Nearest Neighbor Search in High Dimensions (2018)
  Alexandr Andoni et al.
  —
• Approximate Nearest Neighbors in Limited Space (2018)
  Piotr Indyk and Tal Wagner
  —
• An Algorithm for Reducing Approximate Nearest Neighbor to Approximate Near Neighbor with O(logn) Query Time (2018)
  Hengzhao Ma et al.
  —
• An Efficient Data Retrieval Parallel Reeb Graph Algorithm (2020)
  Mustafa Hajij et al.
  —
• Nearest neighbor decoding for Tardos fingerprinting codes (2019)
  Thijs Laarhoven
  —
• PUFFINN: Parameterless and Universally Fast FInding of Nearest Neighbors (2019)
  Martin Aum\"uller et al.
  —
• Polytopes, lattices, and spherical codes for the nearest neighbor problem (2020)
  Thijs Laarhoven
  —
• Optimal Joins using Compact Data Structures (2020)
  Gonzalo Navarro and Juan L. Reutter and Javiel Rojas-Ledesma
  —
• Coresets for the Nearest-Neighbor Rule (2020)
  Alejandro Flores-Velazco et al.
  —
• On Metric DBSCAN with Low Doubling Dimension (2020)
  Hu Ding et al.
  —
• Optimizing Geometry Compression using Quantum Annealing (2020)
  Sebastian Feld et al.
  —
• Locality Sensitive Hashing for Set-Queries, Motivated by Group Recommendations (2020)
  Haim Kaplan et al.
  —
• A Practical Index Structure Supporting Fr\'echet Proximity Queries Among Trajectories (2021)
  Joachim Gudmundsson et al.
  —
• The nearest-colattice algorithm (2020)
  Thomas Espitau et al.
  —
• New Data Structures for Orthogonal Range Reporting and Range Minima Queries (2020)
  Yakov Nekrich
  —
• Locality Sensitive Hashing for Efficient Similar Polygon Retrieval (2021)
  Haim Kaplan et al.
  —
• A Tail Estimate with Exponential Decay for the Randomized Incremental Construction of Search Structures (2025)
  Joachim Gudmundsson et al.
  —
• Preprocessing power weighted shortest path data using a s-Well Separated Pair Decomposition (2021)
  Gurpreet S. Kalsi and Steven B. Damelin
  —
• Near Neighbor Search via Efficient Average Distortion Embeddings (2021)
  Deepanshu Kush et al.
  —
• Tight Bounds for Approximate Near Neighbor Searching for Time Series under the Fr\'echet Distance (2021)
  Karl Bringmann et al.
  —
• Online Search for a Hyperplane in High-Dimensional Euclidean Space (2021)
  Antonios Antoniadis et al.
  —
• Fine-Grained Complexity Theory: Conditional Lower Bounds for Computational Geometry (2021)
  Karl Bringmann
  —
• Parallel Nearest Neighbors in Low Dimensions with Batch Updates (2021)
  Magdalen Dobson and Guy Blelloch
  —
• Optimal Window Queries on Line Segments using the Trapezoidal Search DAG (2024)
  Milutin Brankovic et al.
  —
• Embeddings and labeling schemes for A* (2021)
  Talya Eden et al.
  —
• A new near-linear time algorithm for k-nearest neighbor search using a compressed cover tree (2024)
  Yury Elkin et al.
  —
• Point Enclosure Problem for Homothetic Polygons (2023)
  Waseem Akram and Sanjeev Saxena
  —
• Fast Single-Core K-Nearest Neighbor Graph Computation (2021)
  Dan Kluser et al.
  —
• Paired compressed cover trees guarantee a near linear parametrized complexity for all $k$-nearest neighbors search in an arbitrary metric space (2022)
  Yury Elkin et al.
  —