Выбор точек для нахождения моста в выпуклой оболочке

Question

При нахождении выпуклой оболочки для набора точек с использованием алгоритма «разделяй и властвуй» нам нужно найти верхний и нижний мост.Алгоритм поиска этих мостов, например, верхнего моста:

1. Запуск с любого моста.Например, мост гарантирован, если вы соедините крайнюю правую вершину слева с самой левой вершиной справа.

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

3. Если в (2) нет прогресса (невозможно поднять ни одну из сторон), то остановите повторение (2)).

Мой вопрос: обязательно ли выбирать только крайнюю правую вершину слева и самую левую вершину справа?Можем ли мы выбрать:

a.крайняя левая вершина слева, крайняя левая вершина справа?

b.крайняя правая вершина слева или правая вершина справа?

c.крайняя левая вершина слева до самой правой вершины справа?

Answer 1

На самом деле, оригинальный алгоритм от Preparata использует варианты a и b.Единственное, что вам нужно гарантировать, это то, что наклоны (в любой системе координат) отрезков между двумя крайними точками на обеих частичных оболочках монотонны, и вы идете в правильном направлении.Если вы можете это гарантировать, вы можете выбрать любую комбинацию экстремальных точек.