3
$\begingroup$

My polygon is given by $P=$$\left\{x\geq 0, y\geq 0, 3x-4y\leq 2, 4x+3y\leq 12\right\}$

Now trying to find the largest circle inscribed inside these half-planes. But whenever I formulate it as an LP problem, the answers don't make sense. I'm using the method of Chebyshev Center and these notes. So then I get:

Maximize r

Subject to the constraints:

$3x_c + 5r \leq 2$

$-4x_c + 5r \leq 2$

$4x_c + 5r \leq 12$

$3x_c + 5r \leq 12$

Plugging into maple I get $(x_c, r) = (1/4, 1/4)$ but that doesn't really make sense. Is there something wrong with my formulation?

$\endgroup$
  • 1
    $\begingroup$ Hint! Draw the figure and find the bisectors. $\endgroup$ – Carlos Eugenio Thompson Pinzón Oct 31 '13 at 22:12
  • $\begingroup$ @ Carlos: Can't do it that way. @ Will Jagy: Could you be a little more specific in what you mean? $\endgroup$ – Islands Oct 31 '13 at 22:23
  • $\begingroup$ @CarlosEugenioThompsonPinzón Your solution leads to the short form in the notes he cites :). It is quite clever. $\endgroup$ – gt6989b Oct 31 '13 at 22:45
1
$\begingroup$

In your notes, $x_c$ is a 2-d vector. If you write it out, a circle is represented by the center $(x,y)$ and radius $r$, so you need to maximize $r$ subject to

  • $4x+3y+5r \leq 12$,
  • $3x-4y+5r \leq 2$,
  • and $x \geq r$ and $y \geq r$ with $r \geq 0$,

which is indeed a LP. Solve it using Wolfram Alpha to get $(x,y,r) = (0.9, 1.3, 0.9)$

$\endgroup$
  • $\begingroup$ Oh my gosh. I can't believe I overlooked that. I was wondering why $x_c$ was merely a value instead of two points. It all makes perfect sense now. Thank you. $\endgroup$ – Islands Oct 31 '13 at 23:35

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.