[[Файл:dual.png|400px|thumb|right|типа это одно и то же]]
Короче говоря, верхний(нижний) конвекс-халл для множества точек, то же самоеЗадача: есть конечное множество полуплоскотей, найти фигуру их пересечения или сообщить что и нижняя(верхняя) огибающая(англ. lower(upper) envelope) для множества прямыхоно пусто.
Если рассмотреть что ребро <tex> PQ </tex> принадлежит верхнему конвекс-халлу это означаетДля начала заметим, что все остальные точки лежат снизу. А если ребро <tex> PQ </tex> принаджлежит нижней огибающейпересечение не пусто, то все остальные прямые лежат сверхуоно выпукло. Короче да(Доказательство {{---}} Пересечение выпуклых фигур выпукло, одно и то же...а полуплоскоть выпукла)
Если в конвекс-халле мы идем слева направо по увеличению икса, то тут то же самое будет, если мы пойдем справа налево по увеличению угла наклона. Полностью считать пересечние можно по отдельности (верхняя + нижняя огибающая), а можно и сразу все, как полный конвекс-халл. Тут бы и закончить конспект, но стоит уточнить, что у пересечения полуплоскостей есть одна небольшая особенность {{---}} оно может быть пусто, тогда как выпуклая оболочка вполне себе всегда определена, и это надо учитывать. И еще. когда мы рассматриваем верхнюю(нижнюю) огибающую, мы рассматриваем все прямые кроме вертикальных. Еще прямые близкие к вертикальным, но имеющие разный наклон (/ и \) are mapped to very different points. Отсюда выходит то, почему конвекс-халл состоит из двух таких разных и одинаковых частей. Короче есть биекция Рассмотри отображение <tex> D </tex> между точками и прямыми.:
<tex> D(P(k, b)) = (Y = kX - b) </tex>
<tex> D(D(P)) = P </tex>
В общем алгоритм такой<tex> L = {l_1, l_2, . Отдельно строим конвех-халл для плоскостей смотрящих вверх и для смотрящих вниз. Получаем две цепочки. Пересекаем их пуская заметающую вертикальную прямую, l_n} </tex>Замечания:* Точка <tex> p </tex> лежит на прямой <tex> p </tex>**
== Источники ==
