ALGORITHMS FOR PROJECTING POINTS TO GIVE THE MOST UNIFORM-DISTRIBUTION WITH APPLICATIONS TO HASHING

This paper presents several algorithms for projecting points so as to give the most uniform distribution. Given n points in the plane and an integer b, the problem is to find an optimal angle theta of b equally spaced parallel lines such that points are distributed most uniformly over buckets (regions bounded by two consecutive lines). An algorithm is known only in the tight case in which the two extreme lines are the supporting lines of the point set. The algorithm requires O(bn2 log n) time and O(n2 + b) space to find an optimal solution. In this paper we improve the algorithm both in time and space, based on duality transformation. Two linear-space algorithms are presented. One runs in O(n2 + K log n + bn) time, where K is the number of intersections in the transformed plane. K is shown to be O(n2 + bn) based on a new counting scheme. The other algorithm is advantageous if b < square-root n. It performs a simplex range search in each slab to enumerate all the lines that intersect bucket lines, and runs in O(b0.610n1.695 + K log n) time. It is also shown that the problem can be solved in polynomial time even in the relaxed case. Its one-dimensional analogue is especially related to the design of an optimal hash function for a static set of keys.