Convex Hull of Planar H-Polyhedra

Original · EN

Suppose <Aᵢ, cᵢ> are planar (convex) H-polyhedra, that is, Aᵢ ∈ Rⁿⁱ × ² and cᵢ ∈ Rⁿⁱ. Let Pᵢ = {x ∈ R² Aᵢx ≤ cᵢ } and n = n₁ + n₂. We present an O(n n) algorithm for calculating an H-polyhedron <A, c> with the smallest P = {x ∈ R² Ax ≤ c } such that P₁ ∪ P₂ P.