222
правки
Изменения
Нет описания правки
Для начала заметим, что если пересечение не пусто, то оно выпукло. (Доказательство {{---}} Пересечение выпуклых фигур выпукло, а полуплоскоть выпукла)
Рассмотри отображение <tex> D </tex> между точками и прямыми, такое что:
<tex> D(P(k, b)) = (Y = kX - b) </tex>
<tex> D(Y = kX + b) = P(k, -b) </tex>
Обозначим <tex> D(D(P)) L = P {l_1, l_2, ... , l_n} </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(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>
*
== Источники ==
* 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
