Abstract Accurate and Efficient Unions of Balls

Given a sample of points from the bound-ary of an object in IR 3, we construct a rep-resentation of the object as a union of balls. We use many fewer balls than previous con-structions, but our shape representation is better. We bound the distance from the surface of the union to the original object surface, and show that when the sampling is sufficiently dense the two are homeomor-phic. This implies a topological relation-ship between the true medial axis of the object and both the medial axis, and the a-shape, of the union of balls. We show that the set of ball centers in our construc-tion converges to the true medial axis as the sampling density increases.