Теоремы и алгоритмы художественной галереи - Википедия - Art Gallery Theorems and Algorithms

Теоремы и алгоритмы художественной галереи математическая монография по темам, связанным с проблема художественной галереи, о поиске позиций для охранников на многоугольной схеме этажа музея, чтобы все точки музея были видны хотя бы одному охраннику, и о связанных проблемах в вычислительная геометрия касательно полигоны. Это было написано Джозеф О'Рурк и опубликованы в 1987 году в Международной серии монографий по компьютерным наукам Oxford University Press.^{[1][2][3][4][5]} До того, как книга вышла из печати, было выпущено всего 1000 копий, поэтому, чтобы этот материал оставался доступным, О'Рурк сделал версию книги в формате pdf, доступную онлайн.^[6]

Темы

В проблема художественной галереи, поставленный Виктор Клее в 1973 году, запрашивает количество точек, в которых разместить охранников внутри многоугольника (представляющего план этажа музея) так, чтобы каждая точка внутри многоугольника была видна хотя бы одному охраннику. Вацлав Хваталь предоставил первое доказательство того, что ответ не более ${ Displaystyle lceil п / 3 rceil}$ для многоугольника с ${ displaystyle n}$ углов, но упрощенное доказательство Стива Фиска на основе раскраска графика и триангуляция многоугольника более широко известен. Это вступительный материал книги,^[3] который охватывает темы, включая видимость, разложения многоугольников, покрытия полигонов, алгоритмы триангуляции и триангуляции, а также многомерные обобщения,^[1] включая результат, что некоторые многогранники такой как Многогранник Шёнхардта не имеют триангуляции без дополнительных вершин.^[1][4] В более общем смысле, тема книги «Взаимодействие дискретной и вычислительной геометрии».^[3]

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

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

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

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

Рекомендации