42
правки
Изменения
→Эффективная аппроксимация нахождения значения гиперобъема
==Эффективная аппроксимация нахождения значения гиперобъема==
Приведем псевдокод алгоритма для аппроксимации гиперобъемаобъединения тел. В алгоритме, приведенном в
<ref>
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
od
return <tex>\frac{TV'}{nM}</tex>
Время работы алгоритма составляет
<tex>O(n V(d)+M S(d)+ TP(d) = O(n V(d) + T(S(d)+P(d)))</tex>,
где V(d), S(d) и P(d) это оценка времени работы оракулов VolumeQuery, SampleQuery и PointQuery, соответственно.
Выберем <tex>\epsilon : \epsilon_s, \epsilon_p, \epsilon_v \leq \frac{epsilon^2}{47n}</tex>.
Если все используемые тела являются гиперкубами, то время работы каждого из оракулов составляет в точности <tex>O(d)</tex>, таким образом алгоритм позволяет построить <tex>\epsilon</tex>-аппроксимацию гиперобъема с вероятностью <tex>\geq 3/4</tex> за время <tex>O(\frac{nd}{\epsilon^2})</tex>
== Примечания ==
<references />
