Hitung polytope dimensi terendah dari satu set vektor tanda

Diberikan satu set pesawat terbang yang ditentukan oleh vektor normal , tipe selnya (atau tanda vektor) adalah semua vektor yang terdapat vektor sehingga dan $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 )$ berlaku untuk semua . Di sini, menunjukkan produk dalam dan menunjukkan tanda ( atau ) dari non-nol bilangan real . $i$ $\langle u,v\rangle$ $\text{sign}(x)$ $+$ $-$ $x$

Pertanyaan: Apa algoritma yang paling cepat diketahui untuk operasi invers? Dengan satu set dari tipe sel, kami ingin menghitung beberapa set hyperplanes dalam dimensi sesedikit mungkin, sehingga tipe selnya adalah superset dari . $t_1,\dots,t_n$ $t_1,\dots,t_n$

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

BTW tidak jelas apa produk dalam hyperplane dan vektor. Apakah Anda berniat

menjadi vektor normal dari

hyperplane -th?

h_{i}

$h_i$

i

$i$

Sasho Nikolov

Ya, mereka seharusnya vektor normal - saya menyatakan secara formal apa yang saya cari.

Holger

Hitung polytope dimensi terendah dari satu set vektor tanda

Jawaban: