Abstract

In this paper, we study estimators for geometric optimization problems in the sublinear geometric model. In this model, we have oracle access to a point set with size \(n\) in a discrete space \([\Delta]^d\), where queries can be made to an oracle that responds to orthogonal range counting requests. The query complexity of an optimization problem is measured by the number of oracle queries required to compute an estimator for the problem. We investigate two problems in this framework, the Euclidean Minimum Spanning Tree (MST) and Earth Mover Distance (EMD). For EMD, we show the existence of an estimator that approximates the cost of EMD with \(O(\log \Delta)\)-relative error and \(O(\frac{n\Delta}{s^{1+1/d}})\)-additive error using \(O(s\polylog \Delta)\) range counting queries for any parameter \(s\) with \(1\leq s \leq n\). Moreover, we prove that this bound is tight. For MST, we demonstrate that the weight of MST can be estimated within a factor of \((1 \pm \eps)\) using \(\tilde{O}(\sqrt{n})\) range counting queries.

Corresponding Publications

Range Counting Oracles for Geometric Problems

Anne Driemel, Morteza Monemizadeh, Eunjin Oh, Frank Staals, David Woodruff

Proc. 41th Annual Symposium on Computational Geometry, 2025

Download Local Copy View Slides Export Citation

@inproceedings{sublinearemst2025,
  author = {Driemel, Anne and Monemizadeh, Morteza and Oh, Eunjin and
                 Staals, Frank and Woodruff, David},
  title = {Range Counting Oracles for Geometric Problems},
  booktitle = {Proc. 41th Annual Symposium on Computational Geometry},
  year = {2025},
  location = {Kanazawa Japan},
  keywords = {Range counting oracles, minimum spanning trees, Earth Mover's Distance},
  category = {other},
  series = {Leibniz International Proceedings in Informatics (LIPIcs)},
  publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  doi = {10.4230/LIPIcs.SoCG.2025.42},
  url = {https://doi.org/10.4230/LIPIcs.SoCG.2025.42},
}