There is a vast theoretical literature on approximating convex, compact bodies in $d$-dimensional space $\Bbb R^d$ by convex polytopes.

One of the main results in this area is that under some mild conditions, given any convex, compact body $C\subset \Bbb R^d$ and an error parameter $\epsilon > 0$, there exists a polytope $P$ having $O(\frac{1}{\epsilon^{(d-1)/2}})$ facets such that $P$ is "$\epsilon$-close" to $C$ (with respect to, e.g., the Hausdorff distance). A nice proof of this result appears here.

However, my attempts to dig into the literature on algorithms that can actually construct these approximating polytopes have been less than fruitful so far.

I have found several papers that that seem related, such as 1, 2, 3, but so far the papers I've found either don't seem to directly address the question, or the time bounds of the algorithm(s) are not apparent to me. I have mostly found rather vague references to algorithms, without much in terms of explicit details.

If someone can point me to additional resources for explicitly constructing polytope approximations, it would be greatly helpful. It would also be extremely useful if someone familiar with this area could provide a brief overview of the different types of algorithms that are used for this task, and where I could learn more about them.

Edit: I thought I would add a more concrete problem to my question: For example, I would like to find an algorithm to compute a polytope $P$ that approximates (in the Hausdorff metric) the unit ball $B$ in $\Bbb R^d$ to a given error parameter $\epsilon > 0$.

  • $\begingroup$ Doesn't the proof you link provide such an algorithm (at least for the question in your edit)? Compute a maximal $\delta$ packing of the sphere of radius $2d$ (seems easy enough to do in time proportional in the size of the packing), project radially on $B$ to get the nearest neighbours, and take the intersection of the tangent halfplanes through these points. In general computing the nearest neighbours and tangent planes might be more complicated, but if what we are trying to approximate is a sphere it should be straightforward. $\endgroup$
    – Tassle
    Feb 26 at 9:43
  • $\begingroup$ Thanks. Yes, I did notice that, however I have not been able to find any clear algorithms for computing maximal packings of continuous objects (e.g., spheres). I have just found such algorithms for nets and packings in finite metric spaces. I'm not a computer scientist, so maybe the continuous case is easy to figure out, but I'm not sure how. $\endgroup$ Feb 26 at 14:25


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.