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...
share
research
∙
02/22/2022
How Fast Can We Play Tetris Greedily With Rectangular Pieces?
Consider a variant of Tetris played on a board of width w and infinite h...
research
∙
12/19/2021
Conditional Lower Bounds for Dynamic Geometric Measure Problems
We give new polynomial lower bounds for a number of dynamic measure prob...
research
∙
09/15/2021
Subquadratic Algorithms for Some 3Sum-Hard Geometric Problems in the Algebraic Decision Tree Model
We present subquadratic algorithms in the algebraic decision-tree model ...
research
∙
08/18/2021
Worst-Case Efficient Dynamic Geometric Independent Set
We consider the problem of maintaining an approximate maximum independen...
research
∙
06/28/2021
Dynamic Schnyder Woods
A realizer, commonly known as Schnyder woods, of a triangulation is a pa...
research
∙
06/24/2021
Approximability of (Simultaneous) Class Cover for Boxes
Bereg et al. (2012) introduced the Boxes Class Cover problem, which has ...
research
∙
06/10/2021
An Instance-optimal Algorithm for Bichromatic Rectangular Visibility
Afshani, Barbay and Chan (2017) introduced the notion of instance-optima...
research
∙
01/30/2021
Fragile Complexity of Adaptive Algorithms
The fragile complexity of a comparison-based algorithm is f(n) if each i...
research
∙
08/19/2020
Modular Subset Sum, Dynamic Strings, and Zero-Sum Sets
The modular subset sum problem consists of deciding, given a modulus m, ...
research
∙
07/16/2020
Dynamic Geometric Independent Set
We present fully dynamic approximation algorithms for the Maximum Indepe...
research
∙
07/03/2020
Sublinear Explicit Incremental Planar Voronoi Diagrams
A data structure is presented that explicitly maintains the graph of a V...
research
∙
04/16/2020
Compatible Paths on Labelled Point Sets
Let P and Q be finite point sets of the same cardinality in ℝ^2, each la...
research
∙
08/25/2019
A parallel priority queue with fast updates for GPU architectures
The high computational throughput of modern graphics processing units (G...
research
∙
08/02/2019
Competitive Online Search Trees on Trees
We consider the design of adaptive data structures for searching element...
research
∙
05/07/2019
External Memory Planar Point Location with Fast Updates
We study dynamic planar point location in the External Memory Model or D...
research
∙
03/08/2019
Belga B-trees
We revisit self-adjusting external memory tree data structures, which co...
research
∙
03/07/2019
External memory priority queues with decrease-key and applications to graph algorithms
We present priority queues in the external memory model with block size ...
research
∙
03/06/2019
Encoding 3SUM
We consider the following problem: given three sets of real numbers, out...
research
∙
02/21/2019
Locality
The performance of modern computation is characterized by locality of re...
research
∙
10/03/2018
Weighted dynamic finger in binary search trees
It is shown that the online binary search tree data structure GreedyASS ...
research
∙
08/14/2018
Spanning Properties of Theta-Theta-6
We show that, unlike the Yao-Yao graph YY_6, the Theta-Theta graph ΘΘ_6 ...
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
∙
01/05/2018