<p>There is a vast theoretical literature on approximating convex, compact bodies in <span class="math-container">$d$</span>-dimensional space <span class="math-container">$\Bbb R^d$</span> by <a href="https://en.wikipedia.org/wiki/Convex_polytope" rel="nofollow noreferrer">convex polytopes</a>.</p>
<p>One of the main results in this area is that under some mild conditions, given any convex, compact body <span class="math-container">$C\subset \Bbb R^d$</span> and an error parameter <span class="math-container">$\epsilon &gt; 0$</span>, there exists a polytope <span class="math-container">$P$</span> having <span class="math-container">$O(\frac{1}{\epsilon^{(d-1)/2}})$</span> facets such that <span class="math-container">$P$</span> is &quot;<span class="math-container">$\epsilon$</span>-close&quot; to <span class="math-container">$C$</span> (with respect to, e.g., the <a href="https://en.wikipedia.org/wiki/Hausdorff_distance" rel="nofollow noreferrer">Hausdorff distance</a>). A nice proof of this result appears <a href="https://arxiv.org/pdf/1912.01977.pdf" rel="nofollow noreferrer">here</a>.</p>
<p>However, my attempts to dig into the literature on <em>algorithms</em> that can actually construct these approximating polytopes have been less than fruitful so far.</p>
<p>I have found several papers that that seem related, such as <a href="https://arxiv.org/pdf/1810.12098.pdf" rel="nofollow noreferrer">1</a>, <a href="https://arxiv.org/pdf/2103.06613.pdf" rel="nofollow noreferrer">2</a>, <a href="https://www.researchgate.net/publication/262364653_Analysis_of_an_algorithm_for_approximating_convex_bodies" rel="nofollow noreferrer">3</a>, 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.</p>
<p>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.</p>
<p><strong>Edit:</strong> 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 <span class="math-container">$P$</span> that approximates (in the Hausdorff metric) the unit ball <span class="math-container">$B$</span> in <span class="math-container">$\Bbb R^d$</span> to a given error parameter <span class="math-container">$\epsilon &gt; 0$</span>.</p>

CC BY-SA 4.0
2024-02-26T09:43:00.890Z
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.
Tassle
CC BY-SA 4.0
2024-02-26T14:25:25.350Z
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.
pyridoxal_trigeminus
<ds.algorithms><reference-request><approximation-algorithms><cg.comp-geom><convex-geometry>
References for algorithms to compute approximating polytopes for arbitrary convex sets
pyridoxal_trigeminus
# References for algorithms to compute approximating polytopes for arbitrary convex sets

(Asked by: username_0 on 2024-02-26)

There is a vast theoretical literature on approximating convex, compact bodies in $d$-dimensional space $\Bbb R^d$ by [convex polytopes](https://en.wikipedia.org/wiki/Convex_polytope).

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](https://en.wikipedia.org/wiki/Hausdorff_distance)). A nice proof of this result appears [here](https://arxiv.org/pdf/1912.01977.pdf).

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](https://arxiv.org/pdf/1810.12098.pdf), [2](https://arxiv.org/pdf/2103.06613.pdf), [3](https://www.researchgate.net/publication/262364653_Analysis_of_an_algorithm_for_approximating_convex_bodies), 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$.

**Tags:** ds.algorithms, reference-request, approximation-algorithms, cg.comp-geom, convex-geometry

> **Comments:**
> **username_1**: 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.  
> **username_0**: 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.  

---

## 0 answers

