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:
“I had crossed de line of which I had so long been dreaming. I was free; but dere was no one to welcome me to de land of freedom. I was a stranger in a strange land, and my home after all was down in de old cabin quarter, wid de ole folks, and my brudders and sisters. But to dis solemn resolution I came; I was free, and dey should be free also; I would make a home for dem in de North, and de Lord helping me, I would bring dem all dere.”
—Harriet Tubman (c. 18201913)
“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)