Color-spanning localized query

Authors: Ankush Acharyya, A. Maheswari, S. C. Nandy
Publication year: 2021
Publication type: Článek v odborném periodiku
Periodical: Theoretical Computer Science
Projects: Structural properties of visibility in terrains and farthest color Voronoi diagrams
Bibliographic citation: ACHARYYA, Ankush, MAHESWARI, A., NANDY, S. C. Color-spanning localized query. Theoretical Computer Science. 2021, 861(March 2021), 85-101. ISSN 0304-3975. E-ISSN 1879-2294
Dostupné z: doi:10.1016/j.tcs.2021.02.013.
DOI: 10.1016/j.tcs.2021.02.013
ID: 540808
Online record: View online record

Abstract

Let P be a set of n points, where each point is colored with one of the k possible colors. We present efficient algorithms to preprocess 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, axis-parallel rectangle, equilateral triangle of fixed orientation and (v) circle, as our desired type of objects.