Recently, motivated by the rapid increase of the data size in various applications, Monemizadeh [APPROX'23] and Driemel, Monemizadeh, Oh, Staals, and Woodruff [SoCG'25] studied geometric problems in the setting where the only access to the input point set is via querying a range-search oracle. Algorithms in this setting are evaluated on two criteria: (i) the number of queries to the oracle and (ii) the error of the output. In this paper, we continue this line of research and investigate one of the most fundamental geometric problems in the oracle setting, i.e., the convex hull problem. Let P be an unknown set of points in [0,1]^d equipped with a range-emptiness oracle. Via querying the oracle, the algorithm is supposed to output a convex polygon C ⊆ [0,1]^d as an estimation of the convex hull CH(P) of P. The error of the output is defined as the volume of the symmetric difference C ⊕ CH(P) = (C∖CH(P)) ∪ (CH(P)∖C). We prove tight and near-tight tradeoffs between the number of queries and the error of the output for different variants of the problem, depending on the type of the range-emptiness queries and whether the queries are non-adaptive or adaptive. - Orthogonal emptiness queries in d-dimensional space: We show that the minimum error a deterministic algorithm can achieve with q queries is Θ(q^{-1/d}) if the queries are non-adaptive, and Θ(q^{-1/(d-1)}) if the queries are adaptive. In particular, in 2D, the bounds are Θ(1/√q) and Θ(1/q) for non-adaptive and adaptive queries, respectively. - Halfplane emptiness queries in 2D: We show that the minimum error a deterministic algorithm can achieve with q queries is Θ(1/√q) if the queries are non-adaptive, and Θ̃(1/q²) if the queries are adaptive. Here Θ̃(⋅) hides logarithmic factors.

In the Rectangle Stabbing problem, input is a set R of axis-parallel rectangles and a set L of axis-parallel lines in the plane. The task is to find a minimum size set L^* ⊆ L such that for every rectangle R ∈ R there is a line 𝓁 ∈ L^* such that 𝓁 intersects R. Gaur et al. [Journal of Algorithms, 2002] gave a polynomial time 2-approximation algorithm, while Dom et al. [WALCOM 2009] and Giannopoulos et al. [EuroCG 2009] independently showed that, assuming FPT ≠ W[1], there is no algorithm with running time f(k)(|L||R|)^O(1) that determines whether there exists an optimal solution with at most k lines. We give the first parameterized approximation algorithm for the problem with a ratio better than 2. In particular we give an algorithm that given R, L, and an integer k runs in time k^O(k)(|L||R|)^O(1) and either correctly concludes that there does not exist a solution with at most k lines, or produces a solution with at most 7k/4 lines. We complement our algorithm by showing that unless FPT = W[1], the Rectangle Stabbing problem does not admit a (5/4-ε)-approximation algorithm running in f(k)(|L||R|)^O(1) time for any function f and ε > 0.

Let G = (V,E) be a directed graph on n vertices where each vertex has out-degree k. We say that G is kNN-realizable in d-dimensional Euclidean space if there exists a point set P = {p_1, p_2, …, p_n} in ℝ^d along with a one-to-one mapping ϕ: V → P such that for any u,v ∈ V, u is an out-neighbor of v in G if and only if ϕ(u) is one of the k nearest neighbors of ϕ(v); we call the map ϕ a kNN-realization of G in ℝ^d. The kNN-realization problem, which aims to compute a kNN-realization of an input graph in ℝ^d, is known to be NP-hard already for d = 2 and k = 1 [Eades and Whitesides, Theoretical Computer Science, 1996], and to the best of our knowledge has not been studied in dimension d = 1. The main results of this paper are the following: - For any fixed dimension d ≥ 2, we can efficiently compute an embedding realizing at least a 1 - ε fraction of G’s edges, or conclude that G is not kNN-realizable in ℝ^d. - For d = 1, we can decide in O(kn) time whether G is kNN-realizable and, if so, compute a realization in O(n^{2.5} poly(log n)) time.

We study the problem of k-dominance in a set of d-dimensional vectors, prove bounds on the number of maxima (skyline vectors), under both worst-case and average-case models, perform experimental evaluation using synthetic and real-world data, and explore an application of k-dominant skyline for extracting a small set of top-ranked vectors in high dimensions where the full skylines can be unmanageably large.