Задача о картинной галерее: почему n/3 охранников всегда хватает

Если ты знаешь теорему о галерее, доказательство через раскраску триангуляции в три цвета и почему гребёнке нужно n/3 охранников, листай до «Теперь сам».

Как думаешь, сколько охранников

Музей - один зал сложной формы, многоугольник из 32 вершин. Охранник стоит на месте и видит всё, до чего можно провести отрезок, не выходя из зала. Сколько охранников нужно в худшем случае - для самого неудобного зала из 32 вершин?

Ответь себе до чтения: столько, сколько вмятин? Половина вершин? Ответ: никогда не больше 10 - трети вершин с округлением вниз, - и бывают залы (гребёнка из десяти зубцов), где меньше 10 нельзя. Причём расставить этих десятерых можно почти механически.

На что это похоже

Расстановка камер в квартире-лабиринте. Если разрезать квартиру на треугольные куски, камера в углу треугольника видит весь этот треугольник - он выпуклый. Значит, хватит камер, чтобы в каждом треугольнике был угол с камерой. Если покрасить углы в три цвета так, что у каждого треугольника все три цвета есть, то камеры в углах любого одного цвета закроют все треугольники. Остаётся выбрать самый редкий цвет.

Механизм: раскраска дерева треугольников

Почему раскраска в три цвета существует. Триангуляция многоугольника - это треугольники, соединённые в дерево через диагонали (прошлый урок). Раскрась вершины первого треугольника тремя цветами. Соседний треугольник делит с ним диагональ - две вершины уже раскрашены разными цветами, третьей достаётся оставшийся цвет. Пройдя дерево от треугольника к соседу, раскрашиваем всё. Противоречий нет: когда обход переходит через диагональ, все раскрашенные треугольники лежат по одну её сторону, а третья вершина нового треугольника - по другую. Диагональ режет многоугольник надвое, и вершина той стороны принадлежит только треугольникам той стороны - раскрасить её ещё никто не успел.

Почему это ⌊n/3⌋. Три цвета на n вершинах - самый редкий цвет встречается не больше n/3 раз, а число охранников целое. Каждый треугольник содержит вершину этого цвета, а треугольник выпуклый, так что охранник в его вершине видит его целиком. Треугольники покрывают зал - значит, видно всё.

Почему меньше нельзя. Гребёнка: основание и k острых зубцов. Кончик зубца виден из узкого клина: сам зубец и полоска основания прямо под ним. В гребёнке из программы ниже зубец у основания шириной 2 и высотой 8, прямые от кончика через углы зубца расходятся на 1 вбок за 8 вниз, и за оставшиеся 2 до пола клин шире зубца на четверть с каждой стороны, а между зубцами 2. Клинья не пересекаются - один охранник не видит двух кончиков, и на каждый зубец нужен свой - k штук при n = 3k + 2 вершинах, то есть ⌊n/3⌋.

Правило

Для простого многоугольника с n вершинами ⌊n/3⌋ охранников всегда достаточно и иногда необходимо. Расстановка: триангуляция, раскраска вершин в три цвета обходом дерева треугольников, охранники в вершинах самого редкого цвета. Наименьшее число охранников для данного зала найти NP-трудно.

Разбор: стрелка из прошлого урока

schet = [0]

def povorot(a, b, c):
    schet[0] = schet[0] + 1
    return (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0])

def uho(poly, ost, k):
    # вершина ost[k] - ухо, если угол при ней выпуклый и внутри
    # треугольника (соседи и она) нет других оставшихся вершин
    m = len(ost)
    a = poly[ost[(k - 1) % m]]
    b = poly[ost[k]]
    c = poly[ost[(k + 1) % m]]
    if povorot(a, b, c) <= 0:
        return False
    for j in ost:
        p = poly[j]
        if p == a or p == b or p == c:
            continue
        if povorot(a, b, p) >= 0 and povorot(b, c, p) >= 0:
            if povorot(c, a, p) >= 0:
                return False
    return True

def otrezat_ushi(poly):
    # poly - против часовой стрелки; каждый раз - ухо с меньшим номером
    ost = list(range(len(poly)))
    treug = []
    while len(ost) > 3:
        k = 0
        while not uho(poly, ost, k):
            k = k + 1
        m = len(ost)
        treug.append([ost[(k - 1) % m], ost[k], ost[(k + 1) % m]])
        ost.pop(k)
    treug.append(ost)
    return treug
def raskrasit(n, treug):
    # три цвета вершинам так, что у каждого треугольника все три разные
    cvet = [-1] * n
    a, b, c = treug[0]
    cvet[a] = 0
    cvet[b] = 1
    cvet[c] = 2
    est = True
    while est:
        est = False
        for t in treug:
            gotovy = []
            for v in t:
                if cvet[v] >= 0:
                    gotovy.append(cvet[v])
            if len(gotovy) == 2:
                # третья вершина - соседний треугольник через диагональ
                for v in t:
                    if cvet[v] < 0:
                        cvet[v] = 3 - gotovy[0] - gotovy[1]
                est = True
    return cvet

def ohrana(n, treug):
    cvet = raskrasit(n, treug)
    klassy = [[], [], []]
    for v in range(n):
        klassy[cvet[v]].append(v)
    luchshij = klassy[0]
    for k in klassy:
        if len(k) < len(luchshij):
            luchshij = k
    # в каждом треугольнике есть все три цвета, значит, и охранник
    vse = True
    for t in treug:
        est = False
        for v in t:
            if v in luchshij:
                est = True
        if not est:
            vse = False
    razmery = [len(klassy[0]), len(klassy[1]), len(klassy[2])]
    return [razmery, luchshij, vse]
strelka = [[0, 2], [6, 2], [6, 0], [10, 4], [6, 8], [6, 6], [0, 6],
           [3, 4], [1, 3]]
treug = otrezat_ushi(strelka)
print(ohrana(len(strelka), treug), len(strelka) // 3)

[[4, 2, 3], [0, 3], True] 3

Цвета разделили девять вершин на 4, 2 и 3. Самый редкий - два охранника, в вершинах 0 и 3. Проверка True: в каждом треугольнике разрезания есть один из них. Теорема обещала не больше 9 // 3 = 3, а получилось 2 - теорема говорит о худшем зале, а не о каждом.

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

Разбор: гребёнки - где меньше нельзя

Гребёнки с 3, 5 и 8 зубцами. Печатаем число вершин, ⌊n/3⌋, размеры цветов и сколько вышло охранников.

schet = [0]

def povorot(a, b, c):
    schet[0] = schet[0] + 1
    return (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0])

def uho(poly, ost, k):
    # вершина ost[k] - ухо, если угол при ней выпуклый и внутри
    # треугольника (соседи и она) нет других оставшихся вершин
    m = len(ost)
    a = poly[ost[(k - 1) % m]]
    b = poly[ost[k]]
    c = poly[ost[(k + 1) % m]]
    if povorot(a, b, c) <= 0:
        return False
    for j in ost:
        p = poly[j]
        if p == a or p == b or p == c:
            continue
        if povorot(a, b, p) >= 0 and povorot(b, c, p) >= 0:
            if povorot(c, a, p) >= 0:
                return False
    return True

def otrezat_ushi(poly):
    # poly - против часовой стрелки; каждый раз - ухо с меньшим номером
    ost = list(range(len(poly)))
    treug = []
    while len(ost) > 3:
        k = 0
        while not uho(poly, ost, k):
            k = k + 1
        m = len(ost)
        treug.append([ost[(k - 1) % m], ost[k], ost[(k + 1) % m]])
        ost.pop(k)
    treug.append(ost)
    return treug
def raskrasit(n, treug):
    # три цвета вершинам так, что у каждого треугольника все три разные
    cvet = [-1] * n
    a, b, c = treug[0]
    cvet[a] = 0
    cvet[b] = 1
    cvet[c] = 2
    est = True
    while est:
        est = False
        for t in treug:
            gotovy = []
            for v in t:
                if cvet[v] >= 0:
                    gotovy.append(cvet[v])
            if len(gotovy) == 2:
                # третья вершина - соседний треугольник через диагональ
                for v in t:
                    if cvet[v] < 0:
                        cvet[v] = 3 - gotovy[0] - gotovy[1]
                est = True
    return cvet

def ohrana(n, treug):
    cvet = raskrasit(n, treug)
    klassy = [[], [], []]
    for v in range(n):
        klassy[cvet[v]].append(v)
    luchshij = klassy[0]
    for k in klassy:
        if len(k) < len(luchshij):
            luchshij = k
    # в каждом треугольнике есть все три цвета, значит, и охранник
    vse = True
    for t in treug:
        est = False
        for v in t:
            if v in luchshij:
                est = True
        if not est:
            vse = False
    razmery = [len(klassy[0]), len(klassy[1]), len(klassy[2])]
    return [razmery, luchshij, vse]
def grebenka(k):
    # основание и k зубцов; вершин 3k + 2, против часовой стрелки
    poly = [[0, 0], [4 * k, 0]]
    for i in range(k - 1, -1, -1):
        poly.append([4 * i + 3, 2])
        poly.append([4 * i + 2, 10])
        poly.append([4 * i + 1, 2])
    return poly

for k in [3, 5, 8]:
    g = grebenka(k)
    treug = otrezat_ushi(g)
    otvet = ohrana(len(g), treug)
    print(len(g), len(g) // 3, otvet[0], len(otvet[1]), otvet[2])

11 3 [3, 4, 4] 3 True
17 5 [5, 6, 6] 5 True
26 8 [8, 9, 9] 8 True

Охранников ровно ⌊n/3⌋ - столько же, сколько зубцов. Раскраска нашла лучшую расстановку: меньше нельзя, потому что кончики зубцов попарно не видят общей точки. Так гребёнка доказывает, что граница теоремы точная.

Граница применимости: раскраска даёт гарантию ⌊n/3⌋, но не оптимум для конкретного зала. Для звёздного (есть точка, видящая его целиком) или выпуклого многоугольника хватает одного охранника, а раскраска может дать треть вершин. Наименьшее число охранников - задача NP-трудная (Ли и Лин, 1986), а вопрос «хватит ли k», если охранники стоят где угодно, - ∃ℝ-полный (Абрахамсен, Адамашек, Мильцов, 2018): оптимальные координаты охранников бывают иррациональными.

Что ломается без этого

Охранники в вершинах вмятин «на глаз». Кажется, что вмятины - самые обзорные места, но гребёнка показывает: смотреть надо на зоны, видимые из одного места, а не на углы.

Обещание оптимума. Раскраска даёт верхнюю границу. Отчёт «нужно 10 камер» верен как гарантия, а не как минимум - иногда хватит трёх.

Залы с колоннами. Дыры в многоугольнике меняют границу: в зале с h дырами охранникам, которые могут стоять где угодно, нужно до ⌊(n + h)/3⌋ мест (n - все вершины, вместе с вершинами колонн), и раскраска одной триангуляции уже не работает напрямую.

Зачем это в работе

Расстановка камер и датчиков, покрытие зоны радиосигналом в помещении, где стены заслоняют обзор, освещение. В ортогональных залах (стены идут в двух направлениях, углы 90° и 270°) граница лучше - ⌊n/4⌋ охранников (Кан, Клэйв, Клейтман, 1983). Сама раскраска в три цвета - частный случай раскраски плоских графов, а дерево треугольников - тот же двойственный граф, что связывал Делоне и Вороного.

Теперь сам

1. Зал из 20 вершин. Сколько охранников хватит наверняка?
2. Выпуклый шестиугольник: что даст раскраска и сколько охранников нужно на самом деле?
3. Почему раскраска не может застрять - когда третью вершину треугольника требуется покрасить в цвет, который уже есть у его другой вершины?