  We address the problem of constructing elliptic polytopes in R^d, which are
convex hulls of finitely many two-dimensional ellipses with a common center.
Such sets arise in the study of spectral properties of matrices, asymptotics of
long matrix products, in the Lyapunov stability, etc.. The main issue in the
construction is to decide whether a given ellipse is in the convex hull of
others. The computational complexity of this problem is analysed by considering
an equivalent optimisation problem. We show that the number of local extrema of
that problem may grow exponentially in d. For d=2,3, it admits an explicit
solution for an arbitrary number of ellipses; for higher dimensions, several
geometric methods for approximate solutions are derived. Those methods are
analysed numerically and their efficiency is demonstrated in applications.
