DROPS

Document

DOI: 10.4230/LIPIcs.SoCG.2024.60

Near Optimal Locality Sensitive Orderings in Euclidean Space

Authors: Zhimeng Gao and Sariel Har-Peled

Published in: LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)

Abstract

For a parameter ε ∈ (0,1), a set of ε-locality-sensitive orderings (LSOs) has the property that for any two points, p,q ∈ [0,1)^d, there exist an order in the set such that all the points between p and q (in the order) are ε-close to either p or q. Since the original construction of LSOs can not be (significantly) improved, we present a construction of modified LSOs, that yields a smaller set, while preserving their usefulness. Specifically, the resulting set of LSOs has size M = O(ℰ^{d-1} log ℰ), where ℰ = 1/ε. This improves over previous work by a factor of ℰ, and is optimal up to a factor of log ℰ. As a consequence we get a flotilla of improved dynamic geometric algorithms, such as maintaining bichromatic closest pair, and spanners, among others. In particular, for geometric dynamic spanners the new result matches (up to the aforementioned log ℰ factor) the lower bound, Specifically, this is a near-optimal simple dynamic data-structure for maintaining spanners under insertions and deletions.

Cite as

Zhimeng Gao and Sariel Har-Peled. Near Optimal Locality Sensitive Orderings in Euclidean Space. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 60:1-60:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{gao_et_al:LIPIcs.SoCG.2024.60,
  author =	{Gao, Zhimeng and Har-Peled, Sariel},
  title =	{{Near Optimal Locality Sensitive Orderings in Euclidean Space}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{60:1--60:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-316-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{293},
  editor =	{Mulzer, Wolfgang and Phillips, Jeff M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.60},
  URN =		{urn:nbn:de:0030-drops-200053},
  doi =		{10.4230/LIPIcs.SoCG.2024.60},
  annote =	{Keywords: Orderings, approximation}
}

Search Results

Documents authored by Gao, Zhimeng

Near Optimal Locality Sensitive Orderings in Euclidean Space

Abstract

Cite as

Thanks for your feedback!

Could not send message