Menor de la elipse por el área de encerrar 2D puntos

Question

Estoy interesado en escribir un algoritmo que, para un conjunto dado de $n$ puntos en $\mathbb{R}^2$, encuentra la ecuación de la elipse más pequeña por la zona para encerrar a todos los $n$ puntos. Aquí estoy yo:

La ecuación general de una elipse es $Ax^2+Bxy+Cy^2+Dx+Ey-1=0$. Esta elipse tiene área de $\frac{2\pi}{\sqrt{4AC-B^2}}$ y por definición satisface $4AC-B^2>0$. Por lo tanto, para minimizar el área de esta cónica, podemos minimizar el valor escalar de la función $\phi(x)=B^2-4AC$.

Voy a simplificar esta cuestión a destacar la parte que no entiendo. Imaginemos ahora que tenemos sólo 3 puntos que necesita ser incluido en la elipse, (1,1), (1,5), (7,3). Porque sólo hay 3 puntos, podemos asumir el menor de la elipse iba a pasar a través de todos los 3, y ahora tenemos una ecuación cuadrática problema de optimización bajo restricciones de igualdad como sigue:

$$\min_{x}\phi(x)=B^2-4AC$$

s.t.

$$c_{1}(x) = A+B+C+D+E-1=0$$ $$c_{2}(x)=A+5B+25C+D+5E-1=0$$ $$c_{3}(x)=49A+21B+9C+7D+3E-1=0$$

donde $x = $ $[A$ $B$ $C$ $D$ $E]^{T}$

El uso de multiplicadores de Lagrange, hemos de Lagrange

$$\mathcal{L}(x,\lambda) = \phi(x)-\lambda_{1}c_{1}(x)-\lambda_{2}c_{2}(x)-\lambda_{3}c_{3}(x)$$

Nosotros ahora nos preparamos $\nabla_{x}\mathcal{L} = 0$ e $\nabla_{\lambda}\mathcal{L} = 0$. Estas condiciones (KKT) producen un 8 x 8 sistema lineal. Tediosamente, aquí está:

$$\begin{bmatrix} 0 &0 &4 &0 &0 &1 &1 &49 \\ 0 &-2 &0 & 0 &0 &1 &5 &21\\ 4 &0 &0 &0 &0 &1 &25 &9\\ 0 &0 &0&0&0&1&1&7\\ 0 &0&0&0&0&1&5&3\\ 1&1&1&1&1&0&0&0\\ 1&5&25&1&5&0&0&0\\ 49&21&9&7&3&0&0&0\\ \end{bmatrix} \begin{bmatrix} A\\ B\\ C\\ D\\ E\\ \lambda_{1}\\ \lambda_{2}\\ \lambda_{3}\\ \end{bmatrix} = \begin{bmatrix} 0\\0\\0\\0\\0\\1\\1\\1\\ \end{bmatrix}$$

Este es el equivalente del punto de silla de la matriz, y es nonsingular. Creo que esto tiene sentido debido a que razonablemente debería haber sólo una pequeña elipse, que encierra los 3 puntos dados.

El problema es que la solución a este sistema lineal produce un Langrange multiplicador que es negativo, y la totalidad de la solución cuando se trazan es obviamente erróneo. Así que aquí están mis preguntas:

1) Soy la configuración de este problema correctamente?

2) Si 1) = sí, ¿qué es una interfaz intuitiva explicación de por qué este método no produce una solución factible.

3) ¿Qué método te recomiendo, teniendo en cuenta que esta es una versión simplificada del problema? El objetivo final será el de encontrar la elipse que se encierre $n$ puntos, que se va a producir una ecuación cuadrática problema de optimización bajo restricciones de desigualdad.

Cualquier ayuda es muy apreciada. Muchas gracias chicos.

Answer 1

• Área de un triángulo con vértices en excéntricas ángulos $\alpha$, $\beta$ e $\gamma$ es

  $$\Delta=2ab \left | \sin \frac{\alpha\beta}{2} \sin \frac{\beta\gamma}{2} \sin \frac{\gamma\alpha}{2} \right |$$

• El triángulo del área es máxima cuando $\alpha-\beta=\beta-\gamma=\pm 120^{\circ}$, que es

  $$\Delta=\frac{3\sqrt{3}}{4}ab$$

• Tenga en cuenta que

  $$\sin x+\sin (x+120^{\circ})+\sin (x+240^{\circ})=0$$

  $$\cos x+\cos (x+120^{\circ})+\cos (x+240^{\circ})=0$$

  el centroide $G$ para la máxima triángulo es un invariante que es el centro de la elipse.

• Deje $\boldsymbol{u}=\vec{GA}$, $\boldsymbol{v}=\vec{GB}$, $\boldsymbol{w}=\vec{GC}$, los vectores columna de la semi-ejes ser $\boldsymbol{\lambda}$ e $\boldsymbol{\mu}$.

  Ahora

  \begin{align} \boldsymbol{0} &= \boldsymbol{u}+\boldsymbol{v}+\boldsymbol{w} \\[5pt] \boldsymbol{u} &= \boldsymbol{\lambda} \cos (\theta-60^{\circ})+ \boldsymbol{\mu} \sin (\theta-60^{\circ}) \\[5pt] \boldsymbol{v} &= \boldsymbol{\lambda} \cos (\theta+60^{\circ})+ \boldsymbol{\mu} \sin (\theta+60^{\circ}) \\[5pt] \boldsymbol{\lambda} &= \frac{2[\boldsymbol{u}\sin (\theta+60^{\circ})- \boldsymbol{v}\sin (\theta-60^{\circ})]}{\sqrt{3}} \\[5pt] \boldsymbol{\mu} &= \frac{2[\boldsymbol{v}\cos (\theta-60^{\circ})- \boldsymbol{u}\cos (\theta+60^{\circ})]}{\sqrt{3}} \\[5pt] 0 &= \boldsymbol{\lambda} \cdot \boldsymbol{\mu} \\[5pt] 0 &= \boldsymbol{u} \cdot \boldsymbol{v} \sin 2\theta- \frac{u^2}{2} \sin (2\theta+120^{\circ})- \frac{v^2}{2} \sin (2\theta-120^{\circ}) \\[5pt] \tan 2\theta &= \frac{u^2-v^2}{u^2+4\boldsymbol{u} \cdot \boldsymbol{v}+v^2} \sqrt{3} \end{align}

• También tenga en cuenta que

  \begin{align} \boldsymbol{u} \times \boldsymbol{v} &= \frac{\sqrt{3}}{2} \boldsymbol{\lambda} \times \boldsymbol{\mu} \\[5pt] |\boldsymbol{u} \times \boldsymbol{v}| &= \dfrac{2\Delta}{3} \\[5pt] A_{\text{min}} &= \pi \lambda \mu \\[5pt] &= \frac{2\pi}{\sqrt{3}} |\boldsymbol{u} \times \boldsymbol{v}| \\[5pt] &= \dfrac{4\pi \Delta}{3\sqrt{3}} \\[5pt] \end{align}

• La (columna) ecuación vectorial para la central cónicas está dada por

  $$\boldsymbol{x}^T \mathbb{M} \, \boldsymbol{x}=1$$

  $$\mathbb{M}^{-1}= \begin{pmatrix} \boldsymbol{\lambda} & \boldsymbol{\mu} \end{pmatrix} \begin{pmatrix} \boldsymbol{\lambda}^T \\ \boldsymbol{\mu}^T \end{pmatrix}$$

Actualizaciones

El menor de la elipse es también conocido como Steiner circumellipse.

El Steiner inellipse tiene el área máxima de cualquier inellipse.

El Steiner inellipse es la mitad de la de Steiner circumellipse sobre el centro de gravedad del triángulo.

Si $\alpha$, $\beta$, $\gamma \in \mathbb{C}$ son los vértices del triángulo y dejar

$$f(z)=(z-\alpha)(z-\beta)(z-\gamma)$$

entonces por Marden's_theorem los focos de la Steiner inellipse está dada por

$$ f'(c)=0 \implica c=\frac{\alpha+\beta+\gamma}{3} \pm \frac{\sqrt{\alpha^2+\beta^2+\gamma^2- \beta \gamma\gamma \alpha\alpha \beta}}{3}$$

La duplicación de la distancia focal de inmediato da los focos de interés para el Steiner circumellipse que son

$$\frac{\alpha+\beta+\gamma}{3} \pm \frac{2\sqrt{\alpha^2+\beta^2+\gamma^2- \beta \gamma\gamma \alpha\alpha \beta}}{3}$$

Ver también el artículo aquí por su interés.

Answer 2

Ver estos artículos y las referencias en él:

• B. Gärtner, S. Schönherr, Más pequeño que Encierra Elipses - de forma Rápida y Exacta

• B. Gärtner, S. Schönherr, Más pequeño que Encierra Elipses - Una Exacta y la Implementación Genérica