Self-improving algorithms for coordinate-wise maxima

DOI10.1145/2261250.2261291MaRDI QIDQ2874589zbMATH OpenOpenAlexFDO

Authors Kenneth L. Clarkson, Wolfgang Mulzer, C. Seshadhri

Publication date 7 August 2014

Published in Proceedings of the twenty-eighth annual symposium on Computational geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1204.0824, https://www.osti.gov/biblio/1118451

zbMATH Keywords

coordinate-wise maximaself-improving algorithms

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: 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 emph{self-improving setting}. We have $n$ (unknown) independent distributions $c{D}_1,c{D}_2,\mathrm{...},c{D}_n$ of planar points. An input pointset $(p_1,p_2,\mathrm{...},p_n)$ is generated by taking an independent sample $p_i$ from each $c{D}_i$, so the input distribution $cD$ is the product $pro{d}_{i}c{D}_i$. A self-improving algorithm repeatedly gets input sets from the distribution $cD$ (which is emph{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 $OP{T}_{c}D$ denote the expected depth of an emph{optimal} linear comparison tree computing the maxima for distribution $cD$. Our algorithm eventually has an expected running time of $O(ext{OPT}_{c}D+n)$, even though it did not know $cD$ to begin with. Our result requires new tools to understand linear comparison trees for computing maxima. We show how to convert general linear comparison trees to very restricted versions, which can then be related to the running time of our algorithm. An interesting feature of our algorithm is an interleaved search, where the algorithm tries to determine the likeliest point to be maximal with minimal computation. This allows the running time to be truly optimal for the distribution $cD$.

Recommendations

• Self-improving algorithms for coordinatewise maxima and convex hulls
• Self-improving algorithms
• Self-improving algorithms for convex hulls
• Self-improving algorithms for delaunay triangulations
• scientific article; zbMATH DE number 2038886

Cited in

(9)

• Extensions of self-improving sorters
• Self-improving algorithms
• Maxima-finding algorithms for multidimensional samples: A two-phase approach
• scientific article; zbMATH DE number 1444320 (Why is no real title available?)
• Self-Improving Algorithms
• A PAC Approach to Application-Specific Algorithm Selection
• Self-improving algorithms for convex hulls
• Self-improving algorithms for coordinatewise maxima and convex hulls
• An efficient convex hull algorithm using affine transformation in planar point set

This page was built for publication: Self-improving algorithms for coordinate-wise maxima

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2874589)