Self-improving algorithms for coordinate-wise maxima
Kenneth L. Clarkson, Wolfgang Mulzer, Comandur Seshadhri · 2012
Computing the coordinate-wise maxima of a planar point set is a classic and well-studied problem in computational geometry. We give an algorithm for this problem in the self-improving setting. We have n (unknown) independent distributions cD1, cD2, ..., cDn of planar points. An input pointset (p1, p2, ..., pn) is generated by taking an independent sample pi from each cDi, so the input distribution cD is the product prodi cDi. A self-improving algorithm repeatedly gets input sets from the distribution cD (which is a priori unknown) and tries to optimize its running time for cD. Our algorithm uses the first few inputs to learn salient features of the distribution, and then becomes an optimal algorithm for distribution cD. Let OPTcD denote the expected depth of an optimal linear comparison tree computing the maxima for distribution cD. Our algorithm eventually has an expected running time of O(OPTcD + n), even though it did not know cD to begin with.