Chvátal's art gallery theorem failed?

[bigarcus]

[g______d]

Я вижу 5 вершин, из которых видно всё.

[longstreet]

Black vertices.

[bigarcus]

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

[svv]

А у Вас правильная раскраска?
В Вашей галерее есть две такие самые большие залы, левая и правая, почти треугольной формы. Станьте примерно в центр одной из них, например, правой. Какому треугольнику принадлежит этот центр? Из центра видно только три вершины, поэтому: треугольнику, образованному этими тремя вершинами. Но они все черного цвета. А в Wiki сказано: The vertices of the polygon are then 3-colored in such a way that every triangle has all three colors.

-- Пн июл 15, 2013 17:54:43 --

[bigarcus]

И какой тут алгоритм? Как формально выбирать вершины, в которые стражников ставить?

[longstreet]

Интересно, а тот факт, что любой триангулированный многоугольник можно так раскрасить в три цвета -- можно ли как-то доказать, не прибегая к индукции?

[svv]

bigarcus
Вся площадь галереи поделена на треугольники. Любой треугольник освещается тремя лампами, расположенными в вершинах: красной, желтой и зеленой. Лампа любого цвета освещает треугольник полностью. Значит, уже только жёлтые лампы освещают всю галерею. (Ну, равно как только красные, или только зелёные).

И выбирать советую не тот цвет ламп, которых больше, а, наоборот, которых меньше. Потому что для них есть гарантия, что их не больше $\lfloor n/3 \rfloor$. (Если ламп каждого цвета будет больше $\lfloor n/3 \rfloor$, их будет слишком много).

Если вопрос был о том, каков алгоритм выполнения триангуляции, и, далее, каков алгоритм раскрашивания вершин, то — не знаю. Просто в Вашем примере это не составило труда.

[longstreet]

svv, я не помню: а задача с освещением произвольного зеркального многоугольника с помощью одной лампочки решена?

[svv]

longstreet, по секрету: я до сегодняшнего дня об Art gallery theorem слыхом не слыхивал. Мои ответы — это авантюризм. Рад, если это не сразу заметно.

По поводу задачи, о которой Вы говорите — тоже ничего не знаю.