In this paper we present several results on the expected complexity of a
convex hull of $n$ points chosen uniformly and independently from a convex
shape.

(i) We show that the expected number of vertices of the convex hull of $n$
points, chosen uniformly and independently from a disk is $O(n^{1/3})$, and
$O(k \log{n})$ for the case a convex polygon with $k$ sides. Those results are
well known (see \cite{rs-udkhv-63,r-slcdn-70,ps-cgi-85}), but we believe that
the elementary proof given here are simpler and more intuitive.

The dissimilarity of two polygonal curves can be measured using the Fr\'echet
distance. We introduce the notion of a more robust Fr\'echet distance, where
one is allowed to shortcut between vertices of one of the curves. This is a
natural approach for handling noise, in particular batched outliers. We compute
a constant factor approximation to the minimum Fr\'echet distance over all
possible shortcut curves. Our algorithm is simple and runs in time O(c k^2 n
log^4 n) if one is allowed to take at most k shortcuts and the input curves are
c-packed.

We present simple and practical $(1+\eps)$-approximation algorithm for the
Frechet distance between curves. To analyze this algorithm we introduce a new
realistic family of curves, $c$-packed curves, that is closed under
simplification. We believe the notion of $c$-packed curves to be of independent
interest. We show that our algorithm has near linear running time for
$c$-packed curves, and show similar results for other input models.