Six kinds of problems are particularly important:[1]: Sec.2 optimization, violation, validity, separation, membership and emptiness.
In all problem descriptions, K denotes a compact and convex set in Rn.
It is also possible to approximate the diameter and the width of K: Some problems not yet solved (as of 1993) are whether it is possible to compute in polytime the volume, the center of gravity or the surface area of a convex body given by a separation oracle.
Some binary operations on convex sets preserve the algorithmic properties of the various problems.
An algorithm for WMEM, given circumscribed radius R and inscribe radius r and interior point a0, can solve the following slightly stronger membership problem (still weaker than SMEM): given a vector y in Qn, and a rational ε>0, either assert that y in S(K,ε), or assert that y not in K. The proof is elementary and uses a single call to the WMEM oracle.
[1]: Thm.6.5.14 Note that the above theorems do not require an assumption of full-dimensionality or a lower bound on the volume.
Other reductions cannot be made without additional information: Jain[5] extends one of the above theorems to convex sets that are not polyhedra and not well-described.
He only requires a guarantee that the convex set contains at least one point (not necessarily a vertex) with a bounded representation length.
He proves that, under this assumption, SNEMPT can be solved (a point in the convex set can be found) in polytime.
[5]: Thm.12 Moreover, the representation length of the found point is at most P(n) times the given bound, where P is some polynomial function.
[5]: Thm.13 Using the above basic problems, one can solve several geometric problems related to nonempty polytopes and polyhedra with a bound on the representation complexity, in oracle-polynomial time, given an oracle to SSEP, SVIOL or SOPT:[1]: Sec.6.5