# Sweep Line

Authors: Benjamin Qi, Andi Qu

### Prerequisites

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.

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

Resources | |||
---|---|---|---|

CPH | |||

TC |

## 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.

### Problems

Status | Source | Problem Name | Difficulty | Tags | Solution |
---|---|---|---|---|---|

CEOI | Very Hard | Check CF | |||

Baltic OI | Very Hard | View Solution |

## Manhattan MST

Focus Problem – read through this problem before continuing!

(KACTL code)

explanation? topcoder prob has

Status | Source | Problem Name | Difficulty | Tags | Solution |
---|---|---|---|---|---|

CSA | Hard | Check CSA |