42
правки
Изменения
→Эффективная аппроксимация нахождения значения гиперобъема
Bringmann K., Friedrich T., 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>
используются три оракула: <tt>PointQuery</tt>, <tt>VolumeQuery </tt> и <tt>SampleQuery</tt>, каждый из которых ошибается с вероятностью <tex>\epsilon_p, \epsilon_v</tex> и <tex>\epsilon_s</tex> соответственно.
Оракул
*<tt>PointQuery(x,B) </tt> возвращает true, если точка <tex>x</tex> лежит внутри <tex> B</tex>.*<tt>VolumeQuery(B) </tt> возвращает объем заданного тела <tex>B</tex>.*<tt>SampleQuery(B) </tt> для заданного тела <tex>B</tex> возвращает произвольную его точку <tex>x \in B</tex>.
Для данного алгоритма допускаются следующие ослабления этих оракулов:
*<tt>PointQuery (x,B) </tt> возвращает true для всех точек из некоторого тела <tex> B' : \mu ((B' \backslash B) \cup (B \backslash B'))\leq \epsilon_p \mu(B)</tex>*<tt>VolumeQuery(B) </tt> возвращает значение <tex>V' : (1-\epsilon_v)\mu(B) \leq V' \leq (1+\epsilon_v)\mu(B)</tex>*<tt>SampleQuery(B) </tt> возвращает произвольную точку из тела <tex>B' : |f(x) - 1/\mu(B')| < \epsilon_s </tex>
M := 0; C := 0;
<tex> \overline \epsilon := \frac{\epsilon - \epsilon_v}{1+ \epsilon_v} </tex>
<tex>O(n V(d)+M S(d)+ TP(d) = O(n V(d) + T(S(d)+P(d)))</tex>,
где <tex>V(d)</tex>, <tex>S(d)</tex> и <tex>P(d)</tex> это оценка времени работы оракулов <tt>VolumeQuery</tt>, <tt>SampleQuery </tt> и <tt>PointQuery</tt>, соответственно.
Выберем <tex>\epsilon : \epsilon_s, \epsilon_p, \epsilon_v \leq \frac{\epsilon^2}{47n}</tex>.
