419
правок
Изменения
Нет описания правки
Предикат, определяющий взаимное расположение точек <tex>c_1</tex> и <tex>c_2</tex> по ординате, выглядит следующим образом:
<tex>K = (r_2 \cdot \sin \alpha + y_2) - (r_4 \cdot \sin \beta + y_4) = (r_2 \cdot \frac{y_1 - y_2}{r_1 + r_2} + y_2) - (r_4 \cdot \frac{y_3 - y_4}{r_3 + r_4} + y_4)</tex>
Т.к. <tex> r_1 + r_2 > 0, r_3 + r_4 > 0</tex>, то можно оценивать знак выражения <tex>T = K \cdot (r_1 + r_2) \cdot (r_3 + r_4)</tex>
<tex>T = (r_2 \cdot (y_1 - y_2)+y_2 \cdot (r_1+r_2)) \cdot (r_3+r_4) - (r_4 \cdot (y_3-y_4)+y_4 \cdot (r_3+r_4)) \cdot (r_1+r_2) = \\= (y_1 \cdot r_2 + y_2 \cdot r_1)(r_3+r_4) - (y_3 \cdot r_4 + y_4 \cdot r_3)(r_1+r_2)</tex>
Рассмотрим это выражение в дабловой арифметике. Обозначим за <tex>F(p_1, p_2, \ldots , p_n) = (1 + \delta_{p_1}) \cdot (1 + \delta_{p_2}) \cdot \ldots \cdot (1 + \delta_{p_n})</tex>
<tex>\tilde{T} = (y_1 \otimes r_2 \oplus y_2 \otimes r_1)(r_3 \oplus r_4) \ominus (y_3 \otimes r_4 \oplus y_4 \otimes r_3)(r_1 \oplus r_2) =</tex>
<tex>= [(y_1 \cdot r_2 \cdot F(1,2) + y_2 \cdot r_1 \cdot F(3,4))(r_3+r_4) \cdot F(5,6,7) - \\- (y_3 r_4 F(8,9) + y_4 r_3 F(10,11))(r_1+r_2) F(12,13,14)] F(15) =</tex> <tex>= y_1 r_2 (r_3+r_4)F(1,2,5,6,7,15)+ \\cdot + y_2 r_1 (r_3+r_4 )F(3,4,5,6,7,15)- \cdot \- y_3 r_4 (r_1+r_2)F(8,9,12,13,14,15)-\\- y_4 r_3 (r_1+r_2)F(10,11,12,13,14,15)</tex> <tex> |\delta_i| \leq \varepsilon_m </tex> <tex>|\tilde{T}-T| = \\= |y_1 r_2 (r_3+r_4)(F(1,2,5,6,7,15) -1) + \\+ y_2 r_1 (r_3+r_4)(F(3,4,5,6,7,15)-1) - \\- y_3 r_4 (r_1+ r_2)(F(8,9,12,13,14,15)-1) -\\- y_4 r_3 (r_1+r_2)(F(10,11,12,13,14,15)-1)| \leq \\\leq |y_1 r_2 (r_3+r_4)| \cdot |(F(1,2,5,6,7,15)-1)| + \\+ |y_2 r_1 (r_3 +r_4)| \cdot |(F(103,4,5,6,7,1115)-1)| + \\+ |y_3 r_4 (r_1+r_2) | \cdot |(F(8,9,12,13,14,15)-1)| +\\+ |y_4 r_3 (r_1+r_2)] | \cdot |(F(10,11,12,13,14,15) =-1)|</tex> Теперь раскрываем скобки во всех <tex>F</tex>. Пользуемся тем, что <tex>|\sum{p_i}| \leq \sum{|p_i|}</tex> и <tex> |\delta_i| \leq \varepsilon_m </tex>.Получаем следующее: <tex>|\tilde{T}-T| \leq \\\leq |y_1 r_2 (r_3+r_4)| \cdot (6\varepsilon_m + 15\varepsilon_m^2 + 20\varepsilon_m^3 + 15\varepsilon_m^4 + 6\varepsilon_m^5 + \varepsilon_m^6) + \\+ |y_2 r_1 (r_3+r_4)| \cdot (6\varepsilon_m + 15\varepsilon_m^2 + 20\varepsilon_m^3 + 15\varepsilon_m^4 + 6\varepsilon_m^5 + \varepsilon_m^6) + \\+ |y_3 r_4 (r_1+r_2)| \cdot (6\varepsilon_m + 15\varepsilon_m^2 + 20\varepsilon_m^3 + 15\varepsilon_m^4 + 6\varepsilon_m^5 + \varepsilon_m^6) +\\+ |y_4 r_3 (r_1+r_2)| \cdot (6\varepsilon_m + 15\varepsilon_m^2 + 20\varepsilon_m^3 + 15\varepsilon_m^4 + 6\varepsilon_m^5 + \varepsilon_m^6) = \\= (6\varepsilon_m + 15\varepsilon_m^2 + 20\varepsilon_m^3 + 15\varepsilon_m^4 + 6\varepsilon_m^5 + \varepsilon_m^6) \cdot (|y_1 r_2 (r_3+r_4)|+|y_2 r_1 (r_3+r_4)|+|y_3 r_4 (r_1+r_2)|+|y_4 r_3 (r_1+r_2)|)
</tex>
[[Категория: Вычислительная геометрия]]