222
правки
Изменения
Нет описания правки
<tex> D(Y = kX + b) = P(k, -b) </tex>
[[Файл:dual.png|400px|thumb|right|Совпадение верхнего CH и нижней огибающей]]
Замечания:
* <tex> D(D(P)) = P </tex>
* Точка <tex> p </tex> лежит под/на /над прямой <tex> l_i l </tex> тогда и только тогда, когда <tex> D(l_il) </tex> лежит под/на /над прямой <tex> D(p) </tex>;* Прямая Точка <tex> l_i </tex> лежит на границе пересечения тогда и только тогда, когда <tex> D(l_i) p \in P = \cup p_i </tex> {{---}} экстремальная точка принадлежит <tex> DUH(LP) </tex>;* Точка <tex> l_i </tex> вершина пересечения прямых <tex> l_i </tex> и <tex> l_j </tex> тогда и только тогда, когда <tex> \exists l(D(l_i), D(l_j)) \forall i : p_i </tex> {{---}}опорное ребро конвекс халла лежит под <tex> CH(D(L)) l </tex>;* Точка <tex> l_i </tex> {{---}} не экстемальная точка <tex> D(L) </tex> тогда и только тогда, когда удаление <tex> h_i l </tex> не повлияет на пересечениевертикальна.
Таким образом получаем:
* Взаимно однозначное соответствие между вершинами <tex> CH(D(L)) </tex> и границами пересечения <tex> \cap_{i=1}^{n}(l_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 11 page 253-254
* http://wwwisg.cs.uni-magdeburg.de/ag/lehre/SS2012/GAG/slides/V12.pdf
[[Категория: Вычислительная геометрия]]
