# 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.
Commented Jan 30, 2020 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. Commented Jan 30, 2020 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.
Commented Jan 30, 2020 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$$.

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

• Thanks for detailed solution, just one thing I didn't understand regarding your comment to my solution, how did you get rid of the absolute value that way? I would expect 2 inequalities like if |x| > a then x < -a and x > a. Commented Jan 30, 2020 at 19:21
• @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 Commented Jan 30, 2020 at 20:20
• the third inequality I took from Wikipedia, it just the equation to get a distance from a point to a line en.wikipedia.org/wiki/Distance_from_a_point_to_a_line regarding the OR of the inequalities, what intuition should guide when I need to choose one of this inequalities? Commented Jan 31, 2020 at 6:34
• @omrib40 - the absolute value makes sense, if you don't know on what side of the line your point is. However, you know that - try to use this info to get rid of absolute value Commented Jan 31, 2020 at 17:59

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.