On Semialgebraic Range Reporting

TY - GEN

T1 - On Semialgebraic Range Reporting

AU - Afshani, Peyman

AU - Cheng, Pingan

N1 - Publisher Copyright: © Peyman Afshani and Pingan Cheng; licensed under Creative Commons License CC-BY 4.0

PY - 2022/6

Y1 - 2022/6

N2 - 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 RD 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, “near-linear space” data structures [6, 18] with almost optimal query time of Q(n) = O(n1-1/D+o(1)) were obtained. For “fast query” data structures (i.e., when Q(n) = no(1)), it was conjectured that a similar improvement is possible, i.e., it is possible to achieve space S(n) = O(nD+o(1)). The conjecture was refuted very recently by Afshani and Cheng [3]. In the plane, i.e., D = 2, they proved that S(n) = ?(n?+1-o(1)/Q(n)(?+3)?/2) which shows ?(n?+1-o(1)) space is needed for Q(n) = no(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(nm+o(1)/Q(n)(m-1)D/(D-1)) where m = (DD+?) - 1 = ?(?D) is the maximum number of parameters to define a monic degree-? D-variate polynomial, for any constant dimension D and degree ?. In this paper, we resolve two of the issues: we prove a lower bound in D-dimensions, for constant D, and show that when the query time is no(1) + O(k), the space usage is ?(nm-o(1)), which almost matches the Õ(nm) upper bound and essentially closes the problem for the fast-query 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 [3] 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.

AB - 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 RD 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, “near-linear space” data structures [6, 18] with almost optimal query time of Q(n) = O(n1-1/D+o(1)) were obtained. For “fast query” data structures (i.e., when Q(n) = no(1)), it was conjectured that a similar improvement is possible, i.e., it is possible to achieve space S(n) = O(nD+o(1)). The conjecture was refuted very recently by Afshani and Cheng [3]. In the plane, i.e., D = 2, they proved that S(n) = ?(n?+1-o(1)/Q(n)(?+3)?/2) which shows ?(n?+1-o(1)) space is needed for Q(n) = no(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(nm+o(1)/Q(n)(m-1)D/(D-1)) where m = (DD+?) - 1 = ?(?D) is the maximum number of parameters to define a monic degree-? D-variate polynomial, for any constant dimension D and degree ?. In this paper, we resolve two of the issues: we prove a lower bound in D-dimensions, for constant D, and show that when the query time is no(1) + O(k), the space usage is ?(nm-o(1)), which almost matches the Õ(nm) upper bound and essentially closes the problem for the fast-query 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 [3] 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.

KW - Computational Geometry

KW - Data Structures and Algorithms

KW - Lower Bounds

KW - Range Searching

UR - https://www.scopus.com/pages/publications/85134304476

U2 - 10.4230/LIPIcs.SoCG.2022.3

DO - 10.4230/LIPIcs.SoCG.2022.3

M3 - Article in proceedings

AN - SCOPUS:85134304476

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 38th International Symposium on Computational Geometry, SoCG 2022

A2 - Goaoc, Xavier

A2 - Kerber, Michael

PB - Dagstuhl Publishing

T2 - 38th International Symposium on Computational Geometry, SoCG 2022

Y2 - 7 June 2022 through 10 June 2022

ER -