Allan Grønlund

collaborators

Showing cs.DSShow all

2 papers · 1 filter

cs.DS2014

Towards Tight Lower Bounds for Range Reporting on the RAM

Allan Grønlund, Kasper Green Larsen

In the orthogonal range reporting problem, we are to preprocess a set of $n$ points with integer coordinates on a $U \times U$ grid. The goal is to support reporting all $k$ points…

cs.DS2014

Approximate Range Emptiness in Constant Time and Optimal Space

Mayank Goswami, Allan Grønlund, Kasper Green Larsen +1

This paper studies the \emph{ $ε$ -approximate range emptiness} problem, where the task is to represent a set $S$ of $n$ points from ${0, \dots, U - 1}$ and answer emptiness…