![]() In other words, it is enough to limit yourself only to the positions equal to the abscissas of the end points of the segments. It is enough to consider the sweep line not in all possible real positions $(-\infty \ldots \infty)$, but only in those positions when new segments appear or old ones disappear.To find an intersecting pair, it is sufficient to consider only adjacent segments at each fixed position of the sweep line.This order is interesting because intersecting segments will have the same $y$-coordinate at least at one time: Namely, we will store a list of segments crossing the sweep line at a given time, where the segments will be sorted by their $y$-coordinate on the sweep line. We are interested in the relative order of the segments along the vertical. Thus, for each segment, at some point in time, its point will appear on the sweep line, then with the movement of the line, this point will move, and finally, at some point, the segment will disappear from the line. In the course of its movement, this line will meet with segments, and at each time a segment intersect with our line it intersects in exactly one point (we will assume that there are no vertical segments). Let's draw a vertical line $x = -\infty$ mentally and start moving this line to the right. This article describes an algorithm with the runtime time $O(n \log n)$, which is based on the sweep line algorithm. The naive solution algorithm is to iterate over all pairs of segments in $O(n^2)$ and check for each pair whether they intersect or not. If the answer is yes, then print this pair of intersecting segments it is enough to choose any of them among several answers. It is required to check whether at least two of them intersect with each other. The Stern-Brocot Tree and Farey Sequences Optimal schedule of jobs given their deadlines and durationsġ5 Puzzle Game: Existence Of The Solution MEX task (Minimal Excluded element in an array) Search the subsegment with the maximum/minimum sum RMQ task (Range Minimum Query - the smallest element in an interval) Kuhn's Algorithm - Maximum Bipartite Matching Maximum flow - Push-relabel algorithm improved Maximum flow - Ford-Fulkerson and Edmonds-Karp Lowest Common Ancestor - Tarjan's off-line algorithm Lowest Common Ancestor - Farach-Colton and Bender algorithm Second best Minimum Spanning Tree - Using Kruskal and Lowest Common AncestorĬhecking a graph for acyclicity and finding a cycle in O(M) Minimum Spanning Tree - Kruskal with Disjoint Set Union ![]() Number of paths of fixed length / Shortest paths of fixed length Strongly Connected Components and Condensation Graphĭijkstra - finding shortest paths from given vertexīellman-Ford - finding shortest paths with negative weightsįloyd-Warshall - finding all shortest paths ![]() Half-plane intersection - S
0 Comments
Leave a Reply. |