The rectangle intersection problem revisited

We take another look at the problem of intersecting rectangles with parallel sides. For this we derive a one-pass, time optimal algorithm which is easy to program, generalizes tod dimensions well, and illustrates a basic duality in its data structures and approach.The work of the first author was supported by the DAAD (Deutscher Akademischer Austauschdienst) and carried out while visiting McMaster University as a postdoctoral fellow. The work of the second author was supported by a Natural Sciences and Engineering Research Council of Canada Grant No. A-7700.