Is there an simple algorithm for calculating maximum inscribed circle into a convex polygon?

Up vote 5 down vote favorite share g+ share fb share tw.

I found some solutions, but they're too messy. Algorithm linear-algebra linear-programming convex-optimization convex-polygon link|improve this question edited Oct 31 '10 at 3:47Steve Tjoa7,36911538 asked Oct 17 '10 at 14:31Csaryus4518 57% accept rate.

1 Interesting problem. – Jungle Hunter Oct 17 '10 at 14:48.

I can suggest a simple, but potentially imprecise solution, which uses numerical analysis. Assume you have a resilient ball, and you inflate it, starting from radius zero. If its center is not in the center you're looking for, then it will move, because the walls would "push" it in the proper direction, until it reaches the point, from where he can't move anywhere else.

I guess, for a convex polygon, the ball will eventually move to the point where it has maximum radius. You can write a program that emulates the process of circle inflation. Start with an arbitrary point, and "inflate" the circle until it reaches a wall.

If you keep inflating it, it will move in one of the directions that don't make it any closer to the walls it already encounters. You can determine the possible ways where it could move by drawing the lines that are parallel to the walls through the center you're currently at. In this example, the ball would move in one of the directions marked with green: Then, move your ball slightly in one of these directions (a good choice might be moving along the bisection of the angle), and repeat the step.

If the new radius would be less than the one you have, retreat and decrease the pace you move it. When you'll have to make your pace less than a value of, say, 1 inch, then you've found the centre with precision of 1 in. (If you're going to draw it on a screen, precision of 0.5 pixel would be good enough, I guess).

If an imprecise solution is enough for you, this is simple enough, I guess.

Yes. The Chebyshev center, x*, of a set C is the center of the largest ball that lies inside C. Boyd, p.

416 When C is a convex set, then this problem is a convex optimization problem. Better yet, when C is a polyhedron, then this problem becomes a linear program. Suppose the m-sided polyhedron C is defined by a set of linear inequalities: ai^T x = 0 where the variables of minimization are R and x, and ||a|| is the Euclidean norm of a.

Summary: It is not trivial. So it is very unlikely that it will not get messy. But there are some lecture slides which you may find useful.

Source: eggheadcafe.com/software/aspnet/30304481... Your problem is not trivial, and there is no C# code that does this straight out of the box. You will have to write your own. I found the problem intriguing, and did some research, so here are a few clues that may help.

First, here's an answer in "plain English" from mathforum.org: http://mathforum.org/library/drmath/view/67030. Html The answer references Voronoi Diagrams as a methodology for making the process more efficient. In researching Voronoi diagrams, in conjunction with the "maximum empty circle" problem (same problem, different name), I came across this informative paper: cosy.sbg.ac.

At/~held/teaching/compgeo/slides/vd_slides. Pdf It was written by Martin Held, a Computational Geometry professor at the University of Salzberg in Austria. Further investigation of Dr. Held's writings yielded a couple of good articles: cosy.sbg.ac.

At/~held/projects/vroni/vroni. Html cosy.sbg.ac. At/~held/projects/triang/triang.

Html Further research into Vornoi Diagrams yielded the following site: http://www.voronoi.com/ This site has lots of information, code in various languages, and links to other resources. Finally, here is the URL to the Mathematics and Computational Sciences Division of the National Institute of Standards and Technology (U.S.), a wealth of information and links regarding mathematics of all sorts: http://math.nist.gov/mcsd/ -- HTH, Kevin Spencer Microsoft MVP.

1 This bulk of this reply text from Kevin Spencer refers to the problem involving concave or convex polygons. The problem might be much easier in the convex case. – Josephine Oct 18 '10 at 14:41 @Josephine: Might be.

I haven't gone through in detail, but might be. Perhaps you have something on your mind? – Jungle Hunter Oct 18 '10 at 17:31 After commenting here, I also posted an answer.

My ideas are there. – Josephine Oct 19 '10 at 12:00 The problem is definitely easier when the polygon is convex. The problem becomes a linear program.

I posted an answer, too. – Steve Tjoa Oct 31 '10 at 3:43.

The largest inscribed circle (I'm assuming it's unique) will intersect some of the faces tangentially, and may fail to intersect others. Let's call a face "relevant" if the largest inscribed circle intersects it, and "irrelevant" otherwise. If your convex polygon is in fact a triangle, then the problem can be solved by calculating the triangle's incenter, by intersecting angle bisectors.

This may seem a trivial case, but even when your convex polygon is complicated, the inscribed circle will always be tangent to at least three faces (proof? Seems geometrically obvious), and so its center can be calculated as the incenter of three relevant faces (extended outwards to make a triangle which circumscribes the original polygon). Here we assume that no two such faces are parallel.

If two are parallel, we have to interpret the "angle bisector" of two parallel lines to mean that third parallel line between them. This immediately suggests a rather terrible algorithm: Consider all n-choose-3 subsets of faces, find the incenters of all triangles as above, and test each circle for containment in the original polygon. Maximize among those that are legal.

But this is cubic in n and we can do much better. But it's possible instead to identify faces that are irrelevant upfront: If a face is tangent to some inscribed circle, then there is a region of points bounded by that face and by the two angle bisectors at its endpoints, wherein the circle's center must lie. If even the circle whose center lies at the farthest tip of that triangular region is "legal" (entirely contained in the polygon), then the face itself is irrelevant, and can be removed.

The two faces touching it should be extended beyond it so that they meet. By iteratively removing faces which are irrelevant in this sense, you should be able to reduce the polygon to a triangle, or perhaps a trapezoid, at which point the problem will be easily solved, and its solution will still lie within the original polygon.

Seems geometrically obvious) doesn't seem to hold. – Jungle Hunter Oct 19 '10 at 13:47 In both cases you describe, "the" largest inscribed circle is not unique, but among all largest inscribed circles, at least one intersects three sides. – Josephine Oct 19 '10 at 19:34 even if it was only for such cases, you need to somehow know if the largest inscribed circle is not unique.

– Jungle Hunter Oct 20 '10 at 13:17 1 the polygon is convex, so the largest inscribed circle is unique. – Csaryus Nov 5 '10 at 21:11.

I cant really gove you an answer,but what I can give you is a way to a solution, that is you have to find the anglde that you relate to or peaks your interest. A good paper is one that people get drawn into because it reaches them ln some way.As for me WW11 to me, I think of the holocaust and the effect it had on the survivors, their families and those who stood by and did nothing until it was too late.