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.

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

Your Answer

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

Browse other questions tagged or ask your own question.