Найти max y координату выпуклого многоугольника

Question

У меня есть массив V[1,2,....,n], где каждый элемент массива представляет вершину выпуклого многоугольника в виде координатной пары (x, y).

Дано, что V[1] - это вершина с минимальной координатой x, и что вершины V[1,2,....,n] упорядочены против часовой стрелки, как на рисунке. Также дано, что координаты x вершин различны, как и координаты y вершин.

Теперь я хочу найти вершину с max y значением координаты. Все мы знаем наивный метод O (n), но возможно ли его найти в O (log (n))?

Я использовал информацию о том, что V[1] - это вершина с минимальной координатой x, чтобы найти вершину с максимальной координатой x за время O (log (n)). Но возможно ли это сделать для максимальной координаты y?

Спасибо за помощь!

Answer 1

Пусть V [m] - вершина с координатой max y.

Самый простой случай для рассмотрения - m=1, когда V[2].y < V[1].y > v[n].y. Поскольку исключение этого случая упрощает последующие рассуждения, мы будем предполагать, что начальная проверка для этого случая выполнена.

Рассмотрим ребро E [i] с началом V [i], где 1<i<=n. Учитывая ограничение, что все координаты x и y различны, E [i] должен лежать в одном из 4 плоских квадрантов:

Учитывая, что мы исключили случай, когда m=i=1, для E [i], лежащего в квадрантах I, II или IV, это должен быть случай, когда m>i. Если E [i] лежит в квадранте III, то либо m=i, что верно, если V[i].y > V[i-1].y, либо m<i.

Мы можем использовать эти рассуждения как основу для бинарного поиска, где на каждой итерации мы выполняем:

if E[i] lies in Quadrant III
   if V[i].y > V[i-1].y then m=i
   else consider left half
else
   consider right half

Вот некоторый Java-код для иллюстрации:

static Point maxY(Point[] v)
{       
    // check for max at origin
    if(v[1].y < v[0].y && v[v.length-1].y < v[0].y)
    {
        return v[0];
    }

    int left = 0; 
    int right = v.length-1;     
    Point maxY = null;
    while(left <= right)
    {
        int mid = left + (right-left)/2;
        if(v[(mid+1)%v.length].y < v[mid].y && v[(mid+1)%v.length].x < v[mid].x)
        {
            // Quadrant III
            if(v[mid].y > v[mid-1].y) 
            {
                maxY = v[mid];
                break;
            }
            right = mid - 1;
        }
        else 
        {
            left = mid + 1;
        }
    }
    return maxY;
}

И несколько простых тестовых случаев:

public static void main(String[] args)
{
    Point[][] tests = {
            {new Point(0, 10), new Point(10, 0), new Point(9, 5)},
            {new Point(0, 0), new Point(9, 5), new Point(10, 10)},
            {new Point(0, 0), new Point(10, 10), new Point(5, 8)},
            {new Point(0, 5), new Point(9, 0), new Point(10, 10)},
            {new Point(0, 5), new Point(6,0), new Point(10, 6), new Point(5,10)}};

    for(Point[] coords : tests) 
        System.out.println(maxY(coords) + " : " + Arrays.toString(coords));
}

Выход:

(0, 10) : [(0, 10), (10, 0), (9, 5)]
(10, 10) : [(0, 0), (9, 5), (10, 10)]
(10, 10) : [(0, 0), (10, 10), (5, 8)]
(10, 10) : [(0, 5), (9, 0), (10, 10)]
(5, 10) : [(0, 5), (6, 0), (10, 6), (5, 10)]

Answer 2

Поскольку многоугольник является выпуклым, угол вектора между последовательными точками монотонно увеличивается от 270 градусов (вниз. Назовите это -90 градусов) до 0 (справа), 90 (вверх), 180 (слева) и т. Д., при перемещении от одной точки к другой вокруг многоугольника.

Поэтому вы можете выполнить бинарный поиск, чтобы найти наименьший угол, превышающий 180 градусов. Точка, в которой вектор к следующей точке становится> 180 градусов (V [8] в вашем примере), - это точка, в которой многоугольник поворачивает от направления вверх или влево к направлению вниз, и эта точка должна иметь наибольшую координату Y.

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

Answer 3

Длинная версия

Бинарный поиск отмечается как решение в некоторых местах, но он будет работать только в некоторых случаях.

Распределение вершин может варьироваться различными способами. У вас может быть много кластеризованных вблизи одной точки, а одна - в другом месте, у вас могут быть вершины, которые образуют параболическую форму (на примере вашей диаграммы, исключите вершины 7, 8 и 9), вы можете иметь логарифмическое распределение (например, только вершины 1, 2, 3 и 4) или действительно любое другое количество возможностей. Во всех этих разных случаях у вас будет разное количество и смещение локальных максимумов и минимумов.

Скорее всего, вам понадобится комбинация подходов для оценки распределения, а затем применение стратегии, соответствующей типу распределения.

Давайте попробуем описать такую ​​стратегию:

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

Наблюдайте за поведением V[n]. Если V[n] имеет y-координату V[n].y меньше, чем у V[1], или V[n].y < V[1].y, вы можете заключить, что все другие вершины V[2, n-1] также должны иметь y-координаты ниже, чем V[1] (подумайте, почему это должно быть дело). Таким образом, V[1] имеет наибольшую координату Y.

Теперь, остальная часть этого анализа потребует, чтобы мы изменили нашу концептуальную модель многоугольника, чтобы упростить его представление и, следовательно, проблему, которую мы хотим решить. Вместо построения точек (V[i].x, V[i].y), чтобы получить форму многоугольника, вместо этого нанесите (i, V[i].y), чтобы представить воображаемую непрерывную функцию f(i) = V[i].y. Решение нашей проблемы теперь является решением нахождения глобального максимума функции f(i) = V[i].y.

Имея это в виду, для всех других случаев, когда V[n].y > V[1].y, мы должны выполнить бинарный поиск, но у нас есть два возможных сценария для рассмотрения:

1. V[2] имеет координату y меньше V[1].
2. V[2] имеет координату y больше, чем V[1].

Это важно, потому что случай 1 говорит нам, что V[1] это , а не локальные минимумы, а случай 2 говорит нам, что V[1] это локальные минимумы (еще раз рассмотрим почему это должно быть так).

Случай 2 - хороший, простой случай, поскольку V[1] является локальным минимумом. Это означает, что может быть только один дополнительный локальный минимум в V[n], или нет других локальных минимумов вообще. Таким образом, мы можем выполнить бинарный или бинарный поиск, чтобы постепенно сходиться к единственным локальным максимумам на кривой.

Ваша диаграмма - пример варианта 1, который сложнее. V[1] это не локальные минимумы, поэтому это локальные максимумы. Что еще более важно, у вас есть два возможных локальных максимума, которые расположены в V[1] и V[n-k], где n-k > 1. Для наглядности, если вы нанесете точки для функции f(i) = V[i].y, вы увидите либо параболическую, либо синусоидальную форму. Таким образом, второй локальный максимум на V[n-k] будет либо самым правым концом параболы, либо пиком синусоидальной кривой.

(Примечание. Этот параграф является необязательным шагом оптимизации.) Давайте рассмотрим, как определить, с каким типом локальных максимумов мы имеем дело: если V[n] имеет y-координату больше V[n-1], тогда V[n] должно быть вторым локальным максимумом (опять же, подумайте, почему это должно быть правдой), и фактически мы можем мгновенно определить, что V[n] имеет наибольшую y-координату. В противном случае существует некоторое k такое, что V[n-k] является нашим локальным максимумом, что означает, что нам нужно выполнить поиск.

Теперь это просто оставляет нам вопрос о том, как проводить поиск, чтобы избежать непреднамеренного сближения с V[1] (нам нужно найти локальные максимумы, и, поскольку V[1] - локальные максимумы, мы могли бы случайно сойтись по нему ).

Выполните бинарный поиск со следующими ограничениями:

• Для данного V[i], если V[i].y < V[1].y, то сходятся к V[n].
• Если V[i].y > V[1].y, то сходятся в направлении увеличения y (просто сравните V[i] с V[i-1] и V[i+1]).

Это должно позволить вам безопасно сходиться к крайнему правому локальному максимуму и изолировать значение в течение log(n) времени.

Теперь, когда мы рассмотрели два разных случая для V[1].y < V[n].y, отметим, что этот ограниченный двоичный поиск будет работать в случае 2 так же точно, как и в случае 1. Таким образом, мы можем затем обобщить поиск для обоих случаев 1 и 2, следуя правилам ограниченного двоичного поиска для обоих случаев. Это значительно уменьшает алгоритмическую сложность.

В целом вы должны иметь возможность добиться O(log n) времени для любого общего случая с парой O(1) крайних случаев.

Основная информация

Хитрость, стоящая за этой проблемой, заключается в деконструкции понятия многоугольника, построении точек (i, V[i].y) вместо (V[i].x, V[i].y) и представлении этих точек как непрерывной функции. Тогда решение этой проблемы становится решением проблемы «каков глобальный максимум f(i) = V[i].y?». Из-за свойств выпуклого многоугольника и того, как упорядочены ваши вершины, мы можем установить, что V[1] определенно является локальным максимумом. Имея это в виду, либо V[1] является глобальным максимумом, либо нет, то, что мы можем определить в постоянное время в самом начале. Если это не глобальный максимум, то мы можем выполнить ограниченный двоичный поиск, который не дает нам сойтись на V[1], что позволяет нам определять глобальный максимум в логарифмическом времени. Если мы чувствуем себя слишком сложными, мы также можем определить, является ли V[n] глобальным максимумом в постоянное время, как дополнительный шаг оптимизации.

---

Короткая версия

Когда V[1].y > V[n].y, максимум составляет V[1].y. Ваше решение должно использовать бинарный поиск только в случаях V[1].y < V[n].y. Этот двоичный поиск должен соответствовать следующим ограничениям при произвольном V[i]:

• Базовый случай: если V[1].y > V[i].y, сходятся в направлении V[n].
• Стандартный случай: если V[i].y < V[i+1].y, сходятся в направлении V[n]; иначе, если V[i].y < v[i-1].y, сходятся в направлении V[1]; иначе V[i].y это максимум.

Существует также дополнительная оптимизация, которая может быть выполнена для граничного случая, где V[1].y < V[n].y и V[n].y > V[n-1].y. Эта оптимизация может быть безопасно пропущена и может упростить концептуализацию и реализацию решения.

Псевдокод для соответствующего алгоритма выглядит следующим образом:

Решение с оптимизацией

Если V[1].y > V[n].y, то V[1].y является максимальным.

Если V[1].y < V[n].y и V[n].y > V[n-1].y, то V[n].y является максимальным.

Если V[1].y < V[n].y и V[n].y < V[n-1].y, выполнить ограниченный двоичный поиск.

Эта стратегия имеет два O(1) крайних случая и стандартный O(log n) случай.

Решение без оптимизации

Если V[1].y > V[n].y, то V[1].y является максимальным.

Если V[1].y < V[n].y, выполнить ограниченный двоичный поиск.

Эта стратегия имеет один O(1) крайний случай и стандартный O(log n) случай.

Answer 4

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

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