**Dept. of Computer and Information science, Linköping University**

## IDA Technical Reports: abstract

*Generated: Mon, 30 May 2016 16:31:41 *

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.

**Goto (at Linköping University):**
```
CS Dept
TR Overview
```

*<webmaster@ida.liu.se>*