Self-improving Algorithms for Coordinate-wise Maxima

Details Self-improving Algorithms for Coordinate-wise Maxima Self-improving Algorithms for Coordinate-wise Maxima

2012-04-03

arxiv.org/abs/1204.0824v1

Computer Science

Computational Geometry

To appear in Symposium of Computational Geometry 2012 (17 pages, 2 figures)

Scientific paper

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 $\cD_1, \cD_2, ..., \cD_n$ of planar points. An input pointset $(p_1, p_2, ..., p_n)$ is generated by taking an independent sample $p_i$ from each $\cD_i$, so the input distribution $\cD$ is the product $\prod_i \cD_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 $\OPT_\cD$ 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(\text{OPT}_\cD + 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$.

Affiliated with

Also associated with

No associations

Rating

Self-improving Algorithms for Coordinate-wise Maxima does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Self-improving Algorithms for Coordinate-wise Maxima, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Self-improving Algorithms for Coordinate-wise Maxima will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-31176