---
categories: Algorithm techniques, Graph algorithms
---

## Linear sweep

### Problems
- [Pinball](https://open.kattis.com/problems/pinball)
- [A Safe Bet](https://open.kattis.com/problems/safebet)
- [Square Pie](https://open.kattis.com/problems/squarepie)
- [Grid MST](https://open.kattis.com/problems/gridmst)
- [Red Blue Line Segments](http://www.spoj.com/problems/CS345A1/)

## Angular sweep

### Problems
- [Logging](https://codingcompetitions.withgoogle.com/codejam/round/00000000004336e9/0000000000433d3a)
- [Phone Cell](http://contest.felk.cvut.cz/07cerc/solved/c/)
- [Beacons](https://open.kattis.com/problems/beacons)

## See also
- [Rotating calipers]()
- [Closest pair of points]()
- [Line segment intersection]()

## External links
- [Line Sweep Algorithms](https://www.topcoder.com/community/data-science/data-science-tutorials/line-sweep-algorithms/) (and [code](https://apps.topcoder.com/forums/?module=Thread&threadID=684537&start=0) by the same author)
- [Plane-sweep: A general-purpose algorithm for two-dimensional problems illustrated using line segment intersection](http://www.jn.inf.ethz.ch/education/script/P6_C25.pdf)
- [Lecture 24: Geometry](http://courses.csail.mit.edu/6.006/spring11/lectures/lec24.pdf)
- [Intersection of a Set of Segments](http://geomalgorithms.com/a09-_intersect-3.html)
- [How to sweep like a Sir](http://codeforces.com/blog/entry/20377)