Afshani, Peyman ;
Cheng, Pingan
On Semialgebraic Range Reporting
Abstract
Semialgebraic range searching, arguably the most general version of range searching, is a fundamental problem in computational geometry. In the problem, we are to preprocess a set of points in ℝ^D such that the subset of points inside a semialgebraic region described by a constant number of polynomial inequalities of degree Δ can be found efficiently.
Relatively recently, several major advances were made on this problem. Using algebraic techniques, "nearlinear space" data structures [Agarwal et al., 2013; Matoušek and Patáková, 2015] with almost optimal query time of Q(n) = O(n^{11/D+o(1)}) were obtained. For "fast query" data structures (i.e., when Q(n) = n^{o(1)}), it was conjectured that a similar improvement is possible, i.e., it is possible to achieve space S(n) = O(n^{D+o(1)}). The conjecture was refuted very recently by Afshani and Cheng [Afshani and Cheng, 2021]. In the plane, i.e., D = 2, they proved that S(n) = Ω(n^{Δ+1  o(1)}/Q(n)^{(Δ+3)Δ/2}) which shows Ω(n^{Δ+1o(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 best known upper bounds have S(n) = O(n^{m+o(1)}/Q(n)^{(m1)D/(D1)}) where m = binom(D+Δ,D)1 = Ω(Δ^D) is the maximum number of parameters to define a monic degreeΔ Dvariate polynomial, for any constant dimension D and degree Δ.
In this paper, we resolve two of the issues: we prove a lower bound in Ddimensions, for constant D, and show that when the query time is n^{o(1)}+O(k), the space usage is Ω(n^{mo(1)}), which almost matches the Õ(n^{m}) upper bound and essentially closes the problem for the fastquery case, 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 [Afshani and Cheng, 2021] 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 to obtain better lower bounds a new fundamentally different input set needs to be constructed.
BibTeX  Entry
@InProceedings{afshani_et_al:LIPIcs.SoCG.2022.3,
author = {Afshani, Peyman and Cheng, Pingan},
title = {{On Semialgebraic Range Reporting}},
booktitle = {38th International Symposium on Computational Geometry (SoCG 2022)},
pages = {3:13:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772273},
ISSN = {18688969},
year = {2022},
volume = {224},
editor = {Goaoc, Xavier and Kerber, Michael},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16011},
URN = {urn:nbn:de:0030drops160117},
doi = {10.4230/LIPIcs.SoCG.2022.3},
annote = {Keywords: Computational Geometry, Range Searching, Data Structures and Algorithms, Lower Bounds}
}
01.06.2022
Keywords: 

Computational Geometry, Range Searching, Data Structures and Algorithms, Lower Bounds 
Seminar: 

38th International Symposium on Computational Geometry (SoCG 2022)

Issue date: 

2022 
Date of publication: 

01.06.2022 