Largest Circle in a Polygon

Question

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?

@ 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

score 1 · Accepted Answer · answered Oct 31 '13 at 22:43

1

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

answered Oct 31 '13 at 22:43

gt6989b

54,422

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

Largest Circle in a Polygon

1 Answers1