Diámetro mínimo

Question

Tengo una cerrada delimitada convexidad en $\mathbb{R}^3$. Quiero calcular lo que yo llamaría el diámetro mínimo: encontrar el avión (o, en general, el espacio de codimension 1) que minimiza la distancia máxima entre los puntos de la forma en el plano, luego tomar distancia máxima. Supongo que uno debe tomar el supremum si el conjunto no es cerrado.

¿Cómo puedo encontrar esto de manera eficiente? Y es que hay un estándar nombre para él? Parece demasiado obvio para ser sin nombre.

Estoy particularmente interesado en el caso de que la forma es una sección cónica o de lo contrario, definido por de bajo grado del polinomio desigualdades.

Answer 1

Un algoritmo para esto fue descrito en 1988 papel, "Cálculo de la Anchura de un Conjunto" por Michael Houle y su entonces asesor, Godfried Toussaint (CiteSeer enlace; IEEE journal enlace). Su algoritmo se ejecuta en $O(n^2)$ tiempo para un poliedro de $n$ vértices, o más precisamente, en $O(n+I)$ el tiempo, donde el $I$ es el número de antipodal borde de pares. Que demostrar un teorema de la caracterización de los planos paralelos que puedan darse cuenta de la anchura, que conduce a esta hora de la complejidad.