0
$\begingroup$

I have a set of line segments that are defined as a connection between two arbitrary points (e.g. $(x_1,y_1)$ and $(x_2,y_2)$). I need to find a line $y=mx+b$ that intersects all the line segments in the set at any one point. I understand linear programming is able to help with this, I am however not sure about the constraints. I believe that if the line segments are e.g. just vertical, a constraint like in this answer could work, but I am uncertain how this can be done if the line segments can have any direction.

I am new to linear programming so please excuse any mistakes in my question.

Thanks in advance

$\endgroup$
4
  • $\begingroup$ Are you sure that the form $y = mx + b$ is the one you want? If you had a bunch of horizontal segments, it might be that only a vertical line would pass through all of them, but such a line cannot be expressed using $y = mx + b$. Can you confirm that you explicitly don't care about this particular situation? $\endgroup$ Commented Nov 9, 2024 at 14:50
  • $\begingroup$ I hadn't thought about that, but let's assume for now that the line segments cannot all be horizontal to circumvent this. But out of curiosity, what form would you recommend if the line segments could all be horizontal? $\endgroup$ Commented Nov 9, 2024 at 14:58
  • $\begingroup$ I'd recommend either Ax + By + C = 0 or (angle, distance). In the second, "angle" is the angle of inclination of the line, between 0 and 180 degrees, and distance is the distance from the line to the origin (0,0). In the first, the case where $B$ is nonzero can be changed to $(A/B)x + y + (C/B) = 0$, which can be rewritten as $y = (-A/B)x + (-C/B)$, which has the form $y = mx + b$. When $B = 0$, we get an equation $Ax + C = 0$, which can be converted to $x = (-C/A)$, which is a vertical line. The case where $A = B = 0$ is not allowed. $\endgroup$ Commented Nov 9, 2024 at 15:16
  • $\begingroup$ The $Ax + By + C = 0$ is slightly annoying, however, because $2x + 3y + 7 = 0$ and $10x + 15y + 35 = 0$ denote the same line (as does any nonzero multiple of this equation). So when you try to find a line in this form, you typically end up with a whole "family" of $(A,B,C)$ triples, all of which denote the same line. $\endgroup$ Commented Nov 9, 2024 at 15:18

1 Answer 1

Reset to default
1
$\begingroup$

Parametrize each line segment $k\in\{1,\dots,n\}$ as \begin{align} x_k &= x_1^k (1-t_k) + x_2^k t_k \\ y_k &= y_1^k (1-t_k) + y_2^k t_k \end{align} where $(x_1^k,y_1^k)$ and $(x_2^k,y_2^k)$ are the endpoints and $0 \le t_k \le 1$. Now the problem is to find $m,b,t_1,\dots,t_n$ such that $y_k=mx_k+b$ for all $k$. That is, minimize $0$ subject to \begin{align} y_1^k (1-t_k) + y_2^k t_k &= m (x_1^k (1-t_k) + x_2^k t_k) + b \tag1\label1 \\ 0 \le t_k &\le 1 \tag2\label2 \end{align} But \eqref{1} is quadratic (not linear) in the decision variables because of the products $m\cdot t_k$. When $x_1^k=x_2^k$ as in the linked question, \eqref{1} becomes linear because the RHS reduces to $m x_1^k + b$.

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.