We present an algorithm for computing the exact interior medial axis of a union of balls in R~d, Our algorithm combines the simple characterization of this medial axis given by Attali and Montanvert with the combinatorial information provided by Edelsbrunner's α-shape. This leads to a simple algorithm, which we have implemented for d = 3.
展开▼