  We introduce a new iterative root-finding method for complex polynomials,
dubbed {\it Newton-Ellipsoid} method. It is inspired by the Ellipsoid method, a
classical method in optimization, and a property of Newton's Method derived in
\cite{kalFTA}, according to which at each complex number a half-space can be
found containing a root. Newton-Ellipsoid method combines this property, bounds
on zeros, together with the plane-cutting properties of the Ellipsoid Method.
We present computational results for several examples, as well as corresponding
polynomiography. Polynomiography refers to algorithmic visualization of
root-finding. Newton's method is the first member of the infinite family of
iterations, the {\it basic family}. We also consider general versions of this
ellipsoid approach where Newton's method is replaced by a higher-order member
of the family such as Halley's method.
