Geometry -> Sweep Line

Sort events and maintain an active structure while a conceptual line moves across the plane.

• Topic slug: geometry/sweep-line
• Tutorial page: Open tutorial
• Ladder page: Open ladder
• Repo problems currently tagged here: 3
• Repo companion pages: 0
• Curated external problems: 6

Microtopics

• event-sorting
• active-set
• closest-pair
• interval-union
• segment-intersections
• range-counting

Learning Sources

Source	Type
Topcoder line sweep algorithms	Essay / Blog
USACO Guide sweep line	Reference
Competitive Programmer's Handbook	Reference

Practice Sources

Source	Type
CSES Intersection Points	Practice
CSES Minimum Euclidean Distance	Practice
CSES Area of Rectangles	Practice

Curated External Problems

Core

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Line Segments Trace I	CSES	Medium	Envelope	-	-	Scan; Max-Query; Segments	Scan-line style reasoning over many segments.
Line Segments Trace II	CSES	Hard	Envelope	-	-	Scan; Events; Segments	A more intricate sweep-line companion problem.

Challenge

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Area of Rectangles	CSES	Hard	Area-Union	Coordinate Compression	Event Sweep; Interval Coverage	Rectangle Union; Events; Coordinate-Compression; Rectangles	The classic rectangle-union sweep benchmark.
Intersection Points	CSES	Hard	Intersection-Counting	Event Sorting	Ordered Events; Fenwick Tree / Balanced Bst	Orthogonal Segments; Intersections; Events; Active-Set	A textbook sweep-line intersection counter.
Lines and Queries I	CSES	Hard	-	Online; Data-Structure-Heavy	Convex Hull Trick Basics; Line Evaluation	Line Containers; Optimization	Not a pure sweep line, but a great event-driven geometry/data-structure hybrid.
Minimum Euclidean Distance	CSES	Hard	-	Divide-And-Conquer; Sweep-Line	Sorting; Plane Sweep Intuition	Closest Pair	The closest-pair sweep is a classic geometry engineering benchmark.

Repo Problems

Code	Title	Fit	Difficulty	Pattern	Note	Solution
KINGDOMS	KINGDOMS	primary	hard	laminar regions; sweep events; containment tree	Note	Code
MINIMUMEUCLIDEANDISTANCE	Minimum Euclidean Distance	secondary	hard	closest pair sweep line; active strip by x distance; ordered set by y	Note	Code
VOTELPH	Bà Nà	primary	hard	piecewise maximum; endpoint preprocessing; parabola envelopes	Note	Code

Regeneration

python3 scripts/generate_problem_catalog.py