Intersections

Much of the motivation for studying intersection problems stems from the simple fact that two objects cannot occupy the same place at the same time. An architectural design program must take care not to place doors where they cannot be opened or have corridors that pass through elevator shafts. In computer graphics, an object to be displayed obscures another if their projections on the viewing plane intersect. A pattern can be cut from a single piece of stock only if it can be laid out so that no two pieces overlap. The importance of developing efficient algorithms for detecting intersection is becoming apparent as industrial applications grow increasingly more ambitious: a complicated graphic image may involve one hundred thousand vectors, an architectural database often contains upwards of a million elements, and a single integrated circuit may contain millions of components. In such cases even quadratic-time algorithms are unacceptable.