Ioannis Emiris -- Volume computation of convex regions
23 November 2017 –
The major part of this talk is devoted to sampling methods for convex polytopes. Our main contribution is the development in C++ of a practical method for dimensions in the hundreds, by geometric random walks, following the popular paradigm of Hit-and-Run. We show that worst-case bounds are overly pessimistic. This approach is readily extended to convex regions. We then examine certain structured inputs: We implement efficient methods for sampling simplices as well as formulae for the volume of the intersection of a simplex and one or more halfspaces.