Line Segments Intersection

Two algorithms were implemented for line segments intersection: the brute force (left) - every two line segments are checked for intersection) and Balaban's algorithm (right). The left one has an asimptotic running time of O(n²); the right one has an asimptotic running time of O(n log²(n)+k) where n is the number of segments and k is the number of intersection points.

• Balaban's algorithm behaves worse than the other one for k=O(n²) and for small values of n.
• The colors do not have any particular meaning; they are just for artistic impression
• choose "reset smart" to get a configuration where k=O(n)