¿Cómo encontrar algorítmicamente sólo las aristas de un casco convexo de alta dimensión?

Question

Me han dado un conjunto de puntos $p_1,...,p_n\in\Bbb R^d$ en posición general. Quiero determinar sólo las aristas del casco convexo $C:=\mathrm{conv}\{p_1,...,p_n\}$ y esto de la manera más eficiente posible. Especialmente, no quiero calcular el casco convexo completo con todas sus caras y luego extraer sólo el $1$ -cara del resultado. Esto supondría demasiada sobrecarga.

De forma abstracta, el problema plantea lo siguiente:

Para qué pares $(p_i,p_j)$ existe una función lineal $\Bbb R^d\to\Bbb R$ que toma su máximo exactamente en $p_i$ y $p_j$ ?

Podemos suponer que el origen está dentro del casco convexo, y que todos los puntos serán vértices del casco convexo.

Un algoritmo general sería bienvenido. Sin embargo, para mi caso de uso específico podemos suponer además que todos los puntos son del mismo tipo, es decir, para dos puntos cualesquiera, digamos $p_i$ y $p_j$ existe una transformación de simetría $\phi$ de la disposición, de modo que $\phi(p_i)=p_j$ .

---

Appraoch

Mi enfoque anterior era el siguiente. Dado un par $(p_i,p_j)$ :

• Calcula $q:=p_i+p_j$ .
• Encuentre los puntos que maximizan $\langle p_i,q\rangle$ .
• Si estos son exactamente los puntos $p_i$ y $p_j$ (ni más ni menos), entonces forman un borde. De lo contrario, no lo hacen.

El algoritmo no da falsos positivos, pero sí falsos negativos. Así que puede encontrar muy pocas aristas. Creo que se trata de elegir $q$ de una manera mejor. Pero no tengo ni idea de cómo hacer esto en general.

---

Esta pregunta es diferente de mi otra pregunta en cascos convexos, ya que aquí pido algoritmos eficientes en lugar de técnicas abstractas, y además tengo otras suposiciones sobre el conjunto de puntos.

Además, ya tengo un algoritmo específico en mente, en el que preferiría sólo oír hablar de una opción de trabajo mejor para $q$ . Por supuesto, también son bienvenidos otros enfoques.

Answer 1

Para cada par $\{\mathbf p_i, \mathbf p_j\}$ podemos encontrar $\mathbf q$ mediante la resolución de un programa lineal. Por ejemplo, el programa lineal $$ \min_{\boldsymbol \lambda} \left\{0 : \sum_{k \ne i,j} \lambda_k \mathbf p_k = \lambda_i \mathbf p_i + \lambda_j \mathbf p_j, \sum_{k \ne i,j} \lambda_k = 1, \lambda_i + \lambda_j = 1, \boldsymbol \lambda \ge \mathbf 0\right\} $$ es inviable cuando $\mathbf p_i$ y $\mathbf p_j$ forman una arista (representa "encontrar un punto en el casco convexo de $\mathbf p_i$ y $\mathbf p_j$ que también está en el casco convexo de los otros puntos"). Por lo tanto, su dual, que es (después de un poco de limpieza) $$ \max_{x,y,\mathbf q} \{ x-y : \langle \mathbf p_i, \mathbf q\rangle \ge x, \langle \mathbf p_j, \mathbf q\rangle \ge x, \langle \mathbf p_k, \mathbf q\rangle \le y \text{ for } k \ne i,j\}, $$ no tiene límites cuando $\mathbf p_i$ y $\mathbf p_j$ forman un borde. Resolver este dual hasta que tengamos $x-y>0$ y luego $\mathbf q$ debe ser una dirección maximizada sólo en $\mathbf p_i$ y $\mathbf p_j$ .

Esta respuesta no supone ninguna simetría, pero sí requiere que todos los puntos $\mathbf p_1, \dots, \mathbf p_n$ para ser puntos extremos, como se señala en los comentarios.