Scanline algorithms on a grid

A number of important problems in computational geometry are solved efficiently on 2- or 3-dimensional grids by means of scanline techniques. In the time complexity of solutions to the maximal elements and closure problems, a factor logn is substituted by loglogn, wheren is the number of elements. Next, by using a data structure introduced in the paper, the interval trie, previous solutions to the rectangle intersection and connected component problems are improved upon. Finally, a fast intersection finding algorithm for arbitrarily oriented line segments is presented.