文章基本信息

标题：Dynamic Colored Orthogonal Range Searching
本地全文：下载
作者：Chan, Timothy M. ; Huang, Zhengcheng
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2021
卷号：204
DOI：10.4230/LIPIcs.ESA.2021.28
语种：English
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：In the colored orthogonal range reporting problem, we want a data structure for storing n colored points so that given a query axis-aligned rectangle, we can report the distinct colors among the points inside the rectangle. This natural problem has been studied in a series of papers, but most prior work focused on the static case. In this paper, we give a dynamic data structure in the 2D case which can answer queries in O(log^{1+o(1)} n + klog^{1/2+o(1)}n) time, where k denotes the output size (the number of distinct colors in the query range), and which can support insertions and deletions in O(log^{2+o(1)}n) time (amortized) in the standard RAM model. This is the first fully dynamic structure with polylogarithmic update time whose query cost per color reported is sublogarithmic (near √{log n}). We also give an alternative data structure with O(log^{1+o(1)} n + klog^{3/4+o(1)}n) query time and O(log^{3/2+o(1)}n) update time (amortized). We also mention extensions to higher constant dimensions.
关键词：Range searching;dynamic data structures;word RAM