About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Algorithmica
Paper
Algorithms for projecting points to give the most uniform distribution with applications to hashing
Abstract
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 θ 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 On2+bn) 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 On2+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 < √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. © 1993 Springer-Verlag New York Inc.