Take the 2-minute tour ×

So I'm trying to solve this problem.

We are given an image ( a two dimensional matrix ). The image is all white except for some red dots. We are given the list of the red dots ( (X,Y) pairs ). The red dots have an even geographic distribution across the image :-)

We are given a list of locations where we can place some blue dots. This list has N elements ( (X,Y) pairs ).

The problem is to place M blue dots ( M < N ) in such a way that : the blue dots are geographically distributed across the image ( let's say 25% in the upper left side , 25% in the upper right side etc....) , as far away as possible from the red dots , as far away as possible from each other.

How would I go about finding the best possible M out of N ? Does this problem have a mathematical solution or do I just have to get all possible combinations and see which one is best ?

Cheers !!

share|improve this question
linear programming is defined as problem when you want to maximize or minimize somthing when given some set of constraints.stackoverflow.com please ask there.it is combinatoric problems maybe graph theory.or dynamic programming –  dato datuashvili Apr 7 '13 at 6:25

2 Answers 2

You didn't give an exact formulation of the problem, so my answer will be not exact too.

In your problem you have to optimize some functions (most likely, a sum) of distances between blue/red/white dots. As the distance you most likely choose either $$\sum_{i,j}[(x_i-x_j)^2+(y_i-y_j)^2]$$ or $$\sum_{i,j}[|x_i-x_j|+|y_i-y_j|]$$ or something else (for example, $\sum_{i,j}\sqrt{(x_i-x_j)^2+(y_i-y_j)^2}$ ). Anyway you have to use methods of non-linear and discrete programming, but not linear one.

share|improve this answer

Let $x_j, j = 1 \ldots N$ be binary variables, where $x_j = 1$ or $0$ is interpreted as "place (or do not place, respectively) a blue dot at position #$j$". Then you might formulate an integer linear programming problem. For example, you could have a constraint $x_i + x_j \le 1$ to indicate that positions $i$ and $j$ are too close to place blue dots at both.

It's not really "linear programming" because of the restriction that $x_j \in \{0,1\}$.

share|improve this answer

Your Answer


