Return to Answer

Let's use vector notation to simplify algebraic expressions:

$$a_i=(d_i,e_i)$$ $$x=(x_1,x_2)$$

Then your constraints can be written using Dot Product:

$$a_i \cdot x \le b_i, i \in [1,m]$$

Let's denote the inner circle center $y$ and focus on the $i$-th constraint for now. Imagine a shortest segment, connecting the point $y$ and the line $a_i \cdot x = b_i$. It's easy to see that this segment will be perpendicular to this line and collinear with vector $a_i$.

Let's find the point $z_i$, lying on the segment above, with the distance from the point $y$ equal to the $R$ (radius of the inner circle). This point is given by the following vector expression:

$$z_i = y + \frac{a_i}{\lVert a_i \rVert}R$$

Now we have to make sure that all the points $z_i$ are located in correct halfplanes:

$$a_i \cdot z_i \le b_i, i \in [1,m]$$

Simplifying these equations using the expression for the point $z_i$ (above) we'll get:

$$a_i \cdot y + \lVert a_i \rVert R \le b_i, i \in [1,m]$$

So, now you have an LP problem with three variables $(y_1, y_2, R)$, $m$ constraints (above), an additional constraint $R \ge 0$ and optimization function, which is simply $R$.

Please see the Chebyshev Center page for more information, in particular the reference #4.

You're close to the solution, but aren't there yet. Your third inequality should look like this (no absolute values!):

$$d_i x_1 + e_i x_2 + \sqrt{{e_i}^2 +{d_i}^2}R \le b_i$$

And yes, the maximal inner circle radius can be zero, and even more - this circle might not exist at all. Please see the following explanation to grasp that.

Let's use vector notation to simplify algebraic expressions:

$$a_i=(d_i,e_i)$$ $$x=(x_1,x_2)$$

Then your constraints can be written using Dot Product:

$$a_i \cdot x \le b_i, i \in [1,m]$$

Let's denote the inner circle center $y$ and focus on the $i$-th constraint for now. Imagine a shortest segment, connecting the point $y$ and the line $a_i \cdot x = b_i$. It's easy to see that this segment will be perpendicular to this line and collinear with vector $a_i$.

Let's find the point $z_i$, lying on the segment above, with the distance from the point $y$ equal to the $R$ (radius of the inner circle). This point is given by the following vector expression:

$$z_i = y + \frac{a_i}{\lVert a_i \rVert}R$$

Now we have to make sure that all the points $z_i$ are located in correct halfplanes:

$$a_i \cdot z_i \le b_i, i \in [1,m]$$

Simplifying these equations using the expression for the point $z_i$ (above) we'll get:

$$a_i \cdot y + \lVert a_i \rVert R \le b_i, i \in [1,m]$$

So, now you have an LP problem with three variables $(y_1, y_2, R)$, $m$ constraints (above), an additional constraint $R \ge 0$ and optimization function, which is simply $R$.

Please see the Chebyshev Center page for more information, in particular the reference #4.

Let's use vector notation to simplify algebraic expressions:

$$a_i=(d_i,e_i)$$ $$x=(x_1,x_2)$$

Then your constraints can be written using Dot Product:

$$a_i \cdot x \le b_i, i \in [1,m]$$

Let's denote the inner circle center $y$ and focus on the $i$-th constraint for now. Imagine a shortest segment, connecting the point $y$ and the line $a_i \cdot x = b_i$. It's easy to see that this segment will be perpendicular to this line and collinear with vector $a_i$.

Let's find the point $z_i$, lying on the segment above, with the distance from the point $y$ equal to the $R$ (radius of the inner circle). This point is given by the following vector expression:

$$z_i = y + \frac{a_i}{\lVert a_i \rVert}R$$

Now we have to make sure that all the points $z_i$ are located in correct halfplanes:

$$a_i \cdot z_i \le b_i, i \in [1,m]$$

Simplifying these equations using the expression for the point $z_i$ (above) we'll get:

$$a_i \cdot y + \lVert a_i \rVert R \le b_i, i \in [1,m]$$

So, now you have an LP problem with three variables $(y_1, y_2, R)$, $m$ constraints (above), an additional constraint $R \ge 0$ and optimization function, which is simply $R$.

(This is a known approach, but I couldn't find an understandable explanation of it on the net)

Let's use vector notation to simplify algebraic expressions:

$$a_i=(d_i,e_i)$$ $$x=(x_1,x_2)$$

Then your constraints can be written using Dot Product:

$$a_i \cdot x \le b_i, i \in [1,m]$$

Let's denote the inner circle center $y$ and focus on the $i$-th constraint for now. Imagine a shortest segment, connecting the point $y$ and the line $a_i \cdot x = b_i$. It's easy to see that this segment will be perpendicular to this line and collinear with vector $a_i$.

Let's find the point $z_i$, lying on the segment above, with the distance from the point $y$ equal to the $R$ (radius of the inner circle). This point is given by the following vector expression:

$$z_i = y + \frac{a_i}{\lVert a_i \rVert}R$$

Now we have to make sure that all the points $z_i$ are located in correct halfplanes:

$$a_i \cdot z_i \le b_i, i \in [1,m]$$

Simplifying these equations using the expression for the point $z_i$ (above) we'll get:

$$a_i \cdot y + \lVert a_i \rVert R \le b_i, i \in [1,m]$$

So, now you have an LP problem with three variables $(y_1, y_2, R)$, $m$ constraints (above), an additional constraint $R \ge 0$ and optimization function, which is simply $R$.

Please see the Chebyshev Center page for more information, in particular the reference #4.

Let's use vector notation to simplify algebraic expressions:

$$a_i=(d_i,e_i)$$ $$x=(x_1,x_2)$$

Then your constraints can be written using Dot Product:

$$a_i \cdot x \le b_i, i \in [1,m]$$

Let's denote the inner circle center $y$. Now let's imagine a shortest segment, connecting the point $y$ and the line $a_i \cdot x = b_i$. It's easy to see that this segment will be perpendicular to this line and collinear with vector $a_i$.

Let's find the point $z_i$, lying on the segment above, with the distance from the point $y$ equal to the $R$ (radius of the inner circle). This point is given by the following vector expression:

$$z_i = y + \frac{a_i}{\lVert a_i \rVert}R$$

Now we have to make sure that the point $z_i$ lies in the correct halfplane:

$$a_i \cdot z_i \le b_i, i \in [1,m]$$

Simplifying this equation using the expression for the point $z_i$ we'll get:

$$a_i \cdot y + \lVert a_i \rVert R \le b_i, i \in [1,m]$$

So, now you have an LP problem with three variables $(y_1, y_2, R)$, $m$ constraints (above), an additional constraint $R \ge 0$ and optimization function, which is simply $R$.

(This is a known approach, but I couldn't find an understandable explanation of it on the net)

Let's use vector notation to simplify algebraic expressions:

$$a_i=(d_i,e_i)$$ $$x=(x_1,x_2)$$

Then your constraints can be written using Dot Product:

$$a_i \cdot x \le b_i, i \in [1,m]$$

Let's denote the inner circle center $y$ and focus on the $i$-th constraint for now. Imagine a shortest segment, connecting the point $y$ and the line $a_i \cdot x = b_i$. It's easy to see that this segment will be perpendicular to this line and collinear with vector $a_i$.

Let's find the point $z_i$, lying on the segment above, with the distance from the point $y$ equal to the $R$ (radius of the inner circle). This point is given by the following vector expression:

$$z_i = y + \frac{a_i}{\lVert a_i \rVert}R$$

Now we have to make sure that all the points $z_i$ are located in correct halfplanes:

$$a_i \cdot z_i \le b_i, i \in [1,m]$$

Simplifying these equations using the expression for the point $z_i$ (above) we'll get:

$$a_i \cdot y + \lVert a_i \rVert R \le b_i, i \in [1,m]$$

So, now you have an LP problem with three variables $(y_1, y_2, R)$, $m$ constraints (above), an additional constraint $R \ge 0$ and optimization function, which is simply $R$.

(This is a known approach, but I couldn't find an understandable explanation of it on the net)