Approximating Convex Hulls via Range Queries
Thomas Schibler, Jie Xue, Jiumu Zhu · 2026
Read Approximating Convex Hulls via Range Queries by Thomas Schibler, Jie Xue, Jiumu Zhu (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-20943.txt.
Introduction
Schibler, Xue, and Zhu study how well the convex hull of a hidden point set can be estimated through range queries. The only access to the points is a range emptiness oracle. Algorithms are judged by query count and by the volume error of the output shape. For orthogonal queries, they prove tight error bounds that differ for non adaptive and adaptive plans. In two dimensions the error shrinks with the query count, faster for adaptive plans. Halfplane queries get their own bounds.
Catalog record
| CREATOR | Thomas Schibler, Jie Xue, Jiumu Zhu |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 79291 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.20943
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Approximating Convex Hulls via Range Queries Thomas Schibler, Jie Xue, Jiumu Zhu Abstract 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 P be an unknown set of points in [ 0 , 1 ] d [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 C\subseteq[0,1]^{d} as an estimation of the convex hull 𝒞 ℋ ( P ) \mathcal{CH}(P) of P P . The error of the output is defined as the volume of the symmetric difference C ⊕ 𝒞 ℋ ( P ) = ( C \ 𝒞 ℋ ( P ) ) ∪ ( 𝒞 ℋ ( P ) \ C ) C\oplus\mathcal{CH}(P)=(C\backslash\mathcal{CH}(P))\cup(\mathcal{CH}(P)\backslash 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 d -dimensional space: We show that the minimum error a deterministic algorithm can achieve with q q queries is Θ ( q − 1 / d ) \Theta(q^{-1/d}) if the queries are non-adaptive, and Θ ( q − 1 / ( d − 1 ) ) \Theta(q^{-1/(d-1)}) if the queries are adaptive. In particular, in 2D, the bounds are Θ ( 1 / q ) \Theta(1/\sqrt{q}) and Θ ( 1 / q ) \Theta(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 q queries is Θ ( 1 / q ) \Theta(1/\sqrt{q}) if the queries are non-adaptive, and Θ ~ ( 1 / q 2 ) \widetilde{\Theta}(1/q^{2}) if the queries are adaptive. Here Θ ~ ( ⋅ ) \widetilde{\Theta}(\cdot) hides logarithmic factors. University of California, Santa Barbara, [email protected] New York University Shanghai, [email protected] New York University Shanghai, [email protected] ccs Theory of computation Computational geometry ccs Theory of computation Design and analysis of algorithms keywords convex hull, range searching † † runningauthor: T. Schibler, J. Xue, J. Zhu 1 Introduction Classic algorithms are designed to compute solutions to a problem instance by processing the entire input dataset. These algorithms can suffer two potential drawbacks. The first drawback concerns efficiency . As all of the input data has to be received and examined, the time complexity of such algorithms (even the most efficient ones) is at least linear in the input size. However, due to the rapidly growing size of the datasets involved in real-world applications nowadays, linear running time is already not satisfactory in many scenarios. The second drawback regards data privacy . For security reasons, sometimes the users would like to keep their data private and therefore cannot directly provide the exact dataset to the algorithm. Instead, they can only provide partial and implicit information of the dataset and ask the algorithm to give useful results based on the information provided. In this situation, the classic algorithms no longer work due to lack of full information of the dataset. Motivated by removing these drawbacks, researchers have studied algorithms in the oracle model . In this model, the algorithm does not have direct access to the input dataset. Instead, a provided oracle built on the dataset can answer certain queries about the dataset. The algorithm is required to compute a good solution by performing queries to the oracle. Algorithms in this setting are usually evaluated on two criteria: (i) the number of queries to the oracle and (ii) the error of the output. For geometric problems, various types of oracles have been considered in the literature [ 14 , 16 , 15 , 17 , 22 ] . When the input dataset is a set P of points in a Euclidean space \mathbb{R}^{d} , a natural type is the range-search oracle. A query to a range-search oracle is a range Q in the space \mathbb{R}^{d} of a specific shape, and the oracle will return certain information about the points in P\cap Q . For example, a range-counting oracle returns |P\cap Q| [ 1 , 12 ] , a range-emptiness oracle returns whether P\cap Q=\emptyset or not [ 19 , 26 ] , a range-reporting oracle returns the set P\cap Q itself [ 6 , 23 ] , etc. Range-search oracles have the following advantages. First, range search can usually be implemented very efficiently. As a fundamental topic in Computational Geometry, range search has been extensively studied over decades and many efficient data structures have been proposed for various range queries [ 4 , 5 , 9 , 12 , 13 , 21 ] . Furthermore, most types of range search (except range reporting) do not reveal the exact data points inside the query range Q , and therefore data privacy is well guaranteed. Recently, Monemizadeh [ 22 ] and the authors of [ 17 ] studied multiple geometric problems with range-search oracles, following earlier work of Czumaj and Sohler [ 16 ] and the authors of [ 15 ] . Problems considered include facility location [ 22 ] , clustering [ 16 ] , Euclidean minimum spanning tree [ 15 , 17 ] , earth mover distance [ 17 ] , etc. They show that for all these problems, one can obtain nontrivial approximation solutions via a small number of range-search queries. In this paper, we continue this line of research and investigate one of the most fundamental geometric problems, the convex hull problem [ 7 , 8 , 10 , 11 , 24 , 27 ] , in the range-search oracle model. In the convex hull problem, the goal is to compute the convex hull of a set P of points in \mathbb{R}^{d} , denoted by \mathcal{CH}(P) , which by definition is the smallest convex body in \mathbb{R}^{d} containing P . We study the problem with the simplest type of range-search oracles, i.e., range-emptiness oracles. We are interested in finding a convex body C^{*} as an approximation of \mathcal{CH}(P) via a small number of range-emptiness queries. To this end, we need a measure for the error of the approximation. The most natural measure one can use is the relative error \lVert C^{*}\oplus\mathcal{CH}(P)\rVert\ /\ \lVert\mathcal{CH}(P)\rVert , where \lVert\cdot\rVert denotes the volume and C^{*}\oplus\mathcal{CH}(P)=(C^{*}\backslash\mathcal{CH}(P))\cup(\mathcal{CH}(P)\backslash C^{*}) is the symmetric difference between C^{*} and \mathcal{CH}(P) . Unfortunately, one can easily see that it is impossible to approximate the convex hull with any bounded relative error no matter how many range-emptiness queries the algorithm performs 1 1 1 Even in \mathbb{R}^{1} , there is no way to