18 citations · 70 across the 15 of their papers we have counts for
4 papers · 1 filter
Dual-Pivot Quicksort: Optimality, Analysis and Zeros of Associated Lattice Paths
Martin Aumüller, Martin Dietzfelbinger, Clemens Heuberger +2
We present an average case analysis of a variant of dual-pivot quicksort. We show that the used algorithmic partitioning strategy is optimal, i.e., it minimizes the expected number…
A Simple Hash Class with Strong Randomness Properties in Graphs and Hypergraphs
Martin Aumüller, Martin Dietzfelbinger, Philipp Woelfel
We study randomness properties of graphs and hypergraphs generated by simple hash functions. Several hashing applications can be analyzed by studying the structure of -uniform r…
Parameter-free Locality Sensitive Hashing for Spherical Range Reporting
Thomas D. Ahle, Martin Aumüller, Rasmus Pagh
We present a data structure for *spherical range reporting* on a point set , i.e., reporting all points in that lie within radius of a given query point . Our solutio…
Counting Zeros in Random Walks on the Integers and Analysis of Optimal Dual-Pivot Quicksort
Martin Aumüller, Martin Dietzfelbinger, Clemens Heuberger +2
We present an average case analysis of two variants of dual-pivot quicksort, one with a non-algorithmic comparison-optimal partitioning strategy, the other with a closely related a…