4
$\begingroup$

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.

  • 0
    Thanks for your suggestion. I will take a look at it.2012-05-04

0 Answers 0