On semialgebraic range reporting

DOI10.1007/S00454-023-00574-1MaRDI QIDQ6145667zbMATH OpenOpenAlexFDO

Authors Peyman Afshani, Pingan Cheng

Publication date 9 January 2024

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2203.07096

zbMATH Keywords

computational geometrydata structureslower boundssemialgebraic range searching

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Abstract: In the problem of semialgebraic range searching, we are to preprocess a set of points in $mathbb{R}^D$ such that the subset of points inside a semialgebraic region described by $O(1)$ polynomial inequalities of degree $Delta$ can be found efficiently. Relatively recently, several major advances were made on this problem. Using algebraic techniques, "near-linear space" structures [AMS13,MP15] with almost optimal query time of $Q(n)=O(n^{1-1/D+o(1)})$ were obtained. For "fast query" structures (i.e., when $Q(n)=n^{o(1)}$), it was conjectured that a structure with space $S(n)=O(n^{D+o(1)})$ is possible. The conjecture was refuted recently by Afshani and Cheng [AC21]. In the plane, they proved that $S(n)=Omega(n^{Delta+1-o(1)}/Q(n{)}^{(Delta+3)Delta/2})$ which shows $Omega(n^{Delta+1-o(1)})$ space is needed for $Q(n)=n^{o(1)}$. While this refutes the conjecture, it still leaves a number of unresolved issues: the lower bound only works in 2D and for fast queries, and neither the exponent of $n$ or $Q(n)$ seem to be tight even for $D=2$, as the current upper bound is $$ where $$ is the maximum number of parameters to define a monic degree-$Delta$ $D$-variate polynomial, for any $D,Delta=O(1)$. In this paper, we resolve two of the issues: we prove a lower bound in $D$-dimensions and show that when $Q(n)=n^{o(1)}+O(k)$, $$, which is almost tight as far as the exponent of $n$ is considered in the pointer machine model. When considering the exponent of $Q(n)$, we show that the analysis in [AC21] is tight for $D=2$, by presenting matching upper bounds for uniform random point sets. This shows either the existing upper bounds can be improved or a new fundamentally different input set is needed to get a better lower bound.

Cites work

• A New Lower Bound for Semigroup Orthogonal Range Searching
• Efficient Algorithm for Generalized Polynomial Partitioning and Its Applications
• How hard is half-space range searching?
• Improved pointer machine and I/O lower bounds for simplex range reporting and related problems
• Lower bounds for orthogonal range searching: I. The reporting case
• Lower bounds for orthogonal range searching: part II. The arithmetic model
• Lower Bounds on the Complexity of Polytope Range Searching
• Multilevel polynomial partitions and simplified range searching
• On range searching with semialgebraic sets. II.
• On the Erdős distinct distances problem in the plane
• On the importance of idempotence
• Range searching with efficient hierarchical cuttings
• Simplex range reporting on a pointer machine
• Simplex Range Searching and Its Variants: A Review
• Tight lower bounds for halfspace range searching

This page was built for publication: On semialgebraic range reporting

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6145667)