-
Article
Belga B-Trees
We revisitself-adjustingexternal memory tree data structures, which combine the optimal (and practical) worst-case I/O performances of B-trees, while adapting to the online distribution of queries. Our approac...
-
Chapter and Conference Paper
Fragile Complexity of Adaptive Algorithms
The fragile complexity of a comparison-based algorithm is f(n) if each input element participates in O(f(n)) comparisons. In this paper, we explore the fragile complexity of algorithms adaptive to various restric...
-
Article
Spanning Properties of Theta–Theta-6
We show that, unlike the Yao–Yao graph \(YY_6\)YY6, the Theta–Theta graph \({\varTheta }{\varTheta }_6\)ΘΘ6 defined by six cones is a spanner for sets of points in convex position. We also show that, for sets of ...
-
Article
Subquadratic Algorithms for Algebraic 3SUM
The 3SUM problem asks if an input n-set of real numbers contains a triple whose sum is zero. We qualify such a triple of degenerate because the probability of finding one in a random input is zero. We consider th...
-
Chapter and Conference Paper
Belga B-Trees
We revisit self-adjusting external memory tree data structures, which combine the optimal (and practical) worst-case I/O performances of B-trees, while adapting to the online distribution of queries. Our appro...
-
Article
Data Structures for Halfplane Proximity Queries and Incremental Voronoi Diagrams
We consider preprocessing a set S of n points in convex position in the plane into a data structure supporting queries of the following form: given a point q and a directed line
-
Article
Incremental Voronoi Diagrams
We study the amortized number of combinatorial changes (edge insertions and removals) needed to update the graph structure of the Voronoi diagram (and several variants thereof) of a set S of n sites in the plane ...
-
Chapter and Conference Paper
Searching Edges in the Overlap of Two Plane Graphs
Consider a pair of plane straight-line graphs whose edges are colored red and blue, respectively, and let n be the total complexity of both graphs. We present a
-
Article
The Power and Limitations of Static Binary Search Trees with Lazy Finger
A static binary search tree where every search starts from where the previous one ends (lazy finger) is considered. Such a search method is more powerful than that of the classic optimal static trees, where every...
-
Chapter and Conference Paper
A Linear Potential Function for Pairing Heaps
We present the first potential function for pairing heaps with linear range. This implies that the runtime of a short sequence of operations is faster than previously known. It is also simpler than the only ot...
-
Article
Worst-Case Optimal Tree Layout in External Memory
Consider laying out a fixed-topology binary tree of N nodes into external memory with block size B so as to minimize the worst-case number of block memory transfers required to traverse a path from the root to a ...
-
Chapter and Conference Paper
Range Minimum Query Indexes in Higher Dimensions
Range minimum queries (RMQs) are essential in many algorithmic procedures. The problem is to prepare a data structure on an array to allow for fast subsequent queries that find the minimum within a range in th...
-
Article
Necklaces, Convolutions, and X+Y
We give subquadratic algorithms that, given two necklaces each with n beads at arbitrary positions, compute the optimal rotation of the necklaces to best align the beads. Here alignment is measured according to t...
-
Chapter and Conference Paper
The Power and Limitations of Static Binary Search Trees with Lazy Finger
A static binary search tree where every search starts from where the previous one ends (lazy finger) is considered. Such a search method is more powerful than that of the classic optimal static trees, where every...
-
Chapter and Conference Paper
Cache-Oblivious Persistence
Partial persistence is a general transformation that takes a data structure and allows queries to be executed on any past state of the structure. The cache-oblivious model is the leading model of a modern mult...
-
Chapter and Conference Paper
Why Some Heaps Support Constant-Amortized-Time Decrease-Key Operations, and Others Do Not
A lower bound is presented which shows that a class of heap algorithms in the pointer model with only heap pointers must spend $\Omega...
-
Article
On the hierarchy of distribution-sensitive properties for data structures
In this paper new dependencies are added to the hierarchy of the distribution-sensitive properties for data structures. Most remarkably, we prove that the working-set property is equivalent to the unified-boun...
-
Article
Coverage with k-transmitters in the presence of obstacles
For a fixed integer k≥0, a k-transmitter is an omnidirectional wireless transmitter with an infinite broadcast range that is able to penetrate up to k “walls”, represented as line segments in the plane. We develo...
-
Chapter and Conference Paper
Combining Binary Search Trees
We present a general transformation for combining a constant number of binary search tree data structures (BSTs) into a single BST whose running time is within a constant factor of the minimum of any “well-beh...
-
Chapter
In Pursuit of the Dynamic Optimality Conjecture
In 1985, Sleator and Tarjan introduced the splay tree, a self-adjusting binary search tree algorithm. Splay trees were conjectured to perform within a constant factor as any offline rotation-based search tree ...
