0
$\begingroup$

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.
$\endgroup$

1 Answer 1

0
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – Grigori
    Oct 4, 2023 at 18:50
  • $\begingroup$ @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. $\endgroup$
    – D.W.
    Oct 5, 2023 at 5:35

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.