A weak membership oracle for a convex body 
is an oracle that decides
approximate membership with a specified tolerance 
(Grötschel et al. 1988). Writing 
for the closed ball of radius
1 centered at the origin, define
 |
where addition is the Minkowski sum. For a rational point 
and a positive rational number 
, an affirmative answer certifies 
, and a negative answer certifies 
. Either answer is permitted in the tolerance
region between the two sets. This input model allows algorithms
to work with a convex body without an explicit finite
list of its defining inequalities.
