# Largest Circle in a Polygon

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?

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

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)$
• 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. – Islands Oct 31 '13 at 23:35