I'm currently working on a project where i'm implementing the marriage before conquest algorithm for finding the convex hull of a set of points.
One step involves separating my set of points by a line, and finding the bridge between those set of points.
Constructing such a bridge is the same as finding a line that:
- Passes above all the points.
- Has the lowest intersection point with the line that separates the points.
In terms of a line on the form of y = ax+b that means:
- y_i <= ax_i + b, for every point (x_i, y_i).
- y_m = ax_m + b is minimized (where x_m is the x value of the seperating line).
I know from Duality that a point can be represented as a line and vice versa as such:
- point:(p_x,p_y) -> line: y = p_x*x - p_y
I have previously worked with the scipy.optimize.linprog library, but cannot figure out how to turn this problem into a linear problem solvable by scipy. Is this possible, and if so, how can i do this?