Изменения

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

Convex hull trick

13 байт добавлено, 01:20, 18 января 2017
Ключевая идея оптимизации
[[Файл:picture1convexhull.png]]
Выделим множество точек <tex>(x0, y0)</tex> , таких что все они принадлежат одной из прямых и при этом нету ни одной прямой <tex>y’(x)</tex>, такой что <tex>y’(x0) < y0</tex>. Иными словами возьмем «выпуклую (вверх) оболочку» нашего множества прямых (её еще называют нижней ошибающей множества прямых на плоскости). Назовем ее «<tex>y = convex(x)</tex>». Видно, что множество точек <math>(x, convex(x)) </math> представляет собой выпуклую вверх функцию.
==Цель нижней огибающей множества прямых==
Анонимный участник

Навигация