30 citations · 82 across the 38 of their papers we have counts for
4 papers · 1 filter
New Data Structures for Orthogonal Range Reporting and Range Minima Queries
Yakov Nekrich
In this paper we present new data structures for two extensively studied variants of the orthogonal range searching problem. First, we describe a data structure that supports two-d…
Distance Oracles for Interval Graphs via Breadth-First Rank/Select in Succinct Trees
Meng He, J. Ian Munro, Yakov Nekrich +2
We present the first succinct distance oracles for (unweighted) interval graphs and related classes of graphs, using a novel succinct data structure for ordinal trees that supports…
Further Results on Colored Range Searching
Timothy M. Chan, Qizheng He, Yakov Nekrich
We present a number of new results about range searching for colored (or "categorical") data: 1. For a set of colored points in three dimensions, we describe randomized data st…
Four-Dimensional Dominance Range Reporting in Linear Space
Yakov Nekrich
In this paper we study the four-dimensional dominance range reporting problem and present data structures with linear or almost-linear space usage. Our results can be also used to…