Chan's algorithm [SoCG16]
encode data as a polynomial
A(x) = (sum f(x_i)^p)^(1/p)
approx f. = n^(1/p)
C(x) = (sum i f(x_i)^p)^(1/p)
p = 1/e log n
C(x)/A(x)
insert / delete is just addition subtraction of a value
use different buckets to avoid issues with points that are too close
Chan's algorithm [SoCG16] encode data as a polynomial A(x) = (sum f(x_i)^p)^(1/p) approx f. = n^(1/p) C(x) = (sum i f(x_i)^p)^(1/p) p = 1/e log n C(x)/A(x) insert / delete is just addition subtraction of a value use different buckets to avoid issues with points that are too close