Topological scaling (?)

Question

Say there is a 2D plane (square) with some points inside it.

How to move all the points in such a way that they fill the plane as evenly as possible but every point maintains its neighbors?

In other words, I want the points to be as far from each other as possible but their locality (topology) should be preserved and they should lay in the square.

In other words, I want to kind of zoom-in in the rich-point-populated area and zoom-out in the empty areas.

PS: is there a general solution for higher-dimension spaces? Is there a direct solution or only iterative one?

Edit:

Now what, three great answers but I can accept only one. Thank you all!

Answer 1

The naive approach would be to write down the variance for the pairwise distances as a function of the coordinates of the points and do a gradient descent to spread them out evenly. You probably want to limit which pairwise distances you consider: it might suffice to take, for each point, its three closest neighbors. To spread things out evenly within a square, include the corners and perhaps evenly spaced points on the boundary in your calculation, but don't move them. The strategy would be the same in higher dimensions, but with more neighbors included.

Answer 2

A closely related problem is the creation of cartograms: maps where areas are distorted to show some data dimension other than actual geographical area. Nice examples can be seen at WorldMapper.

There's a large set of algorithms that have been proposed, which you can find by googling "cartogram." But the most effective I've seen (and the one used at WorldMapper) is described by Gastner & Newman (PNAS 2004). The algorithm uses a diffusion analogy, defining a flow from areas of high density to areas of low density.

To get back to your problem, you can actually use this method to create a mapping that moves your points around in a way that, at least visually, equalizes density while preserving neighbor relations. Here's an image from the paper cited above, where the authors took a set of unevenly distributed locations in NY State, and "remapped" the state so they are distributed evenly:

Answer 3

Let $x_i$ be the coordinate of point $i$ and imagine there is an edge $e_{ij}$ between any pair of neighbors. The optimization problem

$$\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}$$

is a strongly convex optimization problem (namely, a linearly constrained quadratic program or LCQP), hence it has a unique global minimum. Hence, the solution can be computed in polynomial time using an interior point method such as the barrier method. In fact, box-constrained quadratic programs can be solved quite efficiently and implementations are readily available (in MATLAB, for instance). In order to avoid trivial solutions, imagine that some of the $x_i$ are constrained to lie on the boundary, e.g., you can either add constraints like $x_i^1=1$ (where the superscript denotes the component) or simply hold some of the $x_i$ fixed.

Note that this problem attempts to minimize the pairwise distance rather than maximize it. On a compact domain the two problems will yield similar results, but the latter problem is nonconvex and hence it is harder to make guarantees about global optimality.