Karlsson, R. G. and Overmars, M. H. (1986). Scanline Algorithms on a Grid. Technical Report LiTH-IDA-R-86-30, Department of Computer and Information Science, Linköping University, Sweden. (bibtex),
Abstract: A number of important problems in computational geometry are solved efficiently on 2- or 3-dimensional grids by means of scanline techniques. In the solutions to the maximal elements and closure problems, a factor log n is substituted by loglog u, where n is the set size and u the grid size. 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.
CS Dept TR Overview