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

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?

• Do you have a more specific question? "What do you think?" is too vague -- we're a question-and-answer site, so we require you to articulate a specific answerable question. I cannot understand the last sentence/question. Please proof-read what you wrote and edit your post accordingly. – D.W. Jan 30 at 17:00
• not sure how to be more precise, then writing a cycle... say if I take some point in the origin (x,y) draw from that point a cycle that it's radius is the radius i have found in the linear program, the cycle won't be out of the feasible area...editing the post. – omrib40 Jan 30 at 17:17
• I still don't see a precise question. "I'm not sure if this is the correct answer." is not a question, and we don't want questions that say "here is my solution, please check if it is correct". I can't understand the last sentence/question; I don't know what "for some constraints if will force..." means. Please proof-read the question and edit to make it clearer what your question is. – D.W. Jan 30 at 17:51

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$$.

• @omrib40 - the inequality $|x|>a$ can be replaced by two inequalities $x <-a$ OR $x>a$. This OR isn't good for the LP... Also you didn't explain how you got this third inequality - frankly I don't understand it – HEKTO Jan 30 at 20:20
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.