Esiste un algoritmo per trovare i vettori di spigolo di un politopo? [duplicare]
Domanda:
Dati alcuni punti$x^1,\dots,x^m \in \mathbb R^n$, esiste un algoritmo che trova i vettori lungo i bordi del politopo$$P = \mathrm{conv}(x^1,\dots,x^n)$$formato dallo scafo convesso di questi punti?
Definizioni:
Un politopo è lo scafo convesso di un numero finito di punti$\mathbb R^n$. Permettere$P \subset \mathbb R^n$essere un politopo. Un volto di$P$è un sottoinsieme$F \subset P$della forma$$F = \arg \max\{c^Tx : x \in P\}$$per alcuni$c \in \mathbb R^n$. La dimensione di un volto di$P$è la dimensione del suo scafo affine. Un vertice è una faccia di dimensione zero e un bordo è una faccia di dimensione uno. Se$E$è un bordo di$P$poi$E = \mathrm{conv}(x, y)$per alcuni vertici$x$,$y$. Un vettore di spigolo di un politopo$P$è un vettore$v \in \mathbb R^n$tale che$v=x-y$per alcuni vertici$x$e$y$per cui$\mathrm{conv}(x,y)$è un vantaggio.
Esempio:
Permettere$x^1=(0,0), x^2=(1,0), x^3=(0,1), x^4=(1,1)$. Lo scafo convesso di questi punti è il quadrato$$P=\mathrm{conv}(x^1, x^2, x^3, x^4)$$i cui vettori di spigolo sono dati da$$\{(1,0), (0,1), (-1, 0), (0, -1)\}.$$Notare che$(1,1)=x^4-x^1$non è un vettore di spigolo sebbene sia la differenza di due vertici.
Risposte
In una prima fase devi determinare quali punti sono i vertici dello scafo convesso. In un secondo passaggio puoi procedere come spiegato da kimchi nei commenti.
Un punto$x_i$è un vertice di$\mathrm{conv}\{x_1,...,x_n\}$Se
$$\max \{p^\top\! x_i\mid p^\top\! x_j \le 1 \text{ for all $j\not=io$}\}$$
è illimitato.
Se$x_i,x_j$sono vertici, per determinare se$\mathrm{conv}\{x_i,x_j\}$è un bordo dello scafo convesso puoi procedere come spiegato in questa risposta . Devi ripeterlo su tutto${n\choose 2}$coppie di vertici. Se è un vantaggio, devi solo calcolare$x_i-x_j$per ottenere la sua direzione.
Per calcolare i massimi in tutti questi casi dovrai usare algoritmi di programmazione lineare che sono standard e hanno molte implementazioni ben sviluppate (ad esempio in Mathematica o MATLAB).