Znalezienie płaszczyzny cięcia, która równomiernie dzieli wielościan

Powiedzmy, że mamy wielościan w standardowej formie:

\begin{aligned} ZA x = b \\ x \geq 0 \end{aligned}

$\begin{equation*} \begin{array}{rl} \mathbf{A}\mathbf{x} = \mathbf{b} \\\\ \mathbf{x} \ge 0 \end{array} \end{equation*}$

Czy są znane metody znalezienia hiperpłaszczyzny która dzieli wielościan w taki sposób, że liczba wierzchołków po każdej stronie hiperpłaszczyzny jest w przybliżeniu taka sama? (tj. algorytm minimalizujący absolutną różnicę liczności wierzchołków po obu stronach podziału). $\mathbf{d} \mathbf{x} +d_0= 0$

Czy są też jakieś znane wyniki dotyczące złożoności tego problemu?

Dodatek: Ograniczanie rodzajów cięć:

Oto wariant pierwotnego problemu z nadzieją, że łatwiej go rozwiązać niż oryginalny:

Czy istnieje sposób na wydajne obliczenie lub oszacowanie, dla której współrzędnej hiperpłaszczyzna w postaci dałaby najniższą bezwzględną różnicę liczności wierzchołków po obu stronach podziału? Przez „efektywny” rozumiem coś bardziej wydajnego niż wyczerpujące wyliczenie liczności wierzchołków dla wszystkich możliwych takich podziałów. $i$ $d_ix_i + d_0 = 0$

Uwaga: po kilku dniach niewielkich postępów opublikowałem to pytanie również w MathOverflow .

ds.algorithms linear-programming linear-algebra

— Amelio Vazquez-Reina
źródło

Czy nie można udowodnić, że jest to trudny problem związany z NP?

— Peter Shor,

Dzięki @Peter. Dowód byłby świetny. To powiedziawszy, zakładam, że problem jest trudny i myślę, że bardziej interesują mnie algorytmy heurystyczne lub aproksymacyjne. Motywem pomysłu ograniczenia rodzajów cięć było po części sprawdzenie, czy istnieją łatwiejsze warianty ogólnego problemu, dla którego znamy już rozwiązanie lub algorytm aproksymacyjny.

— Amelio Vazquez-Reina

Co powiesz na coś w tym kierunku (nie jestem pewien, czy to działa) - Wiemy, że policzenie maksymalnej liczby dwustronnych dopasowań to # P-trudne. Wiemy również, że liniowy program znajdujący maksymalne dopasowanie dwustronne jest całkowicie niemodularny, a zatem każde narożne / podstawowe możliwe rozwiązanie jest integralne. W przypadku problemu z maksymalnym dwustronnym dopasowaniem znajdź wartość dopasowania. Skonstruuj program liniowy z takim ograniczeniem, że każde rozwiązanie musi mieć optymalną wartość. Zatem każdy punkt narożny jest dopasowany. Możliwość wielokrotnego dzielenia równomiernie oznacza, że powinieneś być w stanie policzyć liczbę dopasowań.

— blokujący

Nieważne. Trzeba też umieć policzyć liczbę wierzchołków dodanych przez płaszczyznę cięcia.

— blokujący

-2

Nie pamiętam analitycznego sposobu, aby to zrobić!

Ale to klasyczny problem dla programowania genetycznego! Jeśli go znasz, możesz użyć znormalizowanych wektorów w środku wielościanu, które opisują płaszczyznę cięcia.

Zatem twoja populacja jest zbiorem znormalizowanych wektorów [x, y, z, ...] i jako funkcję dopasowania używasz różnicy między 2 podzielonymi objętościami!

Tak więc, jeśli różnica zmierza do zera, więcej „dopasowania” oznacza wektor / płaszczyznę!

— Eduardo Pons
źródło

Przepraszam, czy możesz to powtórzyć bez użycia języka programowania genetycznego? Co to jest „populacja”? Co to jest „funkcja dopasowania”?

— Jeffε