42
правки
Изменения
→Эффективная аппроксимация нахождения гиперобъема
</ref>
используются три оракула PointQuery, VolumeQuery и SampleQuery, каждый из которых ошибается с вероятностью <tex>\epsilon_p, \epsilon_v</tex> и <tex>\epsilon_s</tex> соответственно.
M := 0; C := 0;
<tex> \overline \epsilon := \frac{\epsilon - \epsilon_v}{1+ \epsilon_v} </tex>
<tex> \overline C := \frac{(1+\epsilon_s)(1+\epsilon_v)(1+\epsilon_p)}{(1-\epsilon_v)(1-\epsilon_p)}</tex>
<tex> T := \frac{24 ln (2) (1 + \overline \epsilon) n}{\overline \epsilon^2 - 8 (\overline C - 1) n}</tex>
for all <tex>B_i \in S</tex>
compute <tex>V'_i</tex> := VolumeQuery(<tex>B_i</tex>)
od
<tex> V' := \sum \limits_(i = 1)^n V'_i</tex>
while <tex>C \leq T</tex> do
choose <tex>i \in [n] </tex> with probability <tex>\frac{V'_i}{V'}</tex>
x := SampleQuery(<tex>B_i</tex>)
repeat
if (C > T) then return <tex>\frac {TV'}{nM} </tex>
choose random <tex>j \in [n]</tex> uniformly
C := C + 1
until PointQuery (x, <tex>B_j</tex>)
M := M + 1
od
return <tex>\frac{TV'}{nM}</tex>
== Примечания ==
<references />
