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

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

Всем привет!

Как решать следующую задачу? Даны N точек на плоскости (N <= 1000), найти минимальную площадь прямоугольника, покрывающего все эти точки. Стороны прямоугольника не обязательно должны быть параллельны осям координат. Я читал, что это можно сделать используя выпуклую оболочку, но не очень понял как.

Помогите пожалуйста, надеюсь в нынетекущих контестах таких задач нет.

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

»
12 лет назад, скрыть # |
 
Проголосовать: нравится +10 Проголосовать: не нравится

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

При указанных ограничениях это дает несложное решение за N^2 — O(N) кандидатов и проверка каждого наивным перебором за О(N).

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

    А быстрее можно? :)

    И как доказать факт про выпуклую?

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

      Можно и быстрее; для заданного выпуклого многоугольника покрывающий прямоугольник минимальной площади можно найти за линейное время. Аналогично поиску диаметра этого многоугольника с помощью rotating calipers, только теперь нам нужно поддерживать две взаимно перпендикулярные пары rotating calipers вместо одной. А дальше аналогично — рассматриваем критичные углы для каждой из касательных, выбираем минимальных из четырех, поворачиваем...

      По поводу доказательства — никогда не интересовался доказательствами, если честно:) Подозреваю, что его можно найти в любой фундаментальной книге по геометрии, вроде Препараты/Шеймоса) Или даже доказать самостоятельно, если немного подумать)

    • »
      »
      »
      12 лет назад, скрыть # ^ |
      ← Rev. 3  
      Проголосовать: нравится -8 Проголосовать: не нравится

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

      В этом легко убедиться, если предположить, что на каждой стороне по одной точке и покрутить прямоугольник. Тогда площадь прямоугольника будет меняться, как произведение двух каких-то синусов (на константу), а произведение двух каких-то синусов — это, в свою очередь, сумма каких-то синусов/косинусов. Косинусы и синусы — выпуклые функции (в определённых рамках, конечно), значит, их сумма тоже выпукла, а значит, минимум достигается на границе интервала, то есть, когда они из сторон прямоугольника упёрлась в ещё одну вершину выпуклой оболочки.

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

        Из первого не следует второе? Оо

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

        два из его углов совпадают с двумя противоположными вершинами выпуклой оболочки — при этом все равно какая-то из сторон оболочки будет лежать на одной из сторон прямоугольника.

        Если нет — значит, можно еще "покрутить" и уменьшать площадь (согласно рассуждениям, которые ты сам написал в следующем абзаце) до тех пор, пока не упремся в еще одну вершину, а из выпуклости оболочки следует, что мы при этом полностью накроем какую-то сторону этой оболочки.

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

          Если два противоположных угла попали в вершины, то мы вылезем за рамки, в которых функции выпуклые.

          Кстати., даже если только один угол прямоугольника попал в вершину выпуклой оболочки, то всё равно можем вылезти. Например, если рассмотреть треугольник со сторонами 1000, 1000, 1.

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

        "В этом легко убедиться, если предположить, что на каждой стороне по одной точке и покрутить прямоугольник. " — Что понимается под кручением прямоугольника? Судя по всему, это не поворот, ведь предполагается, что его площадь будет изменяться.

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

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

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

            Хорошо, тогда что понимается как "произведение 2 синусов"?

            • »
              »
              »
              »
              »
              »
              »
              12 лет назад, скрыть # ^ |
              ← Rev. 4  
              Проголосовать: нравится 0 Проголосовать: не нравится

              если рассмотреть отрезок (пусть его длина l) между двумя противоположными вершинами, в которые упираются стороны, то ширина полосы, в которую он влезает равна l·sin(α), где α — угол наклона между прямыми и этим отрезком. Так же и с другим аналогичным отрезком. Ну а площадь прямоугольника — произведение двух этих ширин. При этом угол наклона к прямым у двух отрезков отличается на некую константу.

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

                Ага, теперь понятно. Только вот там дальше не все так просто. "Косинусы и синусы — выпуклые функции (в определённых рамках, конечно), значит, их сумма тоже выпукла, а значит, минимум достигается на границе интервала," — не факт, что рамки, в которых сумма синусов и косинусов выпукла, содержат в себе границы, в которых можно менять угол α, и нет гарантии, что минимум действительно достигается на экстремальном значении α

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  12 лет назад, скрыть # ^ |
                  ← Rev. 4  
                  Проголосовать: нравится 0 Проголосовать: не нравится

                  Если угол между этими отрезками составляет , α, то (опустив константу) получаем, что . cos(x) — константа, α меняется в промежутке [L, R], где 0 ≤ L ≤ R ≤ π. При этом . Таким образом, функция  - cos рассматривается только на промежутке . Чтобы функция была на этом отрезке выпукла, надо немного получше ограничить α...

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

                  То-то и оно(