Триангуляция вручную

[rtfai]

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

[mihailm]

На олимпиаде такие задачи дают что ли?

[sup]

А я вот не пойму. Какие проблемы с триангуляцией выпуклого многоугольника. Как там, метод "отрезания ушей". Так вроде называется простейший алгоритм. Короче говоря. Отрезаем по одной вершине и всего то делов. Или речь идет о триангуляции Делоне?

[rtfai]

sup в сообщении #825359 писал(а):

А я вот не пойму. Какие проблемы с триангуляцией выпуклого многоугольника. Как там, метод "отрезания ушей". Так вроде называется простейший алгоритм. Короче говоря. Отрезаем по одной вершине и всего то делов. Или речь идет о триангуляции Делоне?

Оценка может быть по полноте ответа, т.е. не просто трюк. Есть еще "стесывание и зарубка", и та же тринагуляция Делоне. Если изменить условие "вручную, за минуту" на "равномерно", то можно надеятся на то, что студент дойдет до решения $ \Delta x=0, \Delta y=0$

[TOTAL]

rtfai в сообщении #825344 писал(а):

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

Вручную ставлю точку внутри треугольника, затем вручную соединяю её с каждой вершиной. Засекал, удается триангулировать практически любой выпуклый 20-угольник секунд за 10.

[mihailm]

TOTAL в сообщении #825584 писал(а):

...Вручную ставлю точку внутри треугольника, затем вручную соединяю её с каждой вершиной. Засекал, удается триангулировать практически любой выпуклый 20-угольник секунд за 10.

Это если многоугольник не очень большой (сравним с тетрадным листом). А если многометровый?

[ewert]

sup в сообщении #825359 писал(а):

Как там, метод "отрезания ушей".

TOTAL в сообщении #825584 писал(а):

Вручную ставлю точку внутри треугольника, затем вручную соединяю её с каждой вершиной.

rtfai в сообщении #825344 писал(а):

и у которого длины сторон отличаются не более чем в два раза.

Явно имелось в виду "у которых". Правда, непонятно, почему именно в два раза.