Convex hull of planar h-polyhedra

Abstract

Suppose

are planar (convex) H-polyhedra, that is, A _i  ∈ ℝ ^{n _i ×2} and

. Let

and n = n ₁ + n ₂. We present an O(n log n) algorithm for calculating an H-polyhedron

with the smallest

such that P ₁ ∪ P ₂ ⊆ P.

^†E-mail: [email protected]

Keywords:

• Convex hull
• Computational geometry

Notes

^†E-mail: [email protected]