Let P be a (non-necessarily convex) embedded polyhedron in R³, with its vertices on the boundary of an ellipsoid. Suppose that the interior of PP can be decomposed into convex polytopes without adding any vertex. Then P is infinitesimally rigid. More generally, let P be a polyhedron bounding a domain which is the union of polytopes C₁, . . ., C_n with disjoint interiors, whose vertices are the vertices of P. Suppose that there exists an ellipsoid which contains no vertex of P but intersects all the edges of the C_i. Then P is infinitesimally rigid. The proof is based on some geometric properties of hyperideal hyperbolic polyhedra.