0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – D.W. Jan 30 at 17:00
  • $\begingroup$ 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. $\endgroup$ – omrib40 Jan 30 at 17:17
  • $\begingroup$ 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. $\endgroup$ – D.W. Jan 30 at 17:51
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – omrib40 Jan 30 at 19:21
  • $\begingroup$ @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 $\endgroup$ – HEKTO Jan 30 at 20:20
  • $\begingroup$ 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? $\endgroup$ – omrib40 Jan 31 at 6:34
  • $\begingroup$ @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 $\endgroup$ – HEKTO Jan 31 at 17:59
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.