research
∙
05/05/2023
Sum-of-Local-Effects Data Structures for Separable Graphs
It is not difficult to think of applications that can be modelled as gra...
share
research
∙
11/11/2022
External-memory dictionaries with worst-case update cost
The B^ϵ-tree [Brodal and Fagerberg 2003] is a simple I/O-efficient exter...
research
∙
11/06/2022
4D Range Reporting in the Pointer Machine Model in Almost-Optimal Time
In the orthogonal range reporting problem we must pre-process a set P of...
research
∙
07/12/2021
Finding a Maximum Clique in a Grounded 1-Bend String Graph
A grounded 1-bend string graph is an intersection graph of a set of poly...
research
∙
07/21/2020
New Data Structures for Orthogonal Range Reporting and Range Minima Queries
In this paper we present new data structures for two extensively studied...
research
∙
06/22/2020
Fast Preprocessing for Optimal Orthogonal Range Reporting and Range Successor with Applications to Text Indexing
Under the word RAM model, we design three data structures that can be co...
research
∙
05/15/2020
Breadth-First Rank/Select in Succinct Trees and Distance Oracles for Interval Graphs
We present the first succinct data structure for ordinal trees that supp...
research
∙
03/25/2020
Further Results on Colored Range Searching
We present a number of new results about range searching for colored (or...
research
∙
03/15/2020
Four-Dimensional Dominance Range Reporting in Linear Space
In this paper we study the four-dimensional dominance range reporting pr...
research
∙
07/19/2019
On Approximate Range Mode and Range Selection
For any ϵ∈ (0,1), a (1+ϵ)-approximate range mode query asks for the posi...
research
∙
05/07/2019
Orthogonal Range Reporting and Rectangle Stabbing for Fat Rectangles
In this paper we study two geometric data structure problems in the spec...
research
∙
03/15/2019
Dynamic Planar Point Location in External Memory
In this paper we describe a fully-dynamic data structure for the planar ...
research
∙
06/27/2018
Dynamic Trees with Almost-Optimal Access Cost
An optimal binary search tree for an access sequence on elements is a st...
research
∙
05/19/2018
Orthogonal Point Location and Rectangle Stabbing Queries in 3-d
In this work, we present a collection of new results on two fundamental ...
research
∙
12/20/2017