Kevin Buchin, Simon Plantinga, Günter Rote, Astrid Sturm, and Gert Vegter:

Convex approximation by spherical patches

In: Abstracts of the 23rd European Workshop on Computational Geometry, Graz, March 2007, pp. 26–29.


Given points in convex position in three dimensions, we want to find an approximating convex surface consisting of spherical patches, such that all points are within some specified tolerance bound of the approximating surface. We describe a greedy algorithm which constructs an approximating surface whose spherical patches are associated to the faces of an inscribed polytope. We show that deciding whether an approximation with not more than a given number of spherical patches exists is NP-hard.

  pdf file (gzipped)
other papers about this subject
Last update: April 13, 2010.