Berechnen Sie das Polytop mit der niedrigsten Dimension aus einem bestimmten Satz von Vorzeichenvektoren

Bei einer Menge von Hyperebenen, die durch die Normalenvektoren , sind ihre Zelltypen (oder Vorzeichenvektoren) alle Vektoren für die ein Vektor so daß und $h_1,\dots,h_m \in \mathbf R^d$ $t\in\{+,-\}^m$ $v\in\mathbf R^d$ $\langle v,h_i \rangle \neq 0$ $t_i = \text{sign}( \langle v,h_i \rangle )$ gilt für alle . Hier bezeichnet das innere Produkt und bezeichnen das Vorzeichen ( oder ) der Nicht-Null - reelle Zahl . $i$ $\langle u,v\rangle$ $\text{sign}(x)$ $+$ $-$ $x$

Frage: Was ist der schnellste bekannte Algorithmus für die inverse Operation? Bei einer Menge von Zelltypen wollen wir eine Menge von Hyperebenen in möglichst wenigen Dimensionen berechnen, so dass ihre Zelltypen eine Obermenge von . $t_1,\dots,t_n$ $t_1,\dots,t_n$

co.combinatorics cg.comp-geom computational-geometry metric-spaces Holger
quelle

Übrigens ist nicht klar, was das innere Produkt einer Hyperebene und eines Vektors ist. Wollten Sie, dass

der normale Vektor der

ten Hyperebene ist?

h_{i}

$h_i$

i

$i$

Sasho Nikolov

Ja, sie sollen die normalen Vektoren sein - ich habe formal genau angegeben, wonach ich suche.

Holger

Berechnen Sie das Polytop mit der niedrigsten Dimension aus einem bestimmten Satz von Vorzeichenvektoren

Antworten: