Matching points on a plane with maximum total weight

Question

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.

Answer 1

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.

• Grigori: D.W., thank you for sharing this thought. I do not fully understand, how to set constraints here... Because we need to ensure, that for those vectors that we will draw, any vertical line intersects vectors of total weight <= 1. How can we write such a constraints?
• D.W.: @Grigori, for each vertical line, enumerate all possible vectors that intersect that line; the sum of their weights must be <= 1, which is a linear inequality on the weights (unknowns). Every vector with non-zero weight is drawn. Zero weight means that the vector is not drawn.