Range Counting Oracles for Geometric Problems

Anne Driemel; Morteza Monemizadeh; Eunjin Oh; Frank Staals; David P. Woodruff

doi:10.4230/LIPIcs.SoCG.2025.42

Range Counting Oracles for Geometric Problems

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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

1 Downloads (Pure)

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 [Δ]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 Δ)-relative error and O(nΔ/s1+1/d)-additive error using O(s polylog Δ) range counting queries for any parameter s with 1 ≤ s ≤ 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 ± ∈) using Õ(√n) range counting queries.

Original language	English
Title of host publication	41st International Symposium on Computational Geometry, SoCG 2025
Editors	Oswin Aichholzer, Haitao Wang
Publisher	Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Chapter	16
ISBN (Electronic)	9783959773706
DOIs	https://doi.org/10.4230/LIPIcs.SoCG.2025.42
Publication status	Published - 20 Jun 2025
Event	41st International Symposium on Computational Geometry, SoCG 2025 - Kanazawa, Japan Duration: 23 Jun 2025 → 27 Jun 2025

Publication series

Name	Leibniz International Proceedings in Informatics, LIPIcs
Volume	332
ISSN (Print)	1868-8969

Conference

Conference	41st International Symposium on Computational Geometry, SoCG 2025
Country/Territory	Japan
City	Kanazawa
Period	23/06/25 → 27/06/25

Bibliographical note

Publisher Copyright:
© Anne Driemel, Morteza Monemizadeh, Eunjin Oh, Frank Staals, and David P. Woodruff.

Keywords

Earth Mover's Distance
minimum spanning trees
Range counting oracles

Access to Document

10.4230/LIPIcs.SoCG.2025.42

pdfFinal published version, 939 KBLicence: CC BY

Cite this

Driemel, A., Monemizadeh, M., Oh, E., Staals, F., & Woodruff, D. P. (2025). Range Counting Oracles for Geometric Problems. In O. Aichholzer, & H. Wang (Eds.), 41st International Symposium on Computational Geometry, SoCG 2025 Article 42 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 332). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2025.42

@inproceedings{fcc272591f854dafac0c35e11755d1db,

title = "Range Counting Oracles for Geometric Problems",

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 [Δ]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 Δ)-relative error and O(nΔ/s1+1/d)-additive error using O(s polylog Δ) range counting queries for any parameter s with 1 ≤ s ≤ 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 ± ∈) using {\~O}(√n) range counting queries.",

keywords = "Earth Mover's Distance, minimum spanning trees, Range counting oracles",

author = "Anne Driemel and Morteza Monemizadeh and Eunjin Oh and Frank Staals and Woodruff, \{David P.\}",

note = "Publisher Copyright: {\textcopyright} Anne Driemel, Morteza Monemizadeh, Eunjin Oh, Frank Staals, and David P. Woodruff.; 41st International Symposium on Computational Geometry, SoCG 2025 ; Conference date: 23-06-2025 Through 27-06-2025",

year = "2025",

month = jun,

day = "20",

doi = "10.4230/LIPIcs.SoCG.2025.42",

language = "English",

series = "Leibniz International Proceedings in Informatics, LIPIcs",

publisher = "Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik",

editor = "Oswin Aichholzer and Haitao Wang",

booktitle = "41st International Symposium on Computational Geometry, SoCG 2025",

}

Driemel, A, Monemizadeh, M, Oh, E, Staals, F & Woodruff, DP 2025, Range Counting Oracles for Geometric Problems. in O Aichholzer & H Wang (eds), 41st International Symposium on Computational Geometry, SoCG 2025., 42, Leibniz International Proceedings in Informatics, LIPIcs, vol. 332, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 41st International Symposium on Computational Geometry, SoCG 2025, Kanazawa, Japan, 23/06/25. https://doi.org/10.4230/LIPIcs.SoCG.2025.42

Range Counting Oracles for Geometric Problems. / Driemel, Anne; Monemizadeh, Morteza; Oh, Eunjin et al.
41st International Symposium on Computational Geometry, SoCG 2025. ed. / Oswin Aichholzer; Haitao Wang. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. 42 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 332).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Range Counting Oracles for Geometric Problems

AU - Driemel, Anne

AU - Monemizadeh, Morteza

AU - Oh, Eunjin

AU - Staals, Frank

AU - Woodruff, David P.

PY - 2025/6/20

Y1 - 2025/6/20

N2 - 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 [Δ]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 Δ)-relative error and O(nΔ/s1+1/d)-additive error using O(s polylog Δ) range counting queries for any parameter s with 1 ≤ s ≤ 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 ± ∈) using Õ(√n) range counting queries.

AB - 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 [Δ]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 Δ)-relative error and O(nΔ/s1+1/d)-additive error using O(s polylog Δ) range counting queries for any parameter s with 1 ≤ s ≤ 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 ± ∈) using Õ(√n) range counting queries.

KW - Earth Mover's Distance

KW - minimum spanning trees

KW - Range counting oracles

UR - https://www.scopus.com/pages/publications/105009597979

U2 - 10.4230/LIPIcs.SoCG.2025.42

DO - 10.4230/LIPIcs.SoCG.2025.42

M3 - Conference contribution

AN - SCOPUS:105009597979

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 41st International Symposium on Computational Geometry, SoCG 2025

A2 - Aichholzer, Oswin

A2 - Wang, Haitao

PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik

T2 - 41st International Symposium on Computational Geometry, SoCG 2025

Y2 - 23 June 2025 through 27 June 2025

ER -

Range Counting Oracles for Geometric Problems

Abstract

Publication series

Conference

Bibliographical note

Keywords

Access to Document

Other files and links

Fingerprint

Cite this