title: Medial spheres for shape approximation.
abstract: We study the problem of approximating a 3D solid with a union of overlapping spheres. In comparison with a state-of-the-art approach, our method offers more than an order of magnitude speedup and achieves a tighter approximation in terms of volume difference with the original solid while using fewer spheres. The spheres generated by our method are internal and tangent to the solid's boundary, which permits an exact error analysis, fast updates under local feature size preserving deformation, and conservative dilation. We show that our dilated spheres offer superior time and error performance in approximate separation distance tests than the state-of-the-art method for sphere set approximation for the class of (σ,θ)-fat solids. We envision that our sphere-based approximation will also prove useful for a range of other applications, including shape matching and shape segmentation.
authors.affiliation: School of Computer Science and the Centre for Intelligent Machines, McGill University, Rm 318, McConnell Engineering Bldg, 3480 University Street, Montréal, QC H3A 2A7, Canada. sveta@cim.mcgill.ca
authors.forename: Svetlana
authors.initials: S
authors.lastname: Stolpner
authors.forename: Paul
authors.initials: P
authors.lastname: Kry
authors.forename: Kaleem
authors.initials: K
authors.lastname: Siddiqi
mesh_terms: D000465:Algorithms; D003196:Computer Graphics; D003198:Computer Simulation; D007089:Image Enhancement / Q000379:methods*; D021621:Imaging, Three-Dimensional / Q000379:methods; D010363:Pattern Recognition, Automated / Q000379:methods