Блог пользователя Barricadenick

Автор Barricadenick, 11 лет назад, По-русски

Даны три выпуклых многоугольника. Необходимо проверить, существуют ли точки, лежащие одновременно внутри всех трех данных выпуклых многоугольников. Как можно решить эту задачу за линию? Для двух выпуклых многоугольников — понятно(сумма Минковского), но как для трех?

  • Проголосовать: нравится
  • +6
  • Проголосовать: не нравится

»
11 лет назад, # |
  Проголосовать: нравится -33 Проголосовать: не нравится

Сумма Минковского и метод включения-икслючения.

»
11 лет назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

Можно представить каждый многоугольник как набор полуплоскостей, дающих его в пересечении. Тогда задача сводится к тому, чтобы проверить, что пересечение набора полуплоскостей непусто. Это можно делать в среднем за O(n), если пошаффлить полуплоскости и добавлять их по одной, поддерживая самую верхнюю точку пересечения.

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Легко придумать пример, в котором всегда будет O(n^2). Что-то похожее на звезду давида для трех многоугольников.

    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Чего будет O(n^2)? Каждый многоугольник добавляет линейное количество плоскостей, а алгоритм в среднем за линию от количества полуплоскостей работает.

      • »
        »
        »
        »
        11 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Линия для добавления плоскостей, а для добавления полуплоскости — еще линия от количества вершин в "общем" множестве. Или я неправильно понял?

        • »
          »
          »
          »
          »
          11 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          мы поддерживаем только самую верхнюю точку, а не находим все точки пересечения.

          • »
            »
            »
            »
            »
            »
            11 лет назад, # ^ |
            Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

            Не совсем понятно, каким образом поддерживать самую верхнюю вершину. Вы могли бы это пояснить?

            • »
              »
              »
              »
              »
              »
              »
              11 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +20 Проголосовать: не нравится

    На самом деле, в задаче автора поста мы имеем только 3 многоугольника = 3 отсортированных множества полуплоскостей. Объединять отсортированные множества мы умеем за O(N * log K), где N — суммарный размер, а K — количество множеств, но т.к. в этой задаче K — константа, имеем асимптотику O(N) даже в худшем случае.

    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      Я правильно понимаю, что под словом "объединять" вы имеете ввиду находить пересечение? И если это так, то где можно почитать о способе за O(N * log K) об этом?

      • »
        »
        »
        »
        11 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится +16 Проголосовать: не нравится

        Есть такой человек, зовут его Per Austrin, он публикует разборы финалов ACM ICPC. В начале каждого разбора он приводит дисклеймер, вот его важная часть:

        Also, note that these sketches are just that—sketches. They are not intended to give a complete solution, but rather to outline some approach that can be used to solve the problem. If some of the terminology or algorithms mentioned below are not familiar to you, your favorite search engine should be able to help.

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

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

        Как объединить k отсортированных множеств? Тупой вариант — завести приоритетную очередь, которая будет содержать наименьшие не добавленные в ответ элементы из каждого множества. Более умный вариант (будет работать явно быстрее в случае небольшого k) — на каждом шаге объединять два наименьших множества за линию, пока у нас не останется одно множество (если нужно доказательство — смотрите доказательство алгоритма Хаффмана).