Return to Answer

Proof of claim 1:

For every query of k points q we have:

$Cost(C1,q)=e_1\cdot Cost(P1,q)$, where $e_1\in [1-\epsilon, 1+\epsilon]$,

$Cost(C2,q)=e_2\cdot Cost(P2,q)$, where $e_2\in [1-\epsilon, 1+\epsilon]$.

Meaning that:

$Cost(C1\bigcup C2,q)=e_1\cdot Cost(P1,q)+e_2\cdot Cost(P2,q)$

This is smaller than: $\leq (1+\epsilon)\cdot Cost(P1,q)+(1+\epsilon)\cdot Cost(P2,q)=(1+\epsilon)Cost(P1\bigcup P2,q)$

And bigger than $\geq (1-\epsilon)\cdot Cost(P1,q)+(1-\epsilon)\cdot Cost(P2,q)=(1-\epsilon)Cost(P1\bigcup P2,q)$

Which proofs claim 1.

Claim 2 is only approximately correct for small values of $\epsilon,\delta$.

Proof of claim 2:

$Cost(C1,q)\leq (1+\epsilon)Cost(C2,q)\leq (1+\epsilon)(1+\delta)Cost(C3,q)=\\(1+\epsilon+\delta+\epsilon\cdot\delta)Cost(C3,q)\approx (1+\epsilon+\delta)Cost(C3,q)$

And a similar proof can be made for the lower bound.

Proof of claim 1:

For every query q of k points we have:

$Cost(C1\bigcup C2,q)=Cost(C1,q)+Cost(C2,q)\\ \leq (1+\epsilon)\cdot Cost(P1,q)+(1+\epsilon)\cdot Cost(P2,q)=(1+\epsilon)Cost(P1\bigcup P2,q)$

And a similar proof can be made for the lower bound.

Claim 2 is only approximately correct for small values of $\epsilon,\delta$.

Proof of claim 2:

$Cost(C1,q)\leq (1+\epsilon)Cost(C2,q)\leq (1+\epsilon)(1+\delta)Cost(C3,q)=\\(1+\epsilon+\delta+\epsilon\cdot\delta)Cost(C3,q)\approx (1+\epsilon+\delta)Cost(C3,q)$

And a similar proof can be made for the lower bound.

Proof of claim 1:

For every query of k points q we have:

$Cost(C1,q)=e_1\cdot Cost(P1,q)$, where $e_1\in [1-\epsilon, 1+\epsilon]$,

$Cost(C2,q)=e_1\cdot Cost(P2,q)$, where $e_2\in [1-\epsilon, 1+\epsilon]$.

Meaning that:

$Cost(C1\bigcup C2,q)=e_1\cdot Cost(P1,q)+e_2\cdot Cost(P2,q)$

This is smaller than: $(1+\epsilon)\cdot Cost(P1,q)+(1+\epsilon)\cdot Cost(P2,q)=(1+\epsilon)Cost(P1\bigcup P2,q)$

And bigger than $(1-\epsilon)\cdot Cost(P1,q)+(1-\epsilon)\cdot Cost(P2,q)=(1-\epsilon)Cost(P1\bigcup P2,q)$

Which proofs claim 1.

Claim 2 is only approximately correct for small values of $\epsilon,\delta$.

Proof of claim 2:

$Cost(C1,q)\leq (1+\epsilon)Cost(C2,q)\leq (1+\epsilon)(1+\delta)Cost(C3,q)=\\(1+\epsilon+\delta+\epsilon\cdot\delta)Cost(C3,q)\approx (1+\epsilon+\delta)Cost(C3,q)$

And a similar proof can be made for the lower bound.

Proof of claim 1:

For every query of k points q we have:

$Cost(C1,q)=e_1\cdot Cost(P1,q)$, where $e_1\in [1-\epsilon, 1+\epsilon]$,

$Cost(C2,q)=e_2\cdot Cost(P2,q)$, where $e_2\in [1-\epsilon, 1+\epsilon]$.

Meaning that:

$Cost(C1\bigcup C2,q)=e_1\cdot Cost(P1,q)+e_2\cdot Cost(P2,q)$

This is smaller than: $\leq (1+\epsilon)\cdot Cost(P1,q)+(1+\epsilon)\cdot Cost(P2,q)=(1+\epsilon)Cost(P1\bigcup P2,q)$

And bigger than $\geq (1-\epsilon)\cdot Cost(P1,q)+(1-\epsilon)\cdot Cost(P2,q)=(1-\epsilon)Cost(P1\bigcup P2,q)$

Which proofs claim 1.

Claim 2 is only approximately correct for small values of $\epsilon,\delta$.

Proof of claim 2:

$Cost(C1,q)\leq (1+\epsilon)Cost(C2,q)\leq (1+\epsilon)(1+\delta)Cost(C3,q)=\\(1+\epsilon+\delta+\epsilon\cdot\delta)Cost(C3,q)\approx (1+\epsilon+\delta)Cost(C3,q)$

And a similar proof can be made for the lower bound.

Proof of claim 1:

For every query of k points q we have:

$Cost(C1,q)=e_1\cdot Cost(P1,q)$, where $e_1\in [1-\epsilon, 1+\epsilon]$,

$Cost(C2,q)=e_1\cdot Cost(P2,q)$, where $e_2\in [1-\epsilon, 1+\epsilon]$.

Meaning that:

$Cost(C1\bigcup C2,q)=e_1\cdot Cost(P1,q)+e_2\cdot Cost(P2,q)$

This is smaller than: $(1+\epsilon)\cdot Cost(P1,q)+(1+\epsilon)\cdot Cost(P2,q)=(1+\epsilon)Cost(P1\bigcup P2,q)$

And bigger than $(1-\epsilon)\cdot Cost(P1,q)+(1-\epsilon)\cdot Cost(P2,q)=(1-\epsilon)Cost(P1\bigcup P2,q)$

Which proofs claim 1.

Claim 2 is a bit trickier and is only approximately correct for small values of $\epsilon,\delta$.

Proof of claim 2:

$Cost(C1,q)\leq (1+\epsilon)Cost(C2,q)\leq (1+\epsilon)(1+\delta)Cost(C3,q)=\\(1+\epsilon+\delta+\epsilon\cdot\delta)Cost(C3,q)\approx (1+\epsilon+\delta)Cost(C3,q)$

And a similar proof can be made for the lower bound.

Proof of claim 1:

For every query of k points q we have:

$Cost(C1,q)=e_1\cdot Cost(P1,q)$, where $e_1\in [1-\epsilon, 1+\epsilon]$,

$Cost(C2,q)=e_1\cdot Cost(P2,q)$, where $e_2\in [1-\epsilon, 1+\epsilon]$.

Meaning that:

$Cost(C1\bigcup C2,q)=e_1\cdot Cost(P1,q)+e_2\cdot Cost(P2,q)$

This is smaller than: $(1+\epsilon)\cdot Cost(P1,q)+(1+\epsilon)\cdot Cost(P2,q)=(1+\epsilon)Cost(P1\bigcup P2,q)$

And bigger than $(1-\epsilon)\cdot Cost(P1,q)+(1-\epsilon)\cdot Cost(P2,q)=(1-\epsilon)Cost(P1\bigcup P2,q)$

Which proofs claim 1.

Claim 2 is only approximately correct for small values of $\epsilon,\delta$.

Proof of claim 2:

$Cost(C1,q)\leq (1+\epsilon)Cost(C2,q)\leq (1+\epsilon)(1+\delta)Cost(C3,q)=\\(1+\epsilon+\delta+\epsilon\cdot\delta)Cost(C3,q)\approx (1+\epsilon+\delta)Cost(C3,q)$

And a similar proof can be made for the lower bound.