18 citations · 72 across the 35 of their papers we have counts for
6 papers · 1 filter
The Complexity of Order Type Isomorphism
Greg Aloupis, John Iacono, Stefan Langerman +1
The order type of a point set in maps each -tuple of points to its orientation (e.g., clockwise or counterclockwise in ). Two point sets and have the sa…
In pursuit of the dynamic optimality conjecture
John Iacono
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 offlin…
Combining Binary Search Trees
Erik D. Demaine, John Iacono, Stefan Langerman +1
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 Power and Limitations of Static Binary Search Trees with Lazy Finger
Prosenjit Bose, Karim Douïeb, John Iacono +1
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 o…
The Fresh-Finger Property
John Howat, John Iacono, Pat Morin
The unified property roughly states that searching for an element is fast when the current access is close to a recent access. Here, "close" refers to rank distance measured among…
Why some heaps support constant-amortized-time decrease-key operations, and others do not
John Iacono
A lower bound is presented which shows that a class of heap algorithms in the pointer model with only heap pointers must spend Omega(log log n / log log log n) amortized time on th…