Пересечение полуплоскостей, связь с выпуклыми оболочками — различия между версиями

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

Версия 15:14, 21 февраля 2014

типа это одно и то же

Задача: есть конечное множество полуплоскотей, найти фигуру их пересечения или сообщить что оно пусто.

Для начала заметим, что если пересечение не пусто, то оно выпукло. (Доказательство — Пересечение выпуклых фигур выпукло, а полуплоскоть выпукла)

Рассмотри отображение [math] D [/math] между точками и прямыми:

[math] D(P(k, b)) = (Y = kX - b) [/math]

[math] D(Y = kX + b) = P(k, -b) [/math]

[math] D(D(P)) = P [/math]

[math] L = {l_1, l_2, ... , l_n} [/math] Замечания:

  • Точка [math] p [/math] лежит на прямой [math] p [/math]

Источники

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Пересечение_полуплоскостей,_связь_с_выпуклыми_оболочками&oldid=36141»