We describe a simplified and strengthened version of Vaidya's volumetric cutting plane method for finding a point in a convex set 𝒞 ⊂ Rn. At each step the algorithm has a system of linear inequality constraints which defines a polyhedron 𝒫 ⊃ 𝒞, and an interior point x ∈ 𝒫. The algorithm then either drops one constraint, or calls an oracle to check if x ∈ 𝒞, and, if not, obtain a new constraint that separates x from 𝒞. Following the addition or deletion of a constraint, the algorithm takes a small number of Newton steps for the volumetric barrier V(·). Progress of the algorithm is measured in terms of changes in V(·). The algorithm is terminated when either it is discovered that x ∈ 𝒞, or V(·) becomes large enough to demonstrate that the volume of 𝒞 must be below some prescribed amount. The complexity of the algorithm compares favourably with that of the ellipsoid method, especially in terms of the number of calls to the separation oracle. Compared to Vaidya's original analysis, we decrease the total number of Newton steps required for termination by a factor of about 1.3 million, while at the same time decreasing the maximum number of constraints used to define 𝒫 from 107n to 200n.
