Uniformly inserting points on square grid

We consider the problem of inserting points in a square grid, which has many motivations, including halftoning in reprography and image processing. The points are inserted one at a time. The objective is to distribute the points as uniformly as possible. More specifically, after each insertion, the gap ratio should be as small as possible. We give an insertion strategy with a maximal gap ratio no more than 22≈2.828, which is the first result in uniformly inserting points in a grid. Moreover, we show that no online algorithm can achieve the maximal gap ratio strictly less than 2.5 for a 3×33×3 grid.

► Study the problem of inserting points on grid. ► Give the first algorithm for uniformly inserting points on square grid. ► The maximal gap ratio of our algorithm is 2.828.