Cтраница 2
Если выпуклая оболочка объединения любых himS 1 множеств этого семейства представляет собой полуограниченное множество, то выпуклая оболочка объединения всех множеств семейства М также является Е - полуограниченным множеством. [16]
Нетрудно убедиться в том, что выпуклая оболочка объединения многогранников A ( D) и B ( D) представляет собой многогранник, двойственный пересечению многогранников А и В. [17]
Если выпуклая оболочка объединения любых himS 1 множеств этого семейства представляет собой полуограниченное множество, то выпуклая оболочка объединения всех множеств семейства М также является Е - полуограниченным множеством. [18]
Алгоритм проверяет, не является ли искомое пересечение пустым, и если нет, полностью строит его. Подход основан на том, что если известна какая-нибудь точка р искомого пересечения, само пересечение можно получить, опираясь на соображения геометрической двойственности. Конкретнее, оба исходных многогранника преобразуются в многогранники, геометрически двойственные им относительно точки р, а выпуклая оболочка объединения последних, которая может быть найдена за время O ( rtlogAi), двойственна многограннику, являющемуся пересечением исходных ( разд. Когда такой точки р в нашем распоряжении не имеется, мы можем с помощью известной техники за время О ( п ogti) проверить, является ли искомое пересечение непустым, и если так, найти одну из его точек ( разд. Описанный алгоритм использует представление многогранников посредством весьма удобной структуры, так называемого реберного списка с двойными связями. Последний может быть получен из более привычного представления ( вырабатываемого алгоритмом построения выпуклой оболочки) за время, линейное относительно числа вершин ( разд. [19]
При построении множества прогноза количество узлов на каждом шаге А может вырасти в три раза. Однако, поскольку все узлы расположены в интервале [ 0 2л: ], то какие-то из них оказываются близкими, что позволяет объединять их для ограничения общего количества сечений. Вместо каждой группы сечений с близкими значениями по ф, вводится одно сечение со средним значением ф, представляющее собой выпуклую оболочку объединения. [20]