Let P be a set of n points and each of the points is colored with one of the k possible colors. We present efficient algorithms to pre-process P such that for a given query point q, we can quickly identify the smallest color spanning object of the desired type containing q. In this paper, we focus on (i) intervals, (ii) axis-parallel square, (iii) axis-parallel rectangle, (iv) equilateral triangle of fixed orientation, as our desired type of objects.

Color-spanning object, Localized query, Multilevel range searching
Lecture Notes in Computer Science
Computational Geometry Lab

Acharyya, A. (Ankush), Maheshwari, A, & Nandy, S.C. (Subhas C.). (2019). Localized query: Color spanning variations. In Lecture Notes in Computer Science. doi:10.1007/978-3-030-11509-8_13