Low-Dimensional Linear Programming

Presentation by: Marc Lebovitz

Seidel's Algorithm

return opt
Seidel (constraints H, objective function c, dimension d) {
    if (|H| == d) return intersection of constraints
    // recurse with one less constraint
    if (|H| > d) opt = Seidel (H - H*, c, d)
    if (pt is in positive halfspace of H*) return opt
    else // pt is in - halfspace of H*
        for each halfspace Hi != H*
            project Hi onto H* -> Hi'
        project c onto H* -> c'
        // recurse to lower dimension
        return Seidel (H', c', d-1)

Here's a look at it in 2D: