Выдержка из книги
Лупанов О.Б.
Кибернетический сборник Выпуск20
Алгоритм проверяет, не является ли искомое пересечение пустым, и если нет, полностью строит его. Подход основан на том, что если известна какая-нибудь точка р искомого пересечения, само пересечение можно получить, опираясь на соображения геометрической двойственности. Конкретнее, оба исходных многогранника преобразуются в многогранники, геометрически двойственные им относительно точки р, а выпуклая оболочка объединения последних, которая может быть найдена за время O ( rtlogAi), двойственна многограннику, являющемуся пересечением исходных ( разд. Когда такой точки р в нашем распоряжении не имеется, мы можем с помощью известной техники за время О ( п ogti) проверить, является ли искомое пересечение непустым, и если так, найти одну из его точек ( разд. Описанный алгоритм использует представление многогранников посредством весьма удобной структуры, так называемого реберного списка с двойными связями. Последний может быть получен из более привычного представления ( вырабатываемого алгоритмом построения выпуклой оболочки) за время, линейное относительно числа вершин ( разд.
