Где можно найти алгоритм?

[Ramm13]

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

[VAL]

Ramm13 в сообщении #510423 писал(а):

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

А его нужно искать?

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

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

[Sonic86]

Быть может спросить здесь: http://forum.algolist.ru/algorithm-geometry/
искать в книгах по вычислительной геометрии

[Ramm13]

Алгоритм должен приводить к результату за время O(N*log(N))

[Sonic86]

Ramm13 в сообщении #510928 писал(а):

Алгоритм должен приводить к результату за время O(N*log(N))

Вам нужен итеративный алгоритм, подходящий к результату сколь угодно близко, или точная формула? В случае точной формулы ответ вот:

VAL в сообщении #510750 писал(а):

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

Из физических соображений видно, что для выпуклого треугольника решение существует и единственно. Ну и ищите градиентным методом попеременно на прямых, параллельных то оси Ox, то оси Oy. Максимум расстояния на каждой прямой ищите двоичным поиском, вычисляя расстояния до всех ребер - итого $O(n \ln n)$ операция на каждом шаге, а всего значит $O(n \ln ^2 n)$, что несущественно медленнее, чем $O(n \ln n)$
Попробуйте это для начала. Возможно, что-то по ходу дела придумаете сами. Если мало, то надо рыться в книгах и статьях, там не совсем все так просто и до наиболее оптимального алгоритма додуматься, не зная вспомогательных алгоритмов, бывает трудно (на АСМ-олимпиадах нужно знать именно оптимальные алгоритмы).

[Indy]

В начале наверно нужно первичное, опорное значение окружности определить, далее это значение изменять. Возникает проблема с формой, ведь может быть например несколько окружностей - для каждой части фигуры своя.
Что такое вписанная окружность - это поверхность или совокупность точек, лежащих внутри фигуры на границе, которая может быть формально описана. Расстояние между двумя точками фигуры, в которую вписывается другая фигура(в данном случае окружность) больше либо равно расстоянию между точками окружности в данной координате.
Если описать поверхность фигуры последовательно, то можно найти лимиты проекций на две оси. Очевидно большая окружность та, которая занимает большую площадь, тоесть сумма расстояний между точками для участка проекций поверхности наибольшая, причём расстояние между точками минимальное для всей поверхности.
Для такого вычисления я бы описал поверхность векторами(попиксельно).

[VPro]

Данная задача есть задача вычисления максимина. Пусть $x,y$ --- искомые координаты центра окружности. Обозначим $D_k(x,y)$ --- расстояние от точки $(x,y)$ до $k-$ой прямой. $D_k(x,y)$ --- линейные функции, их знак выбирается из условия принадлежности точки внутренности многоугольника. Тогда радиус искомой окружности равен $\max_{x,y}\min_k D_k(x,y)$. А центр $(x,y)$ --- точка достижения максимума.
Методы решения таких задач разработаны и их можно найти любой книге по минимаксу. Например, в этих:
Демьянов В.Ф., Малоземов В.Н. Введение в минимакс.- М.: Наука, 1972.- 368 с.
Федоров В.В. Численные методы максимина.- М.: Наука, 1979.- 278 с.

[vjung]

линейное программирование подойдёт?

maximize r:
s.t. $a_i^Tx_c+r\|a_i\|_2 \leq b_i$, i=1..m

где $x_c$ -- координаты центра шара, а многоугольник определяется как множество {$a_i^T x \leq b_i $, i=1..m}