Scanline algorithms on a grid (Q1111020)

In computational geometry (the design and analysis of explicit algorithms and data structures representing geometrical objects in Euclidean space) there exists a large collection of problems where the results are determined almost completely by the order relations between coordinates rather than by these coordinates themselves. A typical example is the problem of determining the maximal points in a finite point set under the partial order ``being greater than in both coordinates''. This makes it possible to transform the input from a set of points with real coordinates into points with integer coordinates within the range 1...n where n is the number of points; this transformation preserves the structure of the answers. The advantage is that the transformed problem supports the use of clever data structures and algorithms which otherwise would not be applicable. The disadvantage is that the transformation requires the input data to be sorted leading to an additional O(n log(n)) term in the complexity for the algorithms. For many of these problems the complexity is O(n log(n)) anyhow and then the transformation doesn't make sense. If the input however consists of points on a grid rather than points with arbitrary real coordinates there are alternative ways of sorting points and preserving order in a finite set under insertions and deletions, and this opens the road towards the list of improved bounds as presented in the paper. In the list presented on the second page of the paper the general pattern is that factors log(n) are replaced by log log(n) or log \(log_ n(u)\) where u is the ``universe size'' (number of grid points in one direction). The first replacement indicates that the efficient priority deques as discovered by the reviewer and modified by D. B. Johnson is used in the revised algorithm. The second replacement indicates the use of a sorting method of Kirkpatrick and Reisch. For the last three problems described the new bounds are obtained by more involved methods. The paper also introduces a number of data structures which are interesting by themselves.