Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|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
add comment

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.