Disclaimer: I think I've just figured this out a couple of minutes ago, so some details may be fuzzy.
The formal theory is in Computational Geometry: Algorithms and Applications (2008 <PERSON> et al.), in the Linear Programming chapter.
Just as in 2D linear programming where we know the optimal incremental solution must lie somewhere on the newly-added line segment, in 3D linear programming, we know the optimal incremental solution must lie on the newly-added plane.
RVO2 defines the constraint plane of a given ORCA line to extend into the Z-axis with a slight tilt, and the infeasible problem we're looking at is just at some slice on an XY-plane.
Now, consider the intersection of two ORCA planes, slightly tilted on the Z-axis -- their intersection is a slightly skewed line, which can be projected onto the XY-plane. This is the bisecting line that RVO2 defines.(1)
Remember that the lines of intersection are parametric; geometrically, we can view these t-parameters as the Z-axis component, i.e. where we should decide to take a new "slice" of the original system of constraints.
When we solve for LP1 in LP3, we are finding the [tl, tr] interval of these bisecting lines -- that is, we are finding the "bounding planes" in the Z-axis between which the optimal solution should be found.
Note that RVO2.LP3 calls LP2 with an optimal velocity pointing into the feasible region of the iterative constraint -- we know the current system is infeasible, so we want to move as directly as possible into a feasible state.
Also note that in LP1, we drop the calculation to find a point closest to the (bisecting) constraint when dirOpt = True -- this is because the linear problem has changed when we project the 3D problem into 2D space. 586
We are no longer looking for minimal perturbation in 2D space, but looking for a shared feasible point among all projected constraints. We have left the minimal perturbation requirement to LP3.
I'm attempting to re-implement ORCA at the moment, at https://github.com/downflux/go-orca. Hopefully I will have more comments to the effect of this post soon.
1. N.B.: The XY-slice that LP3 feeds into LP2 is not technically aligned with the constraint plane itself, but is a 2D planar projection into 2D ambient space -- this nicely avoids attempting to deal with 3D lines and makes reasoning a bit easier. 433