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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
Строка 10: Строка 10:
  
 
<tex> D(Y = kX + b) = P(k, -b) </tex>
 
<tex> D(Y = kX + b) = P(k, -b) </tex>
−
 
−
Обозначим <tex> L = \{l_1, l_2, ... , l_n\} </tex> {{---}} множество прямых. Сначала рассмотрим случай, когда пересечение не пусто и содержит точку <tex> O </tex>. Тогда исходные полуплоскости <tex> h_i </tex> {{---}} это прямая <tex> l_i </tex> и полуплоскость, содержащая <tex> O </tex>.
 
  
 
[[Файл:dual.png|400px|thumb|right|Совпадение верхнего CH и нижней огибающей]]
 
[[Файл:dual.png|400px|thumb|right|Совпадение верхнего CH и нижней огибающей]]
 
Замечания:
 
Замечания:
 
* <tex> D(D(P)) = P </tex>
 
* <tex> D(D(P)) = P </tex>
−
* Точка <tex> p </tex> лежит на прямой <tex> l_i </tex> тогда и только тогда, когда <tex> D(l_i) </tex> лежит на прямой <tex> D(p) </tex>;
+
* Точка <tex> p </tex> лежит под/на/над прямой <tex> l </tex> тогда и только тогда, когда <tex> D(l) </tex> лежит под/на/над прямой <tex> D(p) </tex>;
−
* Прямая <tex> l_i </tex> лежит на границе пересечения тогда и только тогда, когда <tex> D(l_i) </tex> {{---}} экстремальная точка <tex> D(L) </tex>;
+
* Точка <tex> p \in P = \cup p_i </tex> принадлежит <tex> UH(P) </tex> тогда и только тогда, когда <tex> \exists l \forall i : p_i </tex> лежит под <tex> l </tex> и <tex> l </tex> не вертикальна.
−
* Точка <tex> l_i </tex> вершина пересечения прямых <tex> l_i </tex> и <tex> l_j </tex> тогда и только тогда, когда <tex> l(D(l_i), D(l_j)) </tex> {{---}}опорное ребро конвекс халла <tex> CH(D(L)) </tex>;
 
−
* Точка <tex> l_i </tex> {{---}} не экстемальная точка <tex> D(L) </tex> тогда и только тогда, когда удаление <tex> h_i </tex> не повлияет на пересечение.
 
−
 
 
 
Таким образом получаем:
 
Таким образом получаем:
 
* Взаимно однозначное соответствие между вершинами <tex> CH(D(L)) </tex> и границами пересечения <tex> \cap_{i=1}^{n}(l_i) </tex>;
 
* Взаимно однозначное соответствие между вершинами <tex> CH(D(L)) </tex> и границами пересечения <tex> \cap_{i=1}^{n}(l_i) </tex>;
Строка 26: Строка 21:
  
 
== Источники ==
 
== Источники ==
−
* Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars (2008), Computational Geometry: Algorithms and Applications (3rd edition), Springer-Verlag, ISBN 978-3-540-77973-5 Chapter 15 page 253-254
+
* Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars (2008), Computational Geometry: Algorithms and Applications (3rd edition), Springer-Verlag, ISBN 978-3-540-77973-5 Chapter 11 page 253-254
 
* http://wwwisg.cs.uni-magdeburg.de/ag/lehre/SS2012/GAG/slides/V12.pdf
 
* http://wwwisg.cs.uni-magdeburg.de/ag/lehre/SS2012/GAG/slides/V12.pdf
  
 
[[Категория: Вычислительная геометрия]]
 
[[Категория: Вычислительная геометрия]]

Версия 22:05, 21 февраля 2014

Пример отображения

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

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

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

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

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

Совпадение верхнего CH и нижней огибающей

Замечания:

  • [math] D(D(P)) = P [/math]
  • Точка [math] p [/math] лежит под/на/над прямой [math] l [/math] тогда и только тогда, когда [math] D(l) [/math] лежит под/на/над прямой [math] D(p) [/math];
  • Точка [math] p \in P = \cup p_i [/math] принадлежит [math] UH(P) [/math] тогда и только тогда, когда [math] \exists l \forall i : p_i [/math] лежит под [math] l [/math] и [math] l [/math] не вертикальна.

Таким образом получаем:

  • Взаимно однозначное соответствие между вершинами [math] CH(D(L)) [/math] и границами пересечения [math] \cap_{i=1}^{n}(l_i) [/math];
  • Порядок точек в [math] CH(D(L)) [/math] совпадает с порядком прямых в пересечении.

Источники

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