js-data-structures

js-data-structures copied to clipboard

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