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}$$.

  • 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?


Unless I misunderstand your post, you are describing the QuickHull algorithm...? The only difference I see is the order of growing each edge: QuickHull's choice follows a recursion, you are processing edges in counterclockwise order. The growth of an edge to its farthest vertex is independent of when that growth occurs, so the behavior is fundamentally the same.

(Image from Wikipedia article.)
The worst-case occurs when each step only incorporates one new point without excluding any others. Points non-uniformly distributed on a circle achieve this, whereas uniformly distributed points on a circle do not.

(Image from Guy Blelloch notes.)

  • $\begingroup$ Yes, that is in the same spirit as the heuristic I described. I am however primarily interested in using the algorithm as a preprocessing step, before switching to asymptotically faster algorithms that require sorting; the interesting question is, how many iterations of the heuristic suffice to remove x percent of the area inside the convex hull, so that the remaining points will be sufficiently close to the convex, so that sorting them is justified. $\endgroup$ – Manfred Weis Jan 5 '17 at 13:58
  • $\begingroup$ @ManfredWeis: I think a worst-case point distribution could lead to arbitrarily small area inflation per step. $\endgroup$ – Joseph O'Rourke Jan 5 '17 at 14:07
  • $\begingroup$ it is clear, that the area inflations will decrease rapidly and I am convinced, that the decrement is *slowest" for sufficiently dense points on a circle - simply because a circle maximizes the ratio of area/circumference (isoperimetric problem), but can that be proved or disproved? $\endgroup$ – Manfred Weis Jan 5 '17 at 15:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.