INPUT OUTPUT

**Problem:**
Which pairs of line segments intersect each other?
What is the intersection of *P_1* and *P_2*?

**Excerpt from**
The Algorithm Design Manual:
Intersection detection is a fundamental geometric primitive
that arises in many applications.
Picture a virtual-reality
simulation of an architectural model for a building.
The illusion of reality vanishes the instant the virtual person
walks through a virtual wall.
To enforce such physical constraints,
any such intersection between polyhedral models
must be immediately detected and the operator notified or constrained.

Another application of intersection detection is design rule checking for VLSI layouts. A minor design mistake resulting in two crossing metal strips can short out the chip, but such errors can be detected before fabrication using programs to find all intersections between line segments.

Computational Geometry : Algorithms and Applications by Mark De Berg, Marc Van Kreveld, Mark Overmars, and O. Schwartskopf | Computational Geometry in C by Joseph O'Rourke | Computational Geometry: an introduction through randomized algorithms by K. Mulmuley |

Algorithms and Data Structures with applications to graphics and geometry by J. Nievergelt and K. Hinrichs | Algorithms from P to NP, Vol. I: Design and Efficiency by B. Moret and H. Shapiro | Introduction to Algorithms by T. Cormen and C. Leiserson and R. Rivest and C. Stein |

Introduction to Algorithms by U. Manber | Computational Geometry by F. Preparata and M. Shamos |

This page last modified on 2008-07-10 . www.algorist.com