Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

Темы [ править ]

Задача художественной галереи , поставленная Виктором Клее в 1973 году, требует количества точек, в которых разместить охранников внутри многоугольника (представляющего план этажа музея), чтобы каждая точка внутри многоугольника была видна хотя бы одному охраннику. Вацлав Хватал предоставил первое доказательство того, что ответ - самое большее для многоугольника с углами, но более широко известно упрощенное доказательство Стива Фиска, основанное на раскраске графа и триангуляции многоугольника . Это вводный материал книги [3], который охватывает такие темы, как видимость , разложение многоугольников, покрытия многоугольников., алгоритмы триангуляции и триангуляции, а также многомерные обобщения [1], включая результат о том, что некоторые многогранники, такие как многогранник Шёнхардта , не имеют триангуляций без дополнительных вершин. [1] [4] В целом, книга посвящена «взаимодействию дискретной и вычислительной геометрии». [3]

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

Аудитория и прием [ править ]

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

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

Ссылки [ править ]

  1. ^ a b c d Эдельсбруннер, Герберт (1989), "Обзор теорем и алгоритмов художественной галереи ", Mathematical Reviews , MR  0921437
  2. ^ a b c Влах, М., "Обзор теорем и алгоритмов художественной галереи ", zbMATH , Zbl 0653.52001 
  3. ^ a b c d e Авис, Дэвид (1990), «Обзор теорем и алгоритмов художественной галереи », Американское математическое общество , новая серия, 23 (1): 230–234, DOI : 10.1090 / S0273-0979-1990-15939 -7 , Руководство по ремонту 1567872 
  4. ^ a b c Франклин, Wm. Рэндольф (июнь 1989), "Обзор художественной галереи теорем и алгоритмов ", SIAM Review , 31 (2): 342-343, DOI : 10,1137 / 1031076
  5. ^ a b c Райан, Патрик Дж., «Обзор теорем и алгоритмов художественной галереи » , ACM Computing Reviews
  6. ↑ О'Рурк, Джозеф , Теоремы и алгоритмы художественной галереи , Колледж Смита , получено 20 февраля 2020 г.