| Abstrakt: |
We define a class of problems whose input is an n-sized set of d-dimensional vectors, and where the problem is first-order definable using comparisons between coordinates. This class captures a wide variety of tasks, such as complex types of orthogonal range search, model-checking first-order properties on geometric intersection graphs, and elementary questions on multidimensional data like verifying Pareto optimality of a choice of data points. Focusing on constant dimension d, we show that any such k-quantifier, d-dimensional problem is solvable in O (n k - 1 log d - 1 n) time. Furthermore, this algorithm is conditionally tight up to subpolynomial factors: we show that assuming the 3-uniform hyperclique hypothesis, there is a k-quantifier, (3 k - 3) -dimensional problem in this class that requires time Ω (n k - 1 - o (1)) . Towards identifying a single representative problem for this class, we study the existence of complete problems for the 3-quantifier setting (since 2-quantifier problems can already be solved in near-linear time O (n log d - 1 n) , and k-quantifier problems with k > 3 reduce to the 3-quantifier case). We define a problem Vector Concatenated Non-Domination VCND d (Given three sets of vectors X, Y and Z of dimension d, d and 2d, respectively, is there an x ∈ X and a y ∈ Y so that their concatenation x ∘ y is not dominated by any z ∈ Z , where vector u is dominated by vector v if u i ≤ v i for each coordinate 1 ≤ i ≤ d ), and determine it as the "unique" candidate to be complete for this class (under fine-grained assumptions). [ABSTRACT FROM AUTHOR] |
Full text from SpringerLink