42
правки
Изменения
→Эффективная аппроксимация нахождения значения гиперобъема
где 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>
