LP - given m constraints for 2 variables find maximal radius of circle

Question

Given $m$ constraints for 2 variables $x_1,x_2$ :

$d_ix_1 + e_ix_2 \leq b_i$ for $i = 1,...m$

need to create a linear program that finds the maximal radius of a circle such that all the points inside the circle are in the feasible range of the above constraints. The circle can be located anywhere -- not necessarily centered at the origin.

so I know the formula for distance between some $(x,y)$ and some $ax +by + c = 0$

then I have tried -

• $Maximal$ $R$ s.t
• $d_ix_1 + e_ix_2 \leq b_i$ for every $i$
• $R \leq |d_ix_1 + e_ix_2 - b_i| / {\sqrt{{e_i}^2 +{d_i}^2}}$ for every $i$
• $R \geq 0$

I know the standard linear program doesn't get absolute value function but obviously we can just have 2 inequalities to get rid of it.

I'm not sure if this is the correct answer.

furthermore, is it possible that for some constraints if will force the radius to be 0?

Answer 1

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.

Answer 2

Just take the minimum of the radii you get for each restriction.

But that presumes a circle centered at the origin, and all restrictions cutting positive $x$ and $y$ axes. If that isn't the case, you'd have to clarify further.