A. Simon and A. King. Convex Hull of Planar H-Polyhedra. International Journal of Computer Mathematics, 81(4):259--271, March 2004.

Suppose $\langle A_i, \vec{c}_i \rangle$ are planar (convex) H-polyhedra, that is, $A_i \in \mathbb{R}^{n_i \times 2}$ and $\vec{c}_i \in \mathbb{R}^{n_i}$ . Let $P_i = \{ \vec{x} \in \mathbb{R}^2 \mid A_i\vec{x} \leq \vec{c}_i \}$ and $n = n_1 + n_2$ . We present an $O(n \log n)$ algorithm for calculating an H-polyhedron $\langle A, \vec{c} \rangle$ with the smallest $P = \{ \vec{x} \in \mathbb{R}^2 \mid A\vec{x} \leq \vec{c} \}$ such that $P_1 \cup P_2 \subseteq P$ .

Download: PDF Reference: Bibtex