Наибольшее выпуклое множество

Genmaximus

существует ли какой-нибудь алгоритм выделения наибольшего выпуклого множества, целиком содержащегося в данном?

valds75

В каком смысле наибольшего? Очевидно, не существует такого, которое содержит все остальные.

Diman0606

Может, имеющего максимальную меру...

slo14

Наверное, можно переформулировать задачу так: разбить данное множество на наименьшее число выпуклых подмножеств.
Причем слова "наименьшее число" нуждаются в уточнении.

omni51776

Есть еще вариант уточнения...М.б. необходимо найти все такие элементы множества , Выпукл.Комбинация которых пересеченная с начальным множеством была бы максимальной?

Genmaximus

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

omni51776

Мы говорим с тобой о разных областях одной науки

slo14

Дык связную или выпуклую?
Если выпуклую, то проблема вот:

Здесь три множества, каждое из которых при малых деформациях может стать наибольшим.

Genmaximus

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

Sanych

В целом, конечно, получилась ерунда, но во всяком случае какой-то подход есть:
Наибольшее выпуклое обладает следующим свойством:
опорная прямая -- если конечно она не проходит через точку пересечения 2 касательных -- обязана быть касательной к границе нашего множества хотя бы в одной точке.
Идея док-ва: иначе к участку нашего "наибольшего" выпуклого множества можно ещё добавить шапочку.
Так как выпуклое множество есть пересечение своих опорных полуплоскостей, это становится довольно полезным соображением, на основе которого можно построить что-то вроде алгоритма.
Ну и пример, с 3-параметрическим семейством наибольших треугольников -- криволинейный треугольник с выпуклыми внутрь сторонами.
Также не забыть про утверждение, что достаточно задавать не всё наибольшее множество, а лишь его пересечение с границей исходного. И то, что даже бесконечной гладкости для части этих рассуждений может не хватить, если специально брать мерзкую границу. А вот кусочной выпуклости/вогнутости с конечным числом кусков вроде вполне хватит.
/------------
На этот вопрос для достаточно хорошей границы есть такая схема, которая казалась близкой к алгоритму:
а) наибольшее выпуклое подмножество определяется своим пересечением с границей [скорее всего]
б) участок границы наибольшего выпуклого множества, содержащего данную точку, отходящий в одну сторону -- либо касательная в данной точке, либо граница исходного множества, либо является касательной в другом конце
Впрочем, надо заметить, что и вообще наибольших множеств может быть бесконечно много, тем не менее в общем они так и определяются по участкам границы исходного множества+касательным в концах этих участков.
Фактически, это всё должно быть более-менее понятно если представлять выпуклое множество как пересечение полуплоскостей
Тогда понятно, что опорная прямая обязана быть касательной к границе нашего множества хотя бы в одной точке, так как иначе к участку нашего "наибольшего" выпуклого множества можно ещё добавить шапочку.
Итог: для кусочно гладкой границы исходного множества можно начинать с одной касательной, потом выбирать следующую, и так далее обходя таким образом наше выпуклое множество например против часовой стрелки.

Genmaximus

Сапсибо, надеюсь поможет.
Оставить комментарий
Имя или ник:
Комментарий: