V

Algorithm Visualizer

ZHEN
Share on WeiboShare on XGitHub repositoryAuthor website
Learning ToolsAlgorithm Complexity ReferenceAlgorithm Learning Paths
Data StructuresArrayLinked ListStackQueue and DequeBinary Search TreeBinary HeapHash TableGraphTrieDisjoint Set UnionLRU CacheSkip ListSegment TreeB+ TreeBloom FilterFenwick Tree
SortingBubble SortCocktail Shaker SortBitonic SortSelection SortInsertion SortBinary Insertion SortShell SortMerge SortTop-Down Merge SortQuick SortThree-Way Quick SortDual-Pivot Quick SortHeap SortCounting SortRadix SortBucket Sort
Graph AlgorithmsDijkstra's Shortest PathKruskal's Minimum Spanning TreePrim's Minimum Spanning TreeBellman-Ford Shortest PathsTopological SortFloyd-WarshallStrongly Connected Components2-SATMaximum FlowBipartite MatchingLowest Common AncestorEulerian Path
Dynamic ProgrammingEdit Distance0/1 KnapsackUnbounded KnapsackLongest Common SubsequenceLongest Increasing SubsequenceCoin ChangeStone MergingTraveling Salesperson DPTree Dynamic ProgrammingDigit DPRerooting DP
Backtracking and SearchN-QueensSubsetsPermutationsCombination SumMaze Solving with DFSNumber of IslandsWord SearchSudoku SolverA* Search
StringsKMP String MatchingRabin-Karp String MatchingBoyer-Moore String MatchingManacher's Longest Palindromic SubstringSuffix ArrayLCP ArrayAho-Corasick AutomatonZ Function
Math and Number TheorySieve of EratosthenesLinear SieveEuclidean AlgorithmBinary ExponentiationExtended Euclidean AlgorithmChinese Remainder TheoremEuler's Totient FunctionMiller-Rabin Primality TestFast Fourier TransformPollard's Rho Factorization
Computational GeometryConvex HullRotating CalipersClosest Pair of PointsLine Segment IntersectionBentley-Ottmann Sweep Line
SearchingBinary SearchLower and Upper BoundSearch in a Rotated Sorted ArrayBinary Search on the AnswerTernary Search

Bentley-Ottmann Sweep Line

Process endpoint and crossing events while a balanced status order tests only neighboring segments.

Core idea

Sweep events from left to right while a balanced status structure orders segments by their current vertical position. Only neighboring segments can create the next unseen intersection.

Read the visualization

The sweep line advances through endpoint and crossing events. The status order inserts, removes, or swaps segments, and only newly adjacent pairs schedule tests.

Initialize endpoint events and an empty vertical sweep-line status.

1function bentleyOttmann(segs: Seg[]): Pt[] {
2 const events = new EventQueue(segs); // init point init x init queue
3 const status = new SweepStatus(); // init segment init y ordered
4 const out: Pt[] = [];
5 while (!events.empty()) {
6 const e = events.pop(); // start left event
7 if (e.type === 'start') status.insert(e.seg);
8 else if (e.type === 'end') status.remove(e.seg);
9 else { out.push(e.pt); status.swap(e.s1, e.s2); } // cross point
10 for (const [u, v] of status.newAdjacent()) // cross pair
11 events.addCross(intersect(u, v)); // cross point cross queue
12 }
13 return out;
14}
segmentA(1,1)-(9,9), B(2,8)-(8,2), C(2.5,6)-(8.5,6)
event queue6 endpoint events ( enqueue intersection events dynamically)
1 / 11

Complexity and tradeoffs

Time: O((n+k) log n). Space: O(n+k). The output-sensitive bound reports k intersections without comparing every pair of n segments.

Invariant: Between consecutive events, the status structure has the same vertical order as the segments crossing the sweep line.

Where it fits

Bentley-Ottmann reports all intersections output-sensitively. Robust event ordering and exact predicates are essential in production geometry systems.