Изменения

Перейти к: навигация, поиск

Convex hull trick

71 байт добавлено, 21:14, 17 января 2017
Для чего нужна нижняя ошибающая множества прямых
[[Файл:picture3convexhull.png]]
Действительно, План доказательства : пусть новая прямая пересекает последнюю прямую множества позже, чем предпоследнюю (рис.2 - красная прямая новая, фиолетовая - предпоследняя, желтая - последняя), то тогда найдется такой отрезок <math>[x1;x2]</math>, что последняя(желтая) прямая при этих <tex>x-ах \in [x1;x2]</tex> лежит ниже всех остальных и ее следует оставить в множестве.Теперь пусть А если новая прямая пересекает последнюю прямую множества раньше, чем предпоследнюю (рис.1), последняя прямая при любых x лежит выше какой-то другой прямой множества и значит ее можно нужно удалить, чтдБолее формально. Пусть <math>xL <= </math>
==Детали реализации:==
Анонимный участник

Навигация