Escalado topológico (?)

Question

Digamos que hay un plano 2D (cuadrado) con algunos puntos en su interior.

¿Cómo mover todos los puntos de forma que llenen el plano lo más uniformemente posible pero que cada punto mantenga sus vecinos?

En otras palabras, quiero que los puntos estén lo más alejados posible unos de otros, pero que se mantenga su localidad (topología) y que estén en el cuadrado.

En otras palabras, quiero acercarme a la zona poblada de puntos ricos y alejarme de las zonas vacías.

PD: ¿existe una solución general para espacios de mayor dimensión? ¿Existe una solución directa o sólo iterativa?

Editar :

Ahora que, tres grandes respuestas pero solo puedo aceptar una. Gracias a todos.

Answer 1

El enfoque ingenuo consistiría en escribir la varianza de las distancias entre pares en función de las coordenadas de los puntos y realizar un descenso de gradiente para repartirlas uniformemente. Probablemente querrás limitar las distancias por pares que consideras: podría ser suficiente tomar, para cada punto, sus tres vecinos más cercanos. Para distribuir las cosas uniformemente dentro de un cuadrado, incluya en el cálculo las esquinas y, quizá, los puntos uniformemente espaciados del límite, pero no los mueva. La estrategia sería la misma en dimensiones superiores, pero con más vecinos incluidos.

Answer 2

Un problema estrechamente relacionado es la creación de cartogramas mapas en los que las áreas están distorsionadas para mostrar alguna dimensión de datos distinta de la zona geográfica real. En WorldMapper .

Hay un gran conjunto de algoritmos que se han propuesto, que puedes encontrar googleando "cartograma". Pero el más eficaz que he visto (y el que se utiliza en WorldMapper) es el descrito por Gastner y Newman (PNAS 2004) . El algoritmo utiliza una analogía de difusión, definiendo un flujo desde zonas de alta densidad a zonas de baja densidad.

Volviendo a tu problema, puedes utilizar este método para crear una cartografía que desplace los puntos de forma que, al menos visualmente, se iguale la densidad y se mantengan las relaciones de vecindad. He aquí una imagen del artículo citado anteriormente, en el que los autores tomaron un conjunto de ubicaciones distribuidas de forma desigual en el estado de Nueva York, y "remapearon" el estado para que se distribuyeran uniformemente:

Answer 3

Sea $x_i$ sea la coordenada del punto $i$ e imagina que hay un borde $e_{ij}$ entre cualquier par de vecinos. El problema de optimización

$$\begin{array}{rl} \underset{x}{\mathrm{argmin}} & \displaystyle\sum_{e_{ij}} \left( x_j - x_i \right)^2 \\ \mathrm{s.t.}\ 0 \leq x_i \leq 1 \end{array}$$

es un problema de optimización fuertemente convexo (es decir, un programa cuadrático linealmente restringido o LCQP), por lo que tiene un mínimo global único. Por tanto, la solución puede calcularse en tiempo polinómico utilizando un método de puntos interiores como el método de la barrera. De hecho, los programas cuadráticos con restricciones de caja pueden resolverse de forma bastante eficiente y existen implementaciones disponibles (en MATLAB, por ejemplo). Para evitar soluciones triviales, imaginemos que algunas de las $x_i$ se limitan a situarse en el límite, por ejemplo, puede añadir restricciones como $x_i^1=1$ (donde el superíndice denota el componente) o simplemente mantener algunos de los $x_i$ arreglado.

Tenga en cuenta que este problema intenta minimizar la distancia entre pares en lugar de maximizarla. En un dominio compacto, los dos problemas arrojarán resultados similares, pero este último no es convexo y, por tanto, es más difícil garantizar la optimalidad global.