Согласен с Палестинцем.

в принципе хватит и троек + итерационный метод.
итого - 2*N*log( точности )

Не согласен. Во-первых, метод просто точный, т.е. положение и радиус окружности находятся точно при переборе, о каких итерациях идёт речь? Во-вторых, уже для выпуклого многоугольника трудоёмкость при таком подходе O(N*(N^2 + O(1)*N)), т.е. O(N^3), откуда возьмётся N*log(точности??) непонятно.

А в этом случае алгоритм найдёт конечное число решений (в случае прямоугольника два по концам), вот и всё, могу легко продемонстрировать. Вам как пользователю останется лишь выбрать то, которое Вам больше нравится.

ПалестинецN^2 + O(1)*N .. - умножить наверно надо..

Не, умножать не надо. Имелось ввиду что в выпуклом многоугольнике окружность может касаться только по сторонам. Поэтому для каждой отдельно взятой стороны строим N - 1 биссектрис углов, образованных данной стороной и остальными N - 1 сторонами, если какая-либо сторона параллельна данной, то в качестве биссектрисы берем прямую параллельную
обоим и находящуюся от них на равных расстояниях. В общем случае эти N - 1 биссектрис пересекутся в (N - 1)*(N - 2)/2 точках. Для каждой из этих точек пресечения проверим что 3 перпендикуляра из данной точки пересечения двух биссектрис на три стороны, которыми образованы два рассматриваемых угла, попадают внутрь этих трёх сторон. Это O(N^2) операций. После этого отсева у нас останется O(1) точек которые удовлетворают данному условию. Эти оставшиеся точки проверяем на условие не выхода за пределы многоугольника, итого ещё O(1)*O(N) операций. В результате для N шагов имеем N*(O(N^2) + O(1)*O(N)) или O(N^3).

Neekaа если решать с помощью диаграмы Вороного? может кто подскажет алгоритм?

Да забудьте Вы Вороного, внимательно читайте этот пост, здесь уже для Вас эту задачу решили, если Вы этого не понимаете, то всё дальнейшее бесполезно... На всякий случай скажу вот это:

1.Для ЛЮБЫХ трёх непересекающихся отрезков на плоскости можно определить существует или нет окружность которая будет касаться всех трёх. Для этого существуют точные аналитические формулы. Далее, если такая окружность существует, то она единственна и положение её центра и её радиус можно точно определить. Для этого существуют точные аналитические формулы.

2.Для ЛЮБЫХ двух непересекающихся отрезков и точки на плоскости можно определить существует или нет окружность которая будет касаться двух отрезков и проходить через точку. Для этого существуют точные аналитические формулы. Далее, если такая окружность существует, то она единственна и положение её центра и её радиус можно точно определить. Для этого существуют точные аналитические формулы.

3.Для ЛЮБОГО отрезка и двух точек на плоскости можно определить существует или нет окружность которая будет касаться отрезка и проходить через обе точки. Для этого существуют точные аналитические формулы. Далее, если такая окружность существует, то она единственна и положение её центра и её радиус можно точно определить. Для этого существуют точные аналитические формулы.

4.Для ЛЮБЫХ трёх точек на плоскости... ну это знают все дети.

Aklinпример где по трем не построишь.

А Вы, я смотрю, продолжаете упорствовать. Тогда обратите внимание на пункт 2 выше.

Что ж, Вы правы, для случая одной точки и двух отрезков и двух точек и отрезка замените:

Далее, если такая окружность существует, то она единственна и положение её центра и её радиус можно точно определить...

на

Далее, если такая окружность существует, то их может быть не более 2х и положение их центров и радиусы можно точно определить...

С точки зрения алгоритма это мало что меняет, на одну проверку для каждого шага больше, только и всего.