Dados n puntos, encontrar un algoritmo para obtener una circunferencia que tenga el máximo de puntos.
Respuestas
¿Demasiados anuncios?
Kuifje
Puntos
692
Un posible modelo (no lineal) para este problema:
Defina las siguientes variables :
- $a$ es el $x$ -coordinación del círculo
- $b$ es el $y$ -coordenadas del círculo
- $r\ge0\;$ es el radio del círculo
- $\omega_i$ es una variable binaria que es igual a $1$ si y sólo si el punto $(x_i,y_i)$ se encuentra en el círculo.
La función objetivo es entonces maximizar $$ \sum_{i=1}^n \omega_i $$ con sujeción a $$ (x_i-a)^2+(y_i-b)^2\le r^2 +M(1-\omega_i)\quad \forall i=1,\cdots,n\\ (x_i-a)^2+(y_i-b)^2\ge r^2 -M(1-\omega_i)\quad \forall i=1,\cdots,n\\ r\ge 0\\ \omega_i\in\{0,1\}\quad \forall i=1,\cdots,n\\ $$ $M$ es una gran constante. Este enfoque es sencillo, pero (probablemente) no será eficiente si se trata de muchos puntos.
El método de elección todos los conjuntos de 3 puntos, encontrar el círculo que pasa por ese conjunto y ver qué otros puntos se encuentran en esa circunferencia tiene un gran problema: el error de redondeo.
Si intenta utilizar cualquier método que implique tomar raíces cuadradas, el redondeo puede causar problemas.
Este es un método, basado en un trabajo anterior mío, que permite hacer esto sin ningún error, suponiendo que los puntos tienen todos coordenadas racionales.
Todas las operaciones de se supone que se hacen con aritmética racional exacta.
Haga lo siguiente para todos los conjuntos de tres puntos. Se pueden hacer algunas optimizaciones al llevar la cuenta de cuándo un punto se encuentra en una circunferencia que pasa por un conjunto de tres puntos.
Que los puntos sean $(x_i, y_i), i=1, 2, 3 $ .
Que el círculo sea $(x-a)^2+(y-b)^2 =r^2 $ o $x^2-2ax+y^2-2by =r^2-a^2-b^2 $ o $2ax+2by+c =x^2+y^2 $ donde $c = a^2+b^2-r^2 $ .
Resolver el sistema lineal $2ax_i+2by_i+c =x_i^2+y_i^2 , i=1,2,3 $ para $a, b, c$ exactamente, utilizando la aritmética racional. Si no hay solución, intenta el siguiente trío.
Entonces, para cualquier otro punto $(x, y)$ , comprobar si $2ax+2by+c =x^2+y^2 $ . Si es así, el punto está en el círculo. Como antes, esto se puede hacer exactamente con aritmética racional.
En cada etapa, se mantiene un registro del conjunto de tres puntos que tenga el mayor número de puntos en su círculo.
Si utiliza $O(n^3)$ almacenamiento, se puede hacer un seguimiento de todos los cálculos anteriores.
Al final, tendrás el círculo con más puntos en él.
