In computational geometry, the line segment intersection problem supplies a list of line segments in the plane and asks whether any two of them intersect, or cross.
Naive algorithms examine each pair of segments, but for a high number of possibly intersecting segments this becomes increasingly inefficient since most pairs of segments are not close to one another in a typical input sequence.
The most common, more efficient way to solve this problem for a high number of segments is to use a sweep line algorithm, where we imagine a line sliding across the line segments and we track which line segments it intersects at each point in time using a dynamic data structure based on binary search trees. The Shamos–Hoey algorithm applies this principle to solve the line segment intersection detection problem, as stated above, of determining whether or not a set of line segments has an intersection; the Bentley–Ottmann algorithm works by the same principle to list all intersections in logarithmic time per intersection.
Famous quotes containing the words line and/or intersection:
“The modern picture of The Artist began to form: The poor, but free spirit, plebeian but aspiring only to be classless, to cut himself forever free from the bonds of the greedy bourgeoisie, to be whatever the fat burghers feared most, to cross the line wherever they drew it, to look at the world in a way they couldn’t see, to be high, live low, stay young forever—in short, to be the bohemian.”
—Tom Wolfe (b. 1931)
“You can always tell a Midwestern couple in Europe because they will be standing in the middle of a busy intersection looking at a wind-blown map and arguing over which way is west. European cities, with their wandering streets and undisciplined alleys, drive Midwesterners practically insane.”
—Bill Bryson (b. 1951)