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 Õ(√n) range counting queries.