3 papers
cs.DS2026
Near-Optimal Working-Set Heaps and Dijkstra on Pointer Machines
Ivor van der Hoog, John Iacono, Eva Rotenberg +1
A heap is a dynamic data structure that stores a set of labeled values under the following operations: pop returns the minimum value of the heap, Push() pushes a new value $x_…
cs.DS2026
Partition-based Simple Heaps
Gerth Stølting Brodal, John Iacono, Casper Moldrup Rysgaard +1
We introduce a new family of priority-queue data structures: partition-based simple heaps. The structures consist of doubly-linked lists; order is enforced among data i…
cs.DS2025
Incremental Planar Nearest Neighbor Queries with Optimal Query Time
John Iacono, Yakov Nekrich
In this paper we show that two-dimensional nearest neighbor queries can be answered in optimal time while supporting insertions in time. No p…