Что происходит в алгоритме Киркпатрика – Зайделя, если медиана - это точно точка с наибольшей координатой Y?

Question

Я пытался понять алгоритм Киркпатрика – Зайделя, который является алгоритмом для вычисления выпуклой оболочки набора точек на плоскости со сложностью O (nlogh) - где n - количество входных точек, а h - число очки в корпусе. Материал, который я использовал, довольно прост и описателен. Но у меня есть сомнения по поводу работы этого алгоритма в особом случае.

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

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

Проблемное изображение здесь:

Answer 1

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

Если несколько точек делят максимальное y координаты, то может быть несколько возможных вариантов верхнего моста; самая длинная из альтернатив, которая содержит все остальные, является наиболее эффективным выбором (но любая из них будет работать).