softwarer aleks2Не обязан.
Обязан. Вписанная окружность обязана касаться каждой из сторон многоугольника, для невыпуклого многоугольника это условие невыполнимо.

имеется ввиду не вписананя окружность, а окружность наибольшего радиуса, находящяяся внутри многоугольника.

берем 1 угол, да так, что он обязятельно внутри.
и начинаем разростать окружность до тех пор, пока он куда-нибудь не упрется.
потом берем следующий угол.

все углы - внутренние.

аффтопитезь

я сразу скажу, что вам нужен будет ну очень неплохой компьютер. т.к. съедать алгоритм будет много премного.

далее.
возьмем расстояние А = максимально удаленные две точки многоуголника.

Для каждой прямой знаем (xa, ya )-(xb, yb)

далее.
для каждой точки многоулгольника (зная обе линии, коими эта вершина образована, позаботится заранее) берем нашу R = A/2 и D = A. Центр - на биссектриссе. расстояние от вершины до центра можно ввести программно (формулу вывести и ввести). Смотрим для каждой прямой, не пересекает ли прямая окружность. это решается. я думая стоит решать в общем виде, а не перебирать точки. (например задать программное уравнение, или условие, пока не решал как именно ) (кстати, по-моему самый толстый момент). Если пересекает хоть одну, то R = R/2. Если нет, то D = D/2, R = R + D. до определенно малого D.

Теперь прикидываем.
[кол-во вершин]*[log( точности D )]

В принципе не так уж и сложно. а вот программить замудохаца.

аффтопитезь

Палестинец2Aklin .
Если решать ту задачу которую ты решаешь(а не автор). то можно вот так:

максимальная окружность содержащаяся в многоугольнике обязана

1) лежать на 3 вершинах с внутренним углом > 90
OR
2) касаться 1 стороны и содержать 2 вершины с внутренним углом > 90
OR
3) касаться 2 сторон и содержать 1 вершину с внутренним углом > 90
OR
4) касаться 3 сторон

итого перебор всех этих случаев по всем вершинам и сторонам многоугольника - O(N^3) операций. но c оч большим простором для оптимизаций и отсеивания заведомо неподходящих случаев..

я еще забыл действительно.
если окружность будет на 3 вершинах только, например.
N - колдичество вершин? так это немного. я бы сказал от N^3*log( точность ) до N^3*log( точность )^4

ну нафига???Не мучайся!
Учите матчасть.
http://]www.bymath.net/studyguide/geo/sec/geo11.htm

там только про 4х угольники да правильные многоугольники