Círculo mínimo que contiene un conjunto de puntos

Question

Supongamos que hay $n$ puntos en el plano $x_1, x_2, \dots x_n$ y $C$ es el círculo mínimo (el círculo de radio mínimo) que los contiene a todos. Si hay otro punto $p$ fuera de $C$ Entonces, ¿cómo se puede demostrar que $p$ se encuentra en el círculo mínimo que contiene $x_1, \dots , x_n, p$ ? Parece muy intuitivo, pero no encuentro la forma de probarlo... ¿Alguna ayuda?

Answer 1

Dejemos que $D$ sea el disco delimitado por el círculo que minimiza el radio $\partial D = C\{{x_1, \dots, x_n\}}$ . Dos resultados, $p \in D$ o $p \notin D$ .

Si $p \notin C\{x_1, \dots, x_n, p\}$ entonces $p$ está dentro del disco $D$ limitado por $C\{{x_1, \dots, x_n\}}$ . Pero asumimos $p \notin D$ .

---

Esta es una instancia del problema de Appolonius . Por inducción, buscamos el círculo más pequeño $C_1 = C\{x_1, \dots, x_n, p\}$ que contiene $p$ y $C_0 = C\{{x_1, \dots, x_n\}}$ .

Si $p$ no está dentro de $C_0$ entonces $C_1$ debe ser tangente $C_0$ y pasar por $p$ . Para este caso del problema de Appolonius, en realidad se necesita dos puntos para especificar un círculo único.

En otras palabras, hay infinitos círculos $C_1$ de paso $p$ y tangente a $C_0$ . Uno de ellos tiene el radio más pequeño.

---

Lo anterior no es del todo cierto... en lugar de $C_1$ siendo tangente a $C_0$ y $p$ , sólo $C_1$ pasa por $p$ y su tangente al casco convexo, $\overline{\{x_1, \dots, x_n \}}$ .

Lema El diámetro del círculo mínimo es el mismo que el diámetro del casco convexo El círculo minimizador corta al menos tres puntos del conjunto. Genéricamente, exactamente 3.

El círculo tiene que rodear todos los puntos para que el diámetro sea al menos el del casco convexo, pero puede ser mayor. Si el círculo mínimo no pasa por ningún punto, podemos reducir el radio para que pase por al menos uno. De hecho, como 3 puntos determinan un círculo, podemos encoger el radio hasta que pase por al menos 3. Genéricamente, no debería haber un cuarto punto exactamente en el círculo.

Así que podemos recorrer todos $\binom{n}{3}$ triples de puntos, comprueba que la circunferencia contiene todos los demás puntos, y encuentra el de menor radio. Para la inducción, adjuntamos $p$ e iterar a través del $\binom{n+1}{3}$ puntos.

---

Encontré el gráfico en un curso de postgrado de Ciencias de la Computación, sobre el " Círculo de encierro mínimo " problema. Wikipedia llama a esto el " Problema del círculo más pequeño " y lo atribuye al matemático James Joseph Sylvester . Esta pregunta también se hizo en el sitio de programación StackOverflow:

• https://stackoverflow.com/questions/4901535/smallest-circle-which-covers-given-points-on-2d-plane
• ¿Es ésta una solución errónea al problema del círculo más pequeño?

Era una tarea de informática para estudiantes de segundo año en Princeton ( Cos 226 ) La literatura apunta a una solución rápida de Emo Welzl. El documento se llama Discos más pequeños que encierran (bolas y elipsoides)

---

Propuesta el círculo que minimiza el radio es único

Por contradicción, si tenemos dos círculos $C, C'$ que contienen todos los $n$ puntos, estos puntos deben estar en la intersección de los dos círculos $C \cap C'$ . La intersección de estos dos círculos es un lente forma con un diámetro menor que el de $C$ o $C'$ .

Este diámetro determina un círculo que todavía contiene todos los $n$ puntos, pero con un diámetro menor que el de $C$ o $C'$ .

Answer 2

Es así porque estos son círculos . Se conoce el centro y el radio de C. Trazar una perpendicular desde el punto exterior p al círculo $C$ con un diámetro $\phi_C$ . Sea esta distancia exterior a lo largo de la normal $d$ .

El nuevo diámetro mínimo del círculo que contiene el punto $p$ y $C$ es $ \phi_C + d $ porque la longitud de la línea $d$ se añade a lo largo del diámetro de C.

Answer 3

Para cualquier conjunto de puntos diferentes $x$ el casco circular (el círculo mínimo que contiene todos los puntos) de $x$ es igual al casco circular de un subconjunto de $x$ , ese subconjunto que tiene exactamente $2$ o $3$ puntos. Puede haber múltiples subconjuntos, pero hay al menos $1$ .

Entonces hay exactamente $1$ punto $c$ que es equidistante $r$ de aquellos $3$ puntos (o el punto medio de $2$ puntos). Este $c$ es el centro del casco circular.

Todos los demás puntos tienen una distancia a $c$ que es menor o igual que $r$ . La pregunta supone que la distancia de $p$ a $c$ es mayor que $r$ .

$x \cup \{p\}$ también tiene un subconjunto de $2$ o $3$ puntos que determina su casco circular.

La afirmación es que todo subconjunto de puntos que tenga el mismo casco circular que $x \cup \{p\}$ debe contener $p$ .

Considere una $y$ tal que : $y \subseteq x$ , $|y| = 3$ o $|y| = 2$ , $p \not \in y$

Si eso $y$ formó un casco circular de $x \cup \{p\}$ entonces también forma un casco circular de $x$ . Pero en el primer caso, la distancia de $p$ al centro es menor que el radio del casco circular y en este último caso contradice la suposición de que $p$ está fuera del casco circular de $x$ .

Así que todos esos $y$ no puede ser un casco circular de $x \cup \{p\}$ por lo que todos los subconjuntos de puntos que determinan el casco circular de $x \cup \{p\}$ debe contener $p$ .