Institut für Informatik
 
Abteilung V

 
Universität Bonn -> Institut für Informatik -> Abteilung V
CS-Reports 1995 Copyright 1995 Universität Bonn, Institut für Informatik, Abt. V
85145

Approximating the Volume of General Pfaffian Bodies
Marek Karpinski, Angus Macintyre
[Download PostScript] [Download PDF]

We introduce a new powerful method of approximating the volume (and integrals) of vast number of geometric bodies defined by boolean combinations of Pfaffian conditions. The method depends on the polynomial bounds on the VC - Dimensions of the classes of sets to be measured. The resulting approximation algorithms are quite different in spirit from the other up to now known mehtods, and gives efficient randomized solutions even for such seemingly untouchable problems of ststistical phzsics like computing the volume of sets defined by the systems of exponential and polynomial inqualities.

Last Change: 11/05/14 at 09:54:10
 English
Universität Bonn -> Institut für Informatik -> Abteilung V