I want to compute the centroid of a body of the following form: $$ E\cap H_1\cap \cdots \cap H_T $$ where:

  • $E$ is an ellipsoid in $\mathbb{R}^d$: $E = \{x = c + Bu | u^T u \leq 1\}$, where $c$ is the ellipsoid center and $B$ is a matrix.
  • $H_1,\ldots,H_T$ are half-spaces.

Can this be done in time polynomial in $d$ (the dimension) and $T$ (the number of half-spaces)?

The motivation to this question comes from the ellipsoid method. In that method, after intersecting the current ellipsoid with a half-space, we find another ellipsoid that contains the resulting "half-ellipsoid". I would like to understand whether this last step is essential, or maybe we could just keep the half-ellipsoid and find its centroid, etc., without covering them with ellipsoids.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.