8 citations · 32 across the 18 of their papers we have counts for
6 papers · 1 filter
Dynamic Optimality Refuted -- For Tournament Heaps
J. Ian Munro, Richard Peng, Sebastian Wild +1
We prove a separation between offline and online algorithms for finger-based tournament heaps undergoing key modifications. These heaps are implemented by binary trees with keys st…
On Approximate Range Mode and Range Selection
Hicham El-Zein, Meng He, J. Ian Munro +2
For any , a -approximate range mode query asks for the position of an element whose frequency in the query range is at most a factor smaller than the tru…
Dynamic Planar Point Location in External Memory
J. Ian Munro, Yakov Nekrich
In this paper we describe a fully-dynamic data structure for the planar point location problem in the external memory model. Our data structure supports queries in $O(\log_B n(\log…
Entropy Trees and Range-Minimum Queries In Optimal Average-Case Space
J. Ian Munro, Sebastian Wild
The range-minimum query (RMQ) problem is a fundamental data structuring task with numerous applications. Despite the fact that succinct solutions with worst-case optimal …
Space-Efficient Data Structures for Lattices
J. Ian Munro, Bryce Sandlund, Corwin Sinnamon
A lattice is a partially-ordered set in which every pair of elements has a unique meet (greatest lower bound) and join (least upper bound). We present new data structures for latti…
On Huang and Wong's Algorithm for Generalized Binary Split Trees
Marek Chrobak, Mordecai Golin, J. Ian Munro +1
Huang and Wong [1984] proposed a polynomial-time dynamic-programming algorithm for computing optimal generalized binary split trees. We show that their algorithm is incorrect. Thus…