Multiple line segment intersection

In computational geometry, the multiple line segment intersection problem supplies a list of line segments in the Euclidean plane and asks whether any two of them intersect (cross).

Uses your system voice; voice and rate in settings.

Snapshot

≈ 3 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

In computational geometry, the multiple line segment intersection problem supplies a list of line segments in the Euclidean plane and asks whether any two of them intersect (cross).

Simple algorithms examine each pair of segments. However, if a large number of possibly intersecting segments are to be checked, this becomes increasingly inefficient since most pairs of segments are not close to one another in a typical input sequence. The most common, and 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[1] 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.

Contents

See also

edit edit source

References

edit edit source
  1. ^ Shamos, M. I.; Hoey, D. (1976). "17th Annual Symposium on Foundations of Computer Science (sfcs 1976)" (PDF): 208. doi:10.1109/SFCS.1976.16. S2CID 124804. {{cite journal}}: Cite journal requires |journal= (help) Chapter: "Geometric intersection problems" Wikipedia revision 1278568472, retrieved 2026-11-20

Further reading

edit edit source edit edit source

Text derived from https://en.wikipedia.org/w/index.php?oldid=1278568472 under CC BY-SA 4.0; modifications have been made.