2
$\begingroup$

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!

$\endgroup$
4
  • $\begingroup$ The answer surely depends on the structure of your set of points. Are any metric/topological properties of it known? $\endgroup$ Aug 16, 2010 at 13:17
  • $\begingroup$ 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... $\endgroup$
    – Lars Kanto
    Aug 16, 2010 at 13:36
  • 1
    $\begingroup$ 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. $\endgroup$
    – j.c.
    Aug 16, 2010 at 15:37
  • $\begingroup$ Oh, I see -- "nearest neighbor", yes. $\endgroup$
    – Lars Kanto
    Aug 16, 2010 at 19:52

3 Answers 3

2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
0
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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