文章基本信息

标题：Approximate Range Counting Revisited
本地全文：下载
作者：Saladi Rahul
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2017
卷号：77
页码：55:1-55:15
DOI：10.4230/LIPIcs.SoCG.2017.55
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：We study range-searching for colored objects, where one has to count (approximately) the number of colors present in a query range. The problems studied mostly involve orthogonal range-searching in two and three dimensions, and the dual setting of rectangle stabbing by points. We present optimal and near-optimal solutions for these problems. Most of the results are obtained via reductions to the approximate uncolored version, and improved data-structures for them. An additional contribution of this work is the introduction of nested shallow cuttings.
关键词：orthogonal range searching; rectangle stabbing; colors; approximate count; geometric data structures