Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

The convex hull is defined as the smallest convex set containing a set of points. Now we want to generalize it to a set of balls. If these balls have the same radius, then it can be shown that a ball lies on the boundary of the convex hull of balls if and only if its center lies on the boundary of the convex hull of center.

My question is: what about the case when the balls have different radii? Can we solve it in $O(n\log n)$ time, when there are $n$ balls? The correspondence between the convex hull of centers and the convex hull of balls seem to disappear, thus giving me the difficulty.

Remark: This is taken from an exercise in Chapter 1 of "Computational Geometry: Algorithms and Applications" by Mark de Berg et al.

share|cite|improve this question
QuickHull can be adapted to this case, but I don't know whether that would preserve the $O(n\log n)$ average case complexity. – joriki May 3 '12 at 10:57
Thanks for your suggestion. I will take a look at it. – FiniteA May 4 '12 at 6:46

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.