DROPS

Document

DOI: 10.4230/LIPIcs.SoCG.2026.89

Approximating Convex Hulls via Range Queries

Authors: Thomas Schibler, Jie Xue, and Jiumu Zhu

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

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 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.

Cite as

Thomas Schibler, Jie Xue, and Jiumu Zhu. Approximating Convex Hulls via Range Queries. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 89:1-89:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{schibler_et_al:LIPIcs.SoCG.2026.89,
  author =	{Schibler, Thomas and Xue, Jie and Zhu, Jiumu},
  title =	{{Approximating Convex Hulls via Range Queries}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{89:1--89:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.89},
  URN =		{urn:nbn:de:0030-drops-258956},
  doi =		{10.4230/LIPIcs.SoCG.2026.89},
  annote =	{Keywords: convex hull, range searching}
}

Document

DOI: 10.4230/LIPIcs.SoCG.2025.77

Dynamic Maximum Depth of Geometric Objects

Authors: Subhash Suri, Jie Xue, Xiongxin Yang, and Jiumu Zhu

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract

Given a set of geometric objects in the plane (rectangles, squares, disks etc.), its maximum depth (or geometric clique) is the largest number of objects with a common intersection. In this paper, we present data structures for dynamically maintaining the maximum depth under insertions and deletions of geometric objects, with sublinear update time. We achieve the following results: - a 1/k-approximate dynamic maximum-depth data structure for (axis-parallel) rectangles with O(n^{1/(k+1)} log n) amortized update time, for any fixed k ∈ ℤ^+. In particular, when k = 1, this gives an exact data structure for rectangles with O(√n log n) amortized update time, almost matching the best known bound for the offline version of the problem. - a (1/2-ε)-approximate dynamic maximum-depth data structure for disks with n^{2/3} log^{O(1)}n amortized update time, for any constant ε > 0. Having exact data structures for disks with sublinear update time is unlikely, since the static maximum-depth problem for disks is 3SUM-hard and thus does not admit subquadratic-time algorithms.

Cite as

Subhash Suri, Jie Xue, Xiongxin Yang, and Jiumu Zhu. Dynamic Maximum Depth of Geometric Objects. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 77:1-77:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{suri_et_al:LIPIcs.SoCG.2025.77,
  author =	{Suri, Subhash and Xue, Jie and Yang, Xiongxin and Zhu, Jiumu},
  title =	{{Dynamic Maximum Depth of Geometric Objects}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{77:1--77:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.77},
  URN =		{urn:nbn:de:0030-drops-232295},
  doi =		{10.4230/LIPIcs.SoCG.2025.77},
  annote =	{Keywords: dynamic algorithms, maximum depth}
}

Search Results

Documents authored by Zhu, Jiumu

Approximating Convex Hulls via Range Queries

Abstract

Cite as

Dynamic Maximum Depth of Geometric Objects

Abstract

Cite as

Thanks for your feedback!

Could not send message