42
правки
Изменения
→Эффективная аппроксимация нахождения гиперобъема
Karl Bringmann, Tobias Friedrich, Approximating the volume of unions and intersections of high-dimensional geometric objects, ISAAC'2008, http://www.mpi-inf.mpg.de/~kbringma/paper/2008ISAAC_Volume.pdf
</ref>
используются три оракула : PointQuery, VolumeQuery и SampleQuery, каждый из которых ошибается с вероятностью <tex>\epsilon_p, \epsilon_v</tex> и <tex>\epsilon_s</tex> соответственно.
Оракул VolumeQuery возвращает объем заданного тела <tex>B</tex>.
SampleQuery(B) для заданного тела <tex>B</tex> возвращает произвольную его точку <tex>x \in B</tex>.
PointQuery(x,B) возвращает true, если точка <tex>x</tex> лежит внутри <tex> B</tex>.
Для данного алгоритма допускаются следующие ослабления этих оракулов:
*PointQuery (x,B) возвращает true для всех точек из некоторого тела <tex> B' : \mu ((B' \backslash B) \cup (B \backslash B'))\leq \epsilon_p \mu(B)</tex>
*VolumeQuery(B) возвращает значение <tex>V' : (1-\epsilon_v)\mu(B) \leq V' \leq (1+\epsilon_v)\mu(B)</tex>
*SampleQuery(B) возвращает произвольную точку из тела <tex>B' : |f(x) - 1/\mu(B')|<\epsilon_s
M := 0; C := 0;
<tex> \overline \epsilon := \frac{\epsilon - \epsilon_v}{1+ \epsilon_v} </tex>
