On Locality-Sensitive Orderings and Their Applications

DOI10.4230/LIPICS.ITCS.2019.21MaRDI QIDQ5090394zbMATH OpenOpenAlexFDO

Authors Timothy M. Chan, Mitchell Jones, Sariel Har-Peled

Publication date 18 July 2022

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2018/10114/pdf/LIPIcs-ITCS-2019-21.pdf/

zbMATH Keywords

approximation algorithmscomputational geometrydata structures

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• On locality-sensitive orderings and their applications
• Labeled nearest neighbor search and metric spanners via locality sensitive orderings
• scientific article; zbMATH DE number 1775450
• Locality-sensitive orderings and applications to reliable spanners
• scientific article; zbMATH DE number 437552

Cites work

• A tight bound on approximating arbitrary metrics by tree metrics
• An effective way to represent quadtrees
• An Optimal Dynamic Spanner for Doubling Metric Spaces
• Approximate closest-point queries in high dimensions
• Approximate nearest neighbor queries revisited
• Approximation schemes for covering and packing problems in image processing and VLSI
• Covering a ball with smaller equal balls in R^n
• Dynamic data structures for approximate Hausdorff distance in the word RAM
• Dynamic Euclidean minimum spanning trees and extrema of binary functions
• Fast Construction of Nets in Low-Dimensional Metrics and Their Applications
• Faster Fully-Dynamic Minimum Spanning Forest
• Fault-tolerant geometric spanners
• From hierarchical partitions to hierarchical covers: optimal fault-tolerant spanners for doubling metrics
• Fully dynamic geometric spanners
• Geometric approximation algorithms
• scientific article; zbMATH DE number 2185613 (Why is no real title available?)
• scientific article; zbMATH DE number 437554 (Why is no real title available?)
• scientific article; zbMATH DE number 5764857 (Why is no real title available?)
• scientific article; zbMATH DE number 1775403 (Why is no real title available?)
• scientific article; zbMATH DE number 1775450 (Why is no real title available?)
• scientific article; zbMATH DE number 2119699 (Why is no real title available?)
• New Doubling Spanners: Better and Simpler
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• Preserving order in a forest in less than logarithmic time and linear space
• Surpassing the information theoretic bound with fusion trees
• The wonderful Walecki construction
• Well-separated pair decomposition in linear time?

Cited in

(5)

• Local Computation Schemes with Partially Ordered Preferences
• Efficient algorithms for local ranking
• Sometimes Reliable Spanners of Almost Linear Size.
• Locality-sensitive orderings and applications to reliable spanners
• Labeled nearest neighbor search and metric spanners via locality sensitive orderings

This page was built for publication: On Locality-Sensitive Orderings and Their Applications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5090394)