@techreport{R-86-30,
TITLE = {Scanline Algorithms on a Grid},
AUTHOR = {Rolf G. Karlsson and Mark H. Overmars },
YEAR = {1986},
NUMBER = {R-86-30},
INSTITUTION = ida,
ADDRESS = idaaddr,
ABSTRACTURL = {/publications/cgi-bin/tr-fetch.pl?r-86-30+abstr},
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.},
IDANR = {LiTH-IDA-R-86-30}