enésimo punto más cercano con coordenadas enteras a un punto dado

Question

Intento encontrar el enésimo punto más cercano a un punto dado en 2 dimensiones. El punto dado puede tener cualquier coordenada, pero el resultado debe tener coordenadas x e y que sean enteras.

Es posible hacerlo encontrando todos los puntos dentro de un radio de n (en realidad $\sqrt n$ o algo así), construyendo un montón y buscando los n puntos más cercanos, pero ¿hay una manera más rápida de hacer esto? No necesito los n puntos más cercanos, sólo el enésimo más cercano.

Answer 1

Si sólo quiere el $n^{\text{th}}$ punto más cercano, la mejora obvia que hay que hacer es seguir tomando la $\mathcal O(n)$ puntos de distancia $\sqrt n$ del punto dado, pero luego utilizar un algoritmo de selección en tiempo lineal (por ejemplo Quickselect ) para elegir el $n^{\text{th}}$ valor.

Además, podemos utilizar el hecho de que un círculo de radio $r$ con centro entero contiene aproximadamente $\pi r^2$ puntos enteros, con un error que Gauss delimitó por $2\sqrt2 \pi r$ (el Problema del círculo de Gauss ) y para el que ahora tenemos unos límites ligeramente mejores.

Así que podemos, con bastante precisión, elegir una región circular que esté garantizada para tener $n$ puntos enteros en él: por ejemplo, la unión de cuatro círculos centrados en los cuatro puntos enteros más cercanos al punto dado, con radio $r$ tal que $\pi r^2 - 2\sqrt2 \pi r > n$ . También podemos, de forma similar, encontrar una región más pequeña que esté garantizada no contienen el $n^{\text{th}}$ punto más cercano, dejando probablemente $\mathcal O(\sqrt n)$ más o menos los puntos de los candidatos.

Desgraciadamente, aunque esto puede acelerar nuestra búsqueda, no lo hará por debajo de $\mathcal O(n)$ complejidad del tiempo, porque todavía tenemos que averiguar exactamente cuántos puntos de la región más pequeña estamos desechando antes de poder clasificar los puntos realmente viables.

Pero si pudiéramos contar exactamente el número de puntos enteros en un círculo de radio $r$ (incluso podemos suponer que tiene centro entero) en el tiempo $o(r^2)$ Entonces podríamos utilizar esta idea para acelerar aún más el algoritmo.