¿Cuál es el mejor algoritmo para encontrar el número máximo de puntos 2D (de un conjunto dado) que puede encerrar un rectángulo alineado a un eje de un tamaño determinado?

Answer 1

Supongo que el rectángulo debe ser paralelo al eje. De lo contrario, parece que las cosas se ponen un poco más complicadas.

Es más fácil comenzar resolviendo la versión dinámica de este problema en 1 dimensión. Para hacerlo, necesita una estructura de datos que pueda soportar las siguientes operaciones en tiempo O (log N)

1) Insertar un punto
2) Eliminar un punto
3) Encuentre el número máximo de puntos en algún rango de longitud a (donde ‘a’ es una constante)

La versión dual de estas operaciones es más fácil de implementar directamente. En lugar de insertar / eliminar un punto, debería admitir sumar / restar de un rango de longitud ‘a’. Entonces (3) es solo encontrar el punto máximo. Use su estructura de datos de árbol favorita con actualizaciones diferidas para implementar esto.

Una vez que tenga esta estructura de datos 1D, puede aplicarla para resolver el caso 2D en tiempo O (N log N). Simplemente escanee la primera dimensión con una ventana de tamaño ‘a’. Cada vez que ingresa un nuevo punto en la ventana, agréguelo a la estructura de datos y cuando salga, retírelo de la estructura de datos. La respuesta máxima es el mayor número de puntos en una ventana de tamaño ‘b’ en su estructura de datos en cualquier momento en el algoritmo.

Answer 2

Primero, puede resolverlo en un caso unidimensional utilizando un árbol de intervalos modificado.
En este árbol guardará la siguiente información en cada nodo:

1) ¿Cuántos puntos cubrirá un intervalo de longitud dada si comienza en el extremo derecho del intervalo del nodo?
2) Máximo de 1) de todos los subnodos.

Puede actualizar esta estructura en tiempo O (log n) cada vez que agrega un punto.

Esto lleva a una solución en el caso O (N log N) en el caso 1-D (peor que óptimo), pero en el caso 2-D puede crear un árbol de 2 niveles. En el que los nodos contienen subárboles para el otro eje y un nodo en el árbol dentro de un nodo contiene la siguiente información:

1) ¿Cuántos puntos cubrirá una caja de tamaño dado si su borde superior se especifica como el extremo derecho del intervalo de este nodo y el borde derecho se especifica por el intervalo del nodo primario?

Esto lleva a una solución O (n log ^ 2 n)

Answer 3

Un enfoque fácil nos llega desde los gráficos de computadora: simplemente calcule el cuadro delimitador de todos los puntos.

Iterar en todos los n puntos. Calcule min y max para x e y. Esto le proporciona inmediatamente el cuadro delimitador en [math] O (n) [/ math] time.