<p>According to Boyd, it's NP-hard: <a href="http://youtu.be/mNzu42FrlHo?t=41m3s">http://youtu.be/mNzu42FrlHo?t=41m3s</a></p>

CC BY-SA 3.0
2012-12-22T22:54:32.280Z
Interesting. and he also suggests that the opposite is true for max volume inscribed ellipsoid (easy for the H-rep, but hard for the V-rep). I'm still hoping there are some good approiximations, so I'll hold off on accepting the answer, but I'll revisit in a day or two.
Suresh Venkat
CC BY-SA 3.0
2012-12-22T21:10:01.343Z
2012-12-22T21:10:01.343Z
Nicholas DeWaal
<p>The Löwner-John ellipsoid of a convex set $C$ is the minimum-volume ellipsoid (MVE) that encloses it. The ellipsoid can be computed using Khachiyan's method, and there are a number of approximations available if $C$ is (the convex hull of) a set of points. </p>

<p>Are there fast (i.e non-ellipsoid-method based) approximations to the MVE of a bounded polyhedron presented only in terms of the halfplanes whose intersections define it ? In particular, I'd be interested in methods that run in time polynomial in the dimension and the inverse error $1/\varepsilon$.</p>

CC BY-SA 3.0
2012-12-22T12:14:19.070Z
do we even know how to compute/approximate the radius of the polyhedron in this regime? because without that I don't even see a separation oracle for the ellipsoid algorithm
Sasho Nikolov
<cg.comp-geom><convex-geometry>
Computing the Löwner-John ellipsoid of a polyhedron
Suresh Venkat
# Computing the Löwner-John ellipsoid of a polyhedron

(Asked by: username_0 on 2012-12-22)

The Löwner-John ellipsoid of a convex set $C$ is the minimum-volume ellipsoid (MVE) that encloses it. The ellipsoid can be computed using Khachiyan's method, and there are a number of approximations available if $C$ is (the convex hull of) a set of points.

Are there fast (i.e non-ellipsoid-method based) approximations to the MVE of a bounded polyhedron presented only in terms of the halfplanes whose intersections define it ? In particular, I'd be interested in methods that run in time polynomial in the dimension and the inverse error $1/\varepsilon$.

**Tags:** cg.comp-geom, convex-geometry
> **Comments:**
> **username_1**: do we even know how to compute/approximate the radius of the polyhedron in this regime? because without that I don't even see a separation oracle for the ellipsoid algorithm  

---

## 1 answers

### Answer by username_2 on 2012-12-22. Score: 8

According to Boyd, it's NP-hard: <http://youtu.be/mNzu42FrlHo?t=41m3s>

> **Comments:**
> **username_0**: Interesting. and he also suggests that the opposite is true for max volume inscribed ellipsoid (easy for the H-rep, but hard for the V-rep). I'm still hoping there are some good approiximations, so I'll hold off on accepting the answer, but I'll revisit in a day or two.  

---

