Abstract:

We consider a variant of range searching in which points are coloured. A query, whose input consists of an axis-aligned rectangle as well as a subset of colours, must report all points that lie within the query range and match one of the query colours. Such queries are useful, for example, in searching databases with both numerical and categorical attributes. While previous work has solved the 1-D case in the pointer machine model, we make steps towards solving the 2-D case. We give an optimal data structure for 2-sided (dominance) queries and a data structure for 3-sided queries that is a mere log* factor from optimal.

Joint work with: Peyman Afshani

Host: Gerth Stølting Brodal