Любителям сложных структур данных.
Запросы на плоскости: add(line), delete(line), get_max(x).
Можно относительно просто за O(sqrtn), я умел только за O(log^2n). Оказывается, бывает сильно лучше, O(logn) в online: http://cstheory.stackexchange.com/questions/10894/dynamic-upper-envelope-of-lines-in-the-plane
Дочитавшим до конца привет от товарищей Chan, Brodal, Jacob, Kaplan, Tarjan, Demaine, Pătraşcu ;)
Спасибо [id169356|Мише] за всплывшую тему.
Запросы на плоскости: add(line), delete(line), get_max(x).
Можно относительно просто за O(sqrtn), я умел только за O(log^2n). Оказывается, бывает сильно лучше, O(logn) в online: http://cstheory.stackexchange.com/questions/10894/dynamic-upper-envelope-of-lines-in-the-plane
Дочитавшим до конца привет от товарищей Chan, Brodal, Jacob, Kaplan, Tarjan, Demaine, Pătraşcu ;)
Спасибо [id169356|Мише] за всплывшую тему.
Любителям сложных структур данных.
Запросы на плоскости: add(line), delete(line), get_max(x).
Можно относительно просто за O(sqrtn), я умел только за O(log^2n). Оказывается, бывает сильно лучше, O(logn) в online: http://cstheory.stackexchange.com/questions/10894/dynamic-upper-envelope-of-lines-in-the-plane
Дочитавшим до конца привет от товарищей Chan, Brodal, Jacob, Kaplan, Tarjan, Demaine, Pătraşcu ;)
Спасибо [id169356|Мише] за всплывшую тему.
Запросы на плоскости: add(line), delete(line), get_max(x).
Можно относительно просто за O(sqrtn), я умел только за O(log^2n). Оказывается, бывает сильно лучше, O(logn) в online: http://cstheory.stackexchange.com/questions/10894/dynamic-upper-envelope-of-lines-in-the-plane
Дочитавшим до конца привет от товарищей Chan, Brodal, Jacob, Kaplan, Tarjan, Demaine, Pătraşcu ;)
Спасибо [id169356|Мише] за всплывшую тему.
У записи 2 лайков,
0 репостов.
0 репостов.
Эту запись оставил(а) на своей стене Sergey Kopeliovich
