Rare
 0/6

Sweep Line

Authors: Benjamin Qi, Andi Qu

Introduction to line sweep.

Imagine you have a vertical line that "sweeps" the plane from left to right. That's the main idea behind the sweep line.

You might be thinking "wait - isn't keeping track of the sweep line at all possible positions super inefficient?" And you'd be correct. However, we don't actually need to keep track of the sweep line at all possible positions - only at the "critical" positions (e.g. points and intersections).

This section is not complete.

Feel free to file a request to complete this using the "Contact Us" button.

should the reader already be familiar with the 1D case (union of intervals on number line?) never explicitly mentioned in module

Closest Pair

Focus Problem – read through this problem before continuing!

Solution 1

(Divide and Conquer)

Solution 2

(Set)

Line Segments

Focus Problem – read through this problem before continuing!

Solution

This section is not complete.

Feel free to file a request to complete this using the "Contact Us" button.

Problems

StatusSourceProblem NameDifficultyTagsSolution
CEOIVery HardCheck CF
Baltic OIVery HardView Solution

Manhattan MST

Focus Problem – read through this problem before continuing!

(KACTL code)

explanation? topcoder prob has

StatusSourceProblem NameDifficultyTagsSolution
CSAHardCheck CSA

Module Progress:

Give Us Feedback on Sweep Line!