Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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!

share|improve this question
    
The answer surely depends on the structure of your set of points. Are any metric/topological properties of it known? –  Victor Protsak Aug 16 '10 at 13:17
    
Ehm, not sure if I understood... The points are just coordinates in that space (XY pairs in a plane), they are like some samples or data points, the distance could be basic Euclidean one... –  Lars Kanto Aug 16 '10 at 13:36
    
I'll elaborate on Victor Protsak's question. When you say "every point maintains its neighbors" it sounds like there is some kind of graph structure on your points - how are you defining this? My guess would be you are using the "nearest neighbor" structure from the initial placement of the points. –  j.c. Aug 16 '10 at 15:37
    
Oh, I see -- "nearest neighbor", yes. –  Lars Kanto Aug 16 '10 at 19:52
add comment

3 Answers

up vote 2 down vote accepted

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.

share|improve this answer
add comment

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:

cartogram example

share|improve this answer
    
+1 for the picture! –  Somnath Basu Aug 16 '10 at 17:36
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.