1985 | OriginalPaper | Chapter
Intersections
Authors : Franco P. Preparata, Michael Ian Shamos
Published in: Computational Geometry
Publisher: Springer New York
Included in: Professional Book Archive
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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.