# Perfect 2-D Hashing

### Author: Han de Bruijn Date: 2006 November

This is actually a re-write of an article posted in 'sci.math' as the (would be) thread 'Inverse Perfect Hashing'
Imagine a rectangular region which is placed quite arbitrarily inside a rectangular grid. It is questioned which gridpoints are inside this rectangular region.
A picture says more than a thousand words: ## Forward Hash

### Formulation of the problem

How to obtain a list of all grid points which are inside the rectangle, where each grid point occurs only once in the list. And yes, we want our algorithm to be as fast as possible.

### Solution of the problem

The rectangle is transformed into a rectangle which coincides with a cartesian coordinate system at two of its edges (i.e. the top-left position becomes the origin in graphics coordinates). This is a translation combined with a rotation. Each grid point is transformed into the translated/rotated coordinates, giving (x,y) floating point values, instead of integer values: When rounding the floating point values of the transformed interior points to integer values, memory locations may be obtained, in principle.

Such a method is commonly called hashing.

It can be demonstrated (: make a drawing) that at most two collisions can happen when rounding these (x,y) coordinates: just try to bring two grid points together in one grid cell. You will see that they can only fit in if their mutual distance is smaller than √2, the diagonal of the cell: But two different grid points can oly give rise to the same round off values - giving the midpoint of the grid cell - if they fit into the same grid cell. The big trick is now that all lengths may be multiplied with this factor √2 (preferrably even somewhat larger for safety): It is clear that all collisions have disappeared then: it's impossible to bring two grid points with mutual distance greater than √2 together into one 1x1 grid cell and round them to the same midpoint. With other words: we have a perfect hash (though maybe it doesn't look like it, not yet): But if these values are rounded  . . . Look ! Here we are: Therefore what we need is a table which is √2 times √2 = twice as big as the minimal size which would be needed for storing all grid point values "without gaps". The advantage of the overhead by a factor 2 is that an adress is attached to a grid point immediately, without any need for re-hashing (due to a collision) or searching.

## Inverse Hash

Such a "Perfect Hash" can always be inverted. This is evident, because if there is a one-to-one mapping of a grid point onto an adress then such a mapping can always be inverted to a mapping of an adress onto a grid point.

The procedure is as follows. Traverse all adresses in our twice-too-big table; and apply the inverse of all transformations in reverse order. Inverse rounding in the first place, corresponding to plus or minus 1/2 with both coordinates, resulting in a little square with four vertices. Then dividing all coordinates by √2 instead of a multiply. Rotate over minus the angle, perform a translation backwards. The end-result of this (floating point) procedure is the little square with, yes or no, a grid point in it. Iff the grid point is within that little square, then it can be found by rounding the coordinates of the center of the square. This center corresponds with the end-result by rounding, in the Forward Hash procedure. Rounding the center gives whole-number coordinates, hence a possible grid point. Next check if the candidate grid point is within that little square as well. (This is not necessarily true: approximately half of the grid points will be outside and approximately half of the grid points will be inside the little square.) At last check if the candidate grid point is within the large skew rectangle we started with. In this manner, the Inverse Hashing procedure enables us to find all grid points corresponding to adresses which can be filled with Forward Hashing.

The above has been coded into a computer program. The main program produces the pictures as captured and displayed in this web page. It is accompanied, though, with a separate module (Delphi 'unit') called 'wiskunde' (Dutch for 'mathematics') and the above theory is embodied in this module. The source code, together with a (Microsoft Windows) executable, is packed into a downloadable ZIP file. Unpack in a spearate map and eventually execute.

## CG application

But look what we have obtained now ! Because grid points can be interpreted as pixels - with Computer Graphics applications - Inverse Hashing is actually a recursion-free Flood Fill procedure of arbitrary rectangles in an image. The overhead measured in computation time is at most twice the theoretical minimum, that is: iff each pixel could be found immediately, which in general is not the case.

## Number Theory

Key reference is the following article in the 'sci.math' thread ' 3^m/2^n => r '. The IMHO correct statement is that any area equal to = 1 , in the 2-D grid of numerators and denominators of fractions, contains at least zero and at most four fractions. This means that, for a given r and ε , there must be a search up to numerators or denominators with order of magnitude ( r / ε ) , if r is the (irrational) number to be approximated and ε is the error (tolerance) in the approximation.

## Generalization

In three dimensional space, Perfect Hashing is accomplished by 3-D rotation, translation and enlarging the rectangular box with a factor √3 in each direction.

### Disclaimers

Anything free comes without referee :-(
My English may be better than your Dutch.