Círculo de cerramiento máximo de un radio dado

Intento encontrar un enfoque para el siguiente problema:

Dado el conjunto de puntos y el radio , encuentre el punto central del círculo, de modo que el círculo contenga el número máximo de puntos del conjunto. El tiempo de ejecución debe ser .r O ( n 2$S$$r$$O(n^2)$

Al principio parecía ser algo similar al problema del círculo cerrado más pequeño, que se puede resolver fácilmente en $O(n^2)$ . La idea era establecer un centro arbitrario y rodear todo punto de $S$ . Luego, paso a paso, reemplace el círculo para tocar los puntos más a la izquierda / derecha y reduzca el círculo al radio dado, obviamente, esto no va a funcionar.

No sé cómo resolver este problema en el tiempo $O(n^2)$ , pero existe un algoritmo $O(n^2\log n)$ .

Sea $C(s_i)$ el círculo cuyo centro es $s_i$ , el punto $i$ , con radio $r$ . No es difícil encontrar que el conjunto de puntos $P = \{p_0, p_1, \ldots, p_m\}$ puede estar encerrado en un círculo con radio $r$ si la intersección $I(P)$ de $C(p_0), C(p_1), \ldots, C(p_m)$ no está vacío. Además, si $I(P)$ no está vacío, debe haber algunos puntos en $I(P)$ en algún $\textbf{bd}C(p_i)$ (el límite de $C(p_i)$ ). Entonces, para cada $C(s_i)$ y cada punto $p$ en su bondary, tratamos de encontrar cuántos círculos contienen$p$ . La cuenta máxima entre todos los $p$ será la respuesta a este problema.

Examinemos los puntos en $\textbf{bd}C(s_i)$ . Hay un mapeo uno a uno entre los puntos en $\textbf{bd}C(s_i)$ y el número real en $[0, 2\pi)$ . Para cada círculo $C(s_j)$ , la intersección entre $C(s_j)$ y $\textbf{bd}C(s_i)$ se puede representar mediante un intervalo $[begin_j, end_j]$ . Entonces, para todos los círculos que no sean $C(s_i)$ , existen a lo sumo intervalos $n-1$ (algunos círculos pueden no cruzarse con $C(s_i)$ ). El recuento máximo se puede encontrar fácilmente clasificando los $2(n-1)$ puntos finales del intervalo (n-1) , escaneándolos en orden y contando el número superpuesto actual. Para cada$C(s_i)$ , este paso se puede hacer en $O(n\log n)$ tiempo, y hay $n$ tales círculos, por lo que la complejidad temporal de este algoritmo es $O(n^2\log n)$ .

Creo que la pregunta difícil es saber si el círculo que ha seleccionado es realmente "máximo" dentro del conjunto. La única forma en que puedo pensar para determinar esto es probar todas las combinaciones posibles de los puntos y probar el tamaño del círculo que los encierra.

Sin embargo, puede reducir el espacio de búsqueda dividiendo primero el espacio de puntos en una cuadrícula de celdas cuadradas con ancho 2r. Luego ubique la celda con la mayor densidad. Como ya ha localizado un círculo de X puntos, puede concluir que si existe un círculo con más puntos, entonces debe tener al menos X puntos en él. Y use esto como punto de partida para probar las diferentes combinaciones de los puntos.

Si solo está buscando un conjunto de puntos que es probable que sea máximo, entonces podría reducir aún más la cantidad de combinaciones que necesita probar seleccionando aquellos puntos que se encuentran dentro de un vecindario de celdas donde la densidad del vecindario es mayor que X.

Dicho esto, ambas "reducciones" pueden fallar y, en el peor de los casos, calculará círculos para todas las combinaciones posibles de puntos.

En Chazelle, B .; Lee, el artículo de DT Computing 36, 1-16 (1986), teorema 3 en la página 15, afirma que el algoritmo de búsqueda de círculo de cierre máximo requiere un costo de tiempo .$O(n^2)$

Creo que la clave sigue siendo el algoritmo de construcción del gráfico de intersección que menciona antes (o vea Edelsbrunner, H. (1987), Algorithms in Combinatorial Geometry, capítulo 7). Posteriormente, el hallazgo máximo del círculo de cierre debe ser sencillo.$O(n^2)$

Aparentemente, este problema es equivalente a encontrar el punto cubierto por el número máximo de círculos dados y es fácil saber que aquellos que en su mayoría puntos intersectados por n círculos deben considerarse candidatos. (Esto también lleva a un algoritmo directamente) O ( n 2 l o g ( n ) $2n^2$$O(n^2log(n))$

Sin embargo, al utilizar el algoritmo de construcción mencionado anteriormente , también conduce un algoritmo para este problema. Porque el gráfico de intersección construido con vértices como puntos de intersección y aristas como arcos es un gráfico plano de Euler. Entonces uno puede recorrer todos los arcos a través de un ciclo de Euler y un orden de arcos indexados por los índices de círculos a los que pertenece e información de si algún arco es un "arco que se aleja" (curvado hacia atrás) o "que entra en el arco" ( curvado hacia adelante) para el vértice encontrado durante el recorrido en el que este arco incide se registrará.O ( n 2$O(n^2)$$O(n^2)$

Según el teorema de Jordan, un vértice de intersección está encerrado por un círculo solo si se encuentra primero con un "arco de separación" que pertenece a ese círculo o si tiene un arco incidente que pertenece a ese círculo. Entonces, después de todo el viaje, se puede encontrar fácilmente el círculo de cierre máximo. Es similar al caso de decidir los tiempos de cobertura para puntos con intervalos ordenados a lo largo de una línea recta (o es decir, la versión 1D de este problema de cierre), excepto que el viaje ya ha dado la orden. Mientras que según el formulario de Euler para un gráfico plano, el número total de arcos es lineal con el número de vértices, y dado que no es necesario registrar nuevamente la información relacionada cuando se viaja de regreso a los vértices ya visitados, por apretón de manos lema, el costo total del tiempo será .O ( n 2$V + E - F = 2$$O(n^2)$