невыпуклая оболочка

[LmRARtist]

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

Как я понимаю необходимо построить НЕвыпуклую оболочку, задавая размер ребра не меньше кого-либо определенного значения. В инете и куче книг ничего подходящего найти не получается. Подскажите где искать или какие -нибудь идеи по данной тематики.
PS - английский язык очень слабо знаю.
Заранее спасибо.

[venco]

LmRARtist в сообщении #502164 писал(а):

каких либо всплесков

Что вы имеете в виду?

Я думаю, надо начинать как раз с выпуклой оболочки - она даст минимальное количество вершин. А затем вырезать от границы треугольники, не содержащие других вершин. Найти глобальный минимум, скорее всего, можно только полным перебором, но достаточно хорошее решение можно найти и greedy вырезанием.

[LmRARtist]

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

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

Результирующая оболочка должна быть как можно компактнее. периметр минимальный, при как можно меньшей площади.

Буду искать дальше. Придумал алгоритм, возможно неверный, как реализую, напишу.