A Generalization of Self-Improving Algorithms

Siu-Wing Cheng, Man-Kwun Chiu, Kai Jin +1

Ailon et al. [SICOMP'11] proposed self-improving algorithms for sorting and Delaunay triangulation (DT) when the input instances $x_1,\cdots ,x_n$ follow some unknown \emph{product…