Algorithms for projecting points to give the most uniform distribution with applications to hashing

Tetsuo Asano, Takeshi Tokuyama

Research output: Contribution to journalArticlepeer-review

7 Citations (Scopus)


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.

Original languageEnglish
Pages (from-to)572-590
Number of pages19
Issue number6
Publication statusPublished - 1993 Jun 1


  • Computational geometry
  • Duality transform
  • Hashing
  • Intersection-reporting algorithm
  • Linear-space algorithm
  • Plane sweep
  • Projection
  • Simplex range search
  • Topological walk

ASJC Scopus subject areas

  • Computer Science(all)
  • Computer Science Applications
  • Applied Mathematics


Dive into the research topics of 'Algorithms for projecting points to give the most uniform distribution with applications to hashing'. Together they form a unique fingerprint.

Cite this