# Matching points on a plane with maximum total weight

I have a set of points $$P = \{p_1, \dots, p_m \}, \; 0 \le m \le 10^4$$ on a plane of two colors (red and green). Each point has integer x-coordinate (all x-coordinates are different), and non-negative y-coordinate (y-coordinate can be non-integer). In addition, each point has a weight $$w \in \mathbb{R}^+$$.

I can match two points only of different colors $$p_1 = (x_1, y_1, w_1)$$ and $$p_2 = (x_2, y_2, w_2)$$ with a vector $$v = \vec{p_1 p_2}$$ of any weight $$0 \le w \le min(w_1, w_2)$$, if $$x_1 < x_2$$. This vector will be assigned with a value

$$f_v = w \frac{y_1 - y_2}{y_1}$$, if $$p_1$$ is green, and $$-f_v$$ vice versa.

Problem:

What is an algorithm to find a set of vectors $$V = \{ v_1, \dots, v_s \}$$ (described above) with proper weights $$w_1, \dots, w_s$$, that will maximize total value of $$F = \sum_{v \in V} f_v$$?

Constraints:

1. Sum of weights of outgoing and incoming vectors (together) for each point should be less or equal than the weight of this point.

2. For each horizontal line $$x=val$$, total weight of vectors that are intersected by this line is $$\le 1$$.

Methods:

1. I was thinking about dynamic programming approach, where I will calculate the max value of $$F$$ for each $$i \le m$$, but it doesn't support floating weights $$w$$ of vectors.

This can be expressed as an instance of linear programming and then solved with a LP solver. The unknowns are the weights on all possible vectors (at most $$\sim m^2/2$$ of them), the constraints provide linear inequalities, and the objective function to maximize is a linear function of the unknowns.