Re: Exercise from Cormen

From

Andrey Tarasevich ()

To

Yurij Zabelyshynskij

Date

2002-12-07T11:36:30Z

Area

RU.ALGORITHMS

From: Andrey Tarasevich <atarasevich@telocity.com>

Yurij Zabelyshynskij wrote:
> ...
> Многие подписчики знают книгу Кормена и др. Есть там упражнение
> 35.1-4, цитирую:
> 
> "Чтобы узнать, являются ли точки p_i, i от 0 до n-1, вершинами
> выпуклого многоугольника, перечисленными в порядке обхода
> многоугольника, профессор предлагает проверить, что множество углов
> (p_i, p_i+1, p_i+2), i от 0 до n-1, i+1 и i+2 вычисляются по модулю n,
> не содержит одновременно правых и левых поворотов. Покажите, что этот
> способ не всегда дает правильный ответ".
> Рассматриваемые многоугольники являются несамопересекающимися.
> 
> Но я не вижу, в чем неправ профессор. А вы?

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

-- 
Best regards,
Андрей.

--- ifmail v.2.15dev5
 * Origin: good enough (2:5020/400)