Tight Space Bounds for Two-Dimensional Approximate Range Counting

Wei, ZW; Yi, K

Wei, ZW (reprint author), Renmin Univ China, Sch Informat, 59 Zhongguancun Rd, Beijing 100872, Peoples R China.

ACM TRANSACTIONS ON ALGORITHMS, 2018; 14 (2):

Abstract

We study the problem of two-dimensional orthogonal range counting with additive error. Given a set P of n points drawn from an n x n grid and an error......

Full Text Link