Fast $2$D region containment test

Question

Using a tuple $I = (a, b)$, I can define a 2D space region, $G = \{(x, y)||x+a| \leq y +b , x, y \in \mathbb{R} \}$.

Given two coefficient tuple $I_1, I_2, \in \mathbb{Z}^2$. Is there any efficient way to test if $G_1 \subseteq G_2$ ?

Answer 1

The region $G(a,b)$ is an intersection of two half-planes, defined by inequalities:

$$y \ge x+a-b$$ $$ y \ge -x-a-b$$

It looks like a wedge with the angle $\pi / 2$, opened up along the positive direction of the $OY$ axis, with the origin at the point $(-a,-b) \in \Bbb R^2$.

It's easy to see that the region $G_1(a_1,b_1)$ is contained in the region $G_2(a_2,b_2)$ if and only if the origin of the region $G_1$ is contained in the region $G_2$. So, coordinates of the origin of $G_1$ must satisfy the inequality, describing the region $G_2$:

$$|-a_1+a_2| \le -b_1+b_2$$

The left side of this inequality is always positive, so it makes sense only when $b_1 \le b_2$. We can write two conditions to verify that $G_1 \subseteq G_2$ in the following way:

$$(b_1 \le b_2) \land (|a_2-a_1| \le b_2-b_1)$$

In most programming languages the logical "and" operation will be performed from left to right, so the second condition won't be checked when the first one isn't satisfied.