Алгоритм - построение - выпуклая оболочка
Cтраница 2
Последнее расширение заключается в обобщении диаграммы или триангуляции на пространства более высокой размерности. Используя связь между диаграммой Вороного в of - мерном пространстве и выпуклой оболочкой в ( d 1) - мерном пространстве [61] и алгоритм построения выпуклой оболочки, данный Сейделом в работе [310], можно получить эффективное решение задачи построения диаграммы Вороного в пространствах высших размерностей. Задача построения минимального остовного дерева в пространствах высших размерностей также рассматривалась в ряде работ ( см. [33, 98, 158, 192, 267, 351]), но остается отдельным предметом исследований. [16]
Последнее расширение заключается в обобщении диаграммы или триангуляции на пространства более высокой размерности. Используя связь между диаграммой Вороного в d - мерном пространстве и выпуклой оболочкой в ( d - f - 1) - мерном пространстве [61] и алгоритм построения выпуклой оболочки, данный Сейделом в работе [310], можно получить эффективное решение задачи построения диаграммы Вороного в пространствах высших размерностей. Задача построения минимального остовного дерева в пространствах высших размерностей также рассматривалась в ряде работ ( см. [33, 98, 158, 192, 267, 351]), но остается отдельным предметом исследований. [17]
Второй из рассматриваемых алгоритмов начинает работу с построения выпуклой оболочки множества точек Р плоскости. Под выпуклой оболочкой понимается выпуклый многоугольник, каждая из вершин которого совпадает с одной из точек множества Р, а все остальные точки лежат на сторонах или внутри многоугольника. Алгоритмы построения выпуклой оболочки конечного множества точек на плоскости рассмотрены далее в этой главе. Если внутренние точки отсутствуют, то оптимальное решение задачи коммивояжера определяется через обход вершин оболочки в одном из двух направлений, начиная с любой вершины. В том случае, когда оболочка содержит s вершин ( ii 2, , s) j T J полагая Xs ( i 2, 5 s), реализуем первый алгоритм. [18]
Если в действительности число вершин выпуклой оболочки равно h, то время выполнения алгоритма Джарвиса будет 0 ( hN), и он очень эффективен, когда заранее известно, что значение h мало. Например, если оболочка заданного множества является многоугольником с произвольным постоянным числом сторон, то ее можно найти за линейное относительно числа точек время. Этот факт чрезвычайно важен в свете анализа сложности алгоритмов построения выпуклой оболочки в среднем, который будет представлен в следующей главе. [20]
Прежде чем закончить этот раздел, отметим, что метод Грэхема явным образом использует сортировку. Аналогично тому, как исследование сортировки показало, что не существует одного алгоритма, лучшего во всех случаях, мы увидим, что то же самое справедливо и для задачи построения выпуклой оболочки. Давайте продолжим исследование комбинаторной геометрии в поисках идей, способных привести к иным алгоритмам построения выпуклой оболочки. [21]
Предварительная сортировка элементов множества S по координате xi требует O ( N ogN) операций. Отметим, что благодаря такой сортировке и тому, как выполняется шаг 2 алгоритма, множества CH ( Si) и CH ( S2) представляют два непересекающихся трехмерных политопа. Отметим, что для простоты мы считаем N четным, но это не влияет на общность результата. Таким образом, если мы сумеем показать, что M ( N) равно O ( N), то получим для Т ( N) оценку O ( NlogN) и, учитывая затраты на предварительную сортировку, получим оценку О ( N log N) для сложности всего алгоритма построения выпуклой оболочки. [22]
Описанный здесь коротко метод чрезвычайно прост в реализации. Чтобы определить полосу, в которую попадает некоторая точка р, необходимо вычесть из х ( р) минимальное значение - координаты ( хт [ П) и разделить получившуюся разность на ( 1 / &) - ю часть разности значений л - координат экстремальных точек. Взяв целую часть от получившегося результата, получим номер полосы, содержащей точку. Можно параллельно искать минимум и максимум в каждой полосе, так как для каждой точки проверяется, выходит ли она за пределы текущих значений максимума и минимума, и, если это имеет место, производится необходимое изменение в массиве. И наконец, можно выбрать удобный в данном случае алгоритм построения выпуклой оболочки: очевидно, что наиболее подходящим является вариант алгоритма Грэхема, предложенный Эндрью ( см. разд. Заметим, что точки множества S почти упорядочены по значению А - координаты. [23]
Выпуклый политоп задается описанием его границы, состоящей из граней. Если политоп Р имеет размерность d, то его ( d - 1) - грани называются гипергранями, ( d - 2) - грани - подгранями, 1-грани - ребрами, а 0-грани - вершинами. Ясно, что ребра и вершины сохраняют свое привычное значение в пространствах любой размерности. Для 3-политопа гиперграни являются плоскими многоугольниками, а подграни и ребра совпадают. Как мы уже видели ранее, эти четыре класса граней играют важную роль в алгоритмах построения выпуклой оболочки. Для единообразия может оказаться полезным называть cf - политоп d - гранью, а пустое множество в такой терминологии превращается в ( - 1) - грань. Однако не все подмножества S определяют грани. [24]
Алгоритм проверяет, не является ли искомое пересечение пустым, и если нет, полностью строит его. Подход основан на том, что если известна какая-нибудь точка р искомого пересечения, само пересечение можно получить, опираясь на соображения геометрической двойственности. Конкретнее, оба исходных многогранника преобразуются в многогранники, геометрически двойственные им относительно точки р, а выпуклая оболочка объединения последних, которая может быть найдена за время O ( rtlogAi), двойственна многограннику, являющемуся пересечением исходных ( разд. Когда такой точки р в нашем распоряжении не имеется, мы можем с помощью известной техники за время О ( п ogti) проверить, является ли искомое пересечение непустым, и если так, найти одну из его точек ( разд. Описанный алгоритм использует представление многогранников посредством весьма удобной структуры, так называемого реберного списка с двойными связями. Последний может быть получен из более привычного представления ( вырабатываемого алгоритмом построения выпуклой оболочки) за время, линейное относительно числа вершин ( разд. [25]
Страницы: 1 2