A part of ORCA local avoidance collision is calculating a linear program with an incremental approach - adding the constraints one by one. If the problem is determined to be infeasible, the constraints $g_i(x) \leq 0$ are relaxed, and we could instead solve the problem of
$\min_{x,d} d$
$g_i(x) -d \leq 0, \forall i$
However, I don't really understand the approach to how this is done here (which corresponds to the above mentioned problem when $x$ is two dimensional), in the function linearProgram3, line 518:
https://github.com/snape/RVO2/blob/main/src/Agent.cpp
The method there seems to directly convert the 3d problem to a 2d one, using the lines where $d$ is the same for both lines. A quick summary of my understanding of what happens:
Suppose we have three oriented lines that form a triangle and assume the "normals" (suppose they are pointing in the direction of feasibility, not outside of it) point outside and so the problem is infeasible. The algorithm would see that once it adds the constraint of $l_3$, the problem is infeasible, and use a different approach. It does the following: For $l_1$ and $l_2$ we create lines $\tilde{l_1}, \tilde{l_2}$ where $\tilde{l_1}$ passes through the intersection point of $l_1$ and $l_3$, and it bisects the angle between $l_1$ and $l_3$. Similarly for $l_2$. Then,
$\min_{x,d} d$, where $\tilde{g(l_1)}(x) \leq 0$, $\tilde{g(l_2)}(x) \leq 0$
is solved. In the inequality above, $\tilde{g(l_1)}(x)$ corresponds to the constraint of $x$ being on the "correct" side of $\tilde{l_1}$.
I can intuitively see that this approach will work, but I'm not able to justify it formally. Would someone please explain why it will work, or perhaps refer me to a text that would explain this technique?