Self-improving algorithms for coordinatewise maxima and convex hulls

Abstract

Finding the coordinatewise maxima and the convex hull of a planar point set are probably the most classic problems in computational geometry. We consider these problems in the self-improving setting. Here, we have n distributions D1, ⋯ ,Dn of planar points. An input point set (p1, ⋯ , pn) is generated by taking an independent sample pi from each Di, so the input is distributed according to the product D = i Di. A self-improving algorithm repeatedly gets inputs from the distribution D (which is a priori unknown), and it tries to optimize its running time for D. The algorithm uses the first few inputs to learn salient features of the distribution D before it becomes fine-tuned to D. Let OPT-MAXD (resp., OPT-CHD) be the expected depth of an optimal linear comparison tree computing the maxima (resp., convex hull) for D. Our maxima algorithm eventually achieves expected running time O(OPT-MAXD+n). Furthermore, we give a self-improving algorithm for convex hulls with expected running time O(OPT-CHD + n log log n). Our results require new tools for understanding linear comparison trees. In particular, we convert a general linear comparison tree to a restricted version that can then be related to the running time of our algorithms. Another interesting feature is an interleaved search procedure to determine the likeliest point to be extremal with minimal computation. This allows our algorithms to be competitive with the optimal algorithm for D. © 2014 Society for InduStrial and Applied Mathematics.