Obliczanie elipsoidy wielościanu Löwnera-Johna

Elipsoida Löwnera-Johna z wypukłego zestawu jest elipsoidą o minimalnej objętości (MVE), która ją otacza. Elipsoidę można obliczyć metodą Khachiyana i istnieje wiele przybliżeń, jeśli jest (wypukłym kadłubem) zbiorem punktów. $C$ $C$

Czy istnieją szybkie (tj. Oparte na metodzie nieelipsoidalnej) aproksymacje MVE ograniczonego wielościanu przedstawione tylko w odniesieniu do półpłaszczyzn, których przecięcia to definiują? W szczególności interesowałyby mnie metody działające w czasie wielomian w wymiarze i błąd odwrotny . $1/\varepsilon$

cg.comp-geom convex-geometry

— Suresh Venkat
źródło

czy wiemy nawet, jak obliczyć / aproksymować promień wielościanu w tym systemie? ponieważ bez tego nie widzę nawet wyroczni separacyjnej dla algorytmu elipsoidy

— Sasho Nikolov,

Według Boyda jest to NP-trudne: http://youtu.be/mNzu42FrlHo?t=41m3s

— Nicholas DeWaal
źródło

Ciekawy. i sugeruje również, że odwrotnie jest w przypadku elipsoidy z maksymalną objętością (łatwą dla powtórzeń H, ale trudną dla powtórzeń V). Nadal mam nadzieję, że istnieją pewne dobre propozycje, więc wstrzymam się z odpowiedzią, ale wrócę za dzień lub dwa.

— Suresh Venkat,