Теоремы и алгоритмы художественной галереи

«Теоремы и алгоритмы художественной галереи» — математическая монография по темам, связанным с проблемой художественной галереи , по поиску позиций охранников в полигональном плане музея, чтобы все точки музея были видны хотя бы одному охраннику, а также по смежным проблемам вычислительной геометрии. по поводу полигонов . Она была написана Джозефом О'Рурком и опубликована в 1987 году в Международной серии монографий по информатике издательства Oxford University Press . До того, как книга вышла из печати, было выпущено всего 1000 экземпляров, поэтому, чтобы сохранить доступность этого материала, О'Рурк разместил в Интернете версию книги в формате pdf.

Темы

Задача художественной галереи , поставленная Виктором Клее в 1973 году, требует определения количества точек, в которых можно разместить охранников внутри многоугольника (представляющего план этажа музея), чтобы каждая точка внутри многоугольника была видна хотя бы одному охраннику. Вацлав Хватал представил первое доказательство того, что ответ не более чем $\lceil n/3\rceil$ для многоугольника с $n$ упрощенное доказательство Стива Фиска, основанное на раскраске графов и триангуляции многоугольников углы, но более широко известно . Это вступительный материал книги. который охватывает такие темы, как видимость , разложение многоугольников, покрытия многоугольников , триангуляции и алгоритмы триангуляции, а также многомерные обобщения, включая тот результат, что некоторые многогранники, такие как многогранник Шенхардта, не имеют триангуляции без дополнительных вершин. В более общем плане тема книги — «взаимодействие дискретной и вычислительной геометрии».

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

Аудитория и прием

Книга требует лишь знаний теории графов и алгоритмов на уровне бакалавриата . Однако в нем отсутствуют упражнения, и он организован скорее как монография, чем как учебник. Несмотря на предупреждение о том, что в нем опущены некоторые детали, которые были бы важны для разработчиков описываемых алгоритмов, и не описаны алгоритмы, которые хорошо работают на случайных входных данных, несмотря на низкую сложность в худшем случае, рецензент Wm. Рэндольф Франклин рекомендует его «в библиотеку каждого геометра».

Рецензент Герберт Эдельсбруннер пишет: «Эта книга представляет собой наиболее полный сборник результатов по многоугольникам, доступный в настоящее время, и, таким образом, заслуживает свое место в качестве стандартного текста по вычислительной геометрии. Она очень хорошо написана, и ее приятно читать». Однако рецензент Патрик Дж. Райан жалуется, что некоторые корректуры в книге неэлегантны. а рецензент Дэвид Эвис , писавший в 1990 году, отметил, что уже к тому времени произошло «много новых событий», сделавших книгу устаревшей. Тем не менее, Авис пишет, что «книга имеет успех на нескольких уровнях»: как вводный текст для студентов или исследователей в других областях, а также как приглашение решить «многие нерешенные вопросы», оставшиеся в этой области.