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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
Строка 13: Строка 13:
 
Обозначим <tex> L = {l_1, l_2, ... , l_n} </tex> {{---}} множество прямых.
 
Обозначим <tex> L = {l_1, l_2, ... , l_n} </tex> {{---}} множество прямых.
  
 +
[[Файл:duality.png|400px|thumb|right|Пример отображения]]
 
Замечания:
 
Замечания:
 
* <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_i </tex> тогда и только тогда, когда <tex> D(l_i) </tex> лежит на прямой <tex> D(p) </tex>;
* Точка <tex> p </tex> лежит на прямой-границе пересечения <tex> l_i </tex> тогда и только тогда, когда <tex> D(l_i) </tex> {{---}} экстремальная точка <tex> D(L) </tex>.
+
* Прямая <tex> l_i </tex> лежит на границе пересечения тогда и только тогда, когда <tex> D(l_i) </tex> {{---}} экстремальная точка <tex> D(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> 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> не повлияет на пересечение.
 +
 
 
== Источники ==
 
== Источники ==
 
* 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 15 page 253-254

Версия 17:20, 21 февраля 2014

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

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

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

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

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

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

Обозначим [math] L = {l_1, l_2, ... , l_n} [/math] — множество прямых.

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

Замечания:

  • [math] D(D(P)) = P [/math]
  • Точка [math] p [/math] лежит на прямой [math] l_i [/math] тогда и только тогда, когда [math] D(l_i) [/math] лежит на прямой [math] D(p) [/math];
  • Прямая [math] l_i [/math] лежит на границе пересечения тогда и только тогда, когда [math] D(l_i) [/math] — экстремальная точка [math] D(L) [/math];
  • Точка [math] l_i [/math] вершина пересечения прямых [math] l_i [/math] и [math] l_j [/math] тогда и только тогда, когда [math] l(D(l_i), D(l_j)) [/math] —опорное ребро конвекс халла [math] CH(D(L)) [/math];
  • Точка [math] l_i [/math] — не экстемальная точка [math] D(L) [/math] тогда и только тогда, когда удаление [math] h_i [/math] не повлияет на пересечение.

Источники