## 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(bn^{2} log n) time and On^{2}+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 On^{2}+K log n+bn) time, where K is the number of intersections in the transformed plane. K is shown to be O(@#@ n^{2}+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(b^{0.610}n^{1.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 language | English |
---|---|

Pages (from-to) | 572-590 |

Number of pages | 19 |

Journal | Algorithmica |

Volume | 9 |

Issue number | 6 |

DOIs | |

Publication status | Published - 1993 Jun 1 |

## Keywords

- 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