Изменения

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

Convex hull trick

1 байт добавлено, 20:15, 18 января 2017
Альтернативный подход
[[Файл:picture5convexhull.png]]
Докажем то, что описанный выше алгоритм корректен. Для этого достаточно показать, что если имеются <math>3</math> вектора <math>a, b, c</math>, расположенные как на рис. 5, т.е. точка <math>b</math> не лежит на выпуклой оболочке векторов <tex>0, a, b, c </tex> : <tex> \Leftrightarrow |[a-b, b-c]| < 0 </tex>, то либо <tex>(a, u[i])</tex> оптимальнее, чем <tex>(b, u[i])</tex>, либо <tex>(c, u[i])</tex> оптимальнее, чем <tex>(b, u[i])</tex>.
{{Теорема
|id=th12392.
Анонимный участник

Навигация