Algorithms.Geometry.LinearProgramming.LP2DRIC

2D Linear programming in expected linear time.

Documentation

solveBoundedLinearProgram :: (MonadRandom m, Ord r, Fractional r) => LinearProgram 2 r -> m (Maybe (Point 2 r))

Solves a bounded linear program in 2d. Returns Nothing if there is no solution.

pre: The linear program is bounded, meaning that *the first two constraints* m1,m2 make sure th the there is no arbitrarily large/good solution. I..e. these halfspaces bound the solution in the c direction.

(note that if there is only one constraint, m1, the assumption that the LP is bounded means that the contraint must be perpendicular to the objective direction. Hence, any point on the bounding plane is a solution, and they are all equally good.)

\(O(n)\) expected time

solveBoundedLinearProgram' :: (Ord r, Fractional r) => LinearProgram 2 r -> Maybe (Point 2 r)

Solves a bounded linear program (like solveBoundedLinearProgram) assuming that the first two constraints [m1,m2] make sure the solutions is bounded, and the other constraints already have been shuffled.

maximumOn :: (Ord r, Fractional r) => LPState 2 r -> Line 2 r -> Maybe (Point 2 r)

Let l be the boundary of h, and assume that we know that the new point in the common intersection must lie on h, try to find this point. In partiuclar, we find the maximum point in the s^.direction vector. The funtion returns Nothing if no such point exists, i.e. if there is no point on l that is contained in all halfspaces.

Note that this is essentially one dinsional LP

oneDLinearProgramming :: (Ord r, Num r, Arity d) => Vector d r -> Line d r -> [HalfLine d r] -> Maybe (Point d r)

One dimensional linear programming on lines embedded in \(\mathbb{R}^d\).

Given an objective vector c, a line l, and a collection of half-lines hls that are all sublines of l (i.e. halfspaces *on* l), compute if there is a point inside all these halflines. If so, we actually return the one that maximizes c.

running time: \(O(n)\)

commonIntersection :: (Ord r, Num r, Arity d) => Line d r -> NonEmpty (HalfLine d r :+ a) -> Either (Two (HalfLine d r :+ a)) (OneOrTwo (Point d r :+ a))

Computes the common intersection of a nonempty list of halfines that are all colinear with the given line l.

We return either the two halflines that prove that there is no counter example or we return one or two points that form form the boundary points of the range in which all halflines intersect.

cmpHalfPlane :: (Ord r, Num r, Arity d) => Vector d r -> Point d r -> Point d r -> Ordering

Given a vector v and two points a and b, determine which is smaller in direction v.