  Finding the coordinate-wise 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
$\mathcal{D}_1, \ldots, \mathcal{D}_n$ of planar points. An input point set
$(p_1, \ldots, p_n)$ is generated by taking an independent sample $p_i$ from
each $\mathcal{D}_i$, so the input is distributed according to the product
$\mathcal{D} = \prod_i \mathcal{D}_i$. A self-improving algorithm repeatedly
gets inputs from the distribution $\mathcal{D}$ (which is a priori unknown),
and it tries to optimize its running time for $\mathcal{D}$. The algorithm uses
the first few inputs to learn salient features of the distribution
$\mathcal{D}$, before it becomes fine-tuned to $\mathcal{D}$. Let
$\text{OPTMAX}_\mathcal{D}$ (resp. $\text{OPTCH}_\mathcal{D}$) be the expected
depth of an \emph{optimal} linear comparison tree computing the maxima (resp.
convex hull) for $\mathcal{D}$. Our maxima algorithm eventually achieves
expected running time $O(\text{OPTMAX}_\mathcal{D} + n)$. Furthermore, we give
a self-improving algorithm for convex hulls with expected running time
$O(\text{OPTCH}_\mathcal{D} + 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 $\mathcal{D}$.
