В представленном здесь алгоритме для всех сторон и невыпуклых вершин многоугольника строятся границы областей близости по типу диаграммы Вороного. Узлы этих областей являются центрами вписанных окружностей. После того, как все эти окружности найдены из них выбирается одна с максимальным радиусом:

Def<Circle2d> maxCircleInPolygon ( CCArrRef<Vector2d> & vert );

Мои тесты показали, что временная сложность этого алгоритма приблизительно равна O ( n^1,5 ), где n - это количество вершин многоугольника.

В приложении DEMO можно посмотреть результат вписания.

Описание класса Circle2d находится здесь.
Описание шаблона классов CArrRef находится здесь.
Описание шаблона классов Def находится здесь.
Описание класса Vector2d находится здесь.
Исходники алгоритма находятся в файле opti2d.cpp.