Space-time trade-offs for some ranking and searching queries

We study space/time tradeoffs for querying some combinatorial structures. I n the first, given an arrangement of n lines in general position in the pla ne, a query for a real number t asks about Rank(t), the number of vertices of the arrangement with x-coordinates less than or equal to t. We show that for K = O(n/log n), after a preprocessing step that uses space S = O(n(2)/ (K log K)) the query can be answered in time O(n log K). The second query i nvolves the Cartesian sum of vectors a = (a(1),..., a(n)) and b = (b(1)..., b(n)). For a given real t, it asks about Rank(t), the number of sums a(i) + b(j) which are less than or equal to t. We show that for some positive co nstant c and K less than or equal to c(log n)/(log log n), after a preproce ssing step that uses space S = O(n(2)/K-2), the query may be answered in ti me O((n/K) log K). Both results fit neatly between two obvious extremes. (C ) 2001 Elsevier Science B.V. All rights reserved.