I am currently implementing a heuristic algorithm for planar convex hulls hand would like to know, for which kind of strictly convex region it exhibits worst performance.

I know that there are many different algorithms for calculating planar convex hulls, so there is no need to provide me with pointers to algorithms for *that* problem.

$$ $$
**The heuristic:**

the objective of the heuristic is a successive refinement of the convex hull starting with two points $p$ and $q$ of with minimal, resp. maximal x-coordinate, i.e. $x(p) < x(q)$.

Assuming that the points are in general position and, that the resulting hull shall be oriented counter clockwise, the heuristic is to

- start with the "digon" hull $\left\{(p,q),(q,p)\right\} := CH_0$
- construct $CH_{i+1}$ from $CH_i$ by inserting between the adjacent vertices $u$ and $w$ of each edge $\left(u,w\right)$ of $CH_i$ the vertex $v$ that is not yet in $CH_i$ and farthest to the right of $\left(u,w\right)$, thus effectively replacing $\left(u,w\right)$ with $\left(u,v\right),\left(v,w\right)$ (provided such $v$ exists)

It is obvious that the heuristic strives for creating a $CH_{i+1}$ of maximal area when epanding $CH_i$; the rationale for that heuristic thus is to be able to exlude a maximal subset of the points, that are not elements of the final convex hull.

Formulated differently, the heuristic strives for the fastest exhaustion of a polygonal convex area; the heuristic easily transfers to exhausting strictly convex regions.

$$ $$

using the above heuristic for exhausting a (w.l.o.g unit area) disk yields a $CH_i$ with area $$\cos\left(\frac{\pi}{2^i}\right)\sin\left(\frac{\pi}{2^i}\right)\frac{2^i}{\pi}$$.

Questions:

is the circular disk the convex region with the slowest growing exhaustion-ratio and, if it isn't,

what are examples of worse regions, resp.

which region is the worst?