2003-01: Comparison of convex hulls and box hulls

DIMACS TR: 2003-01

Comparison of convex hulls and box hulls

Authors: E. Boros, V. Gurvich, Y. Liu

ABSTRACT
A {\it convex hull} of a set of points $X$ is the minimal convex set containing $X$. A {\it box $B$} is an interval $B=\{\vx|\vx\in [\va, \vb], \va, \vb \in \R^n\}$. A {\it box hull} of a set of points $X$ is defined to be the minimal box containing $X$. Because both convex hulls and box hulls are closure operations of points, classical results for convex sets can naturally be extended for box hulls. We consider here the extensions of theorems by Carath\'{e}odory, Helly and Radon to box hulls and obtain exact results.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2003/2003-01.ps.gz

DIMACS Home Page