| Space-time trade-os for some ranking and searching queries (2007) | |||||||||||||||
Abstract | |||||||||||||||
| We study space/time tradeos for querying some combinatorial structures. In the rst, given an arrangement of n lines in general position in the plane, a query for a real number t asks about Rank(t), the number of vertices of the arrangement with x-coordinates t. We show that for K = O(n=log n), after a preprocessing step that uses space S = O(n | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||