Sweep Line - Summary

http://openinx.github.io/2013/01/01/plane-sweep-thinking/
有非常多的经典算法借助平面扫描的思想极大的降低了算法时间复杂度。例如线段相交问题、平面上多矩形轮廓算法、平面多矩形求交、空间冲突检测算法、Voronoi图构造算法、平面最近点对等等。

        平面扫描算法一般由扫描线、事件点和当前扫描线事件点集合三个部分组成。扫描线一般是一根平行于坐标轴的水平线（或垂直线）。它按照从上到下（或从左到右）的顺序，依次检测事件点，通过删除或新增事件点来维护当前扫描线事件点集合。当前扫描线事件点集合通常都是用线段树、树状数组、红黑树等平衡二叉树来维护的，特殊情况下也需要用Hash表、块状表、跳跃链表等高级数据结构来达到维护目的。通过查询当前扫描线事件点集合的相关信息，我们就可以获得问题的答案。

平面扫描思想是算法设计中的一个非常重要的思想，它通过充分利用事物之间的相邻性，能够更清晰的展示问题的本质，因而能够达到优化算法的目地。

在论文正文中，作者从数据统计、几何实体位置关系的检测、最近点对三个应用层次，依次详细分析了5个经典问题，并剖析了与经典问题相对应的比赛试题。对每个经典问题，论文都有清晰细致的算法流程描述和详尽的时间复杂度分析，必要时给出了算法的证明。

正文中的扫描线算法基本由三个部分组成：扫描线、待扫描事件（一般有插入事件和删除事件）、维护当前扫描线相关事件（一般是平衡二叉树、线段树等树形结构，也有块状链表、跳跃表的情况）。事先将待扫描事件按照某个顺序排好序，然后扫描线依序扫描各事件。对不同类型的事件，将当前扫描线相关事件进行相应的维护。最后，通过查询当前扫描线相关事件的某些信息，就能计算得到问题的解的信息。扫描线算法正是在处理相邻事件的过程中，获知问题的答案信息的。

https://www.topcoder.com/community/competitive-programming/tutorials/line-sweep-algorithms/
They are all based on the simple but powerful idea of a sweep line: a vertical line that is conceptually “swept” across the plane. In practice, of course, we cannot simulate all points in time and so we consider only some discrete points

In several places I’ll refer to the Euclidean and Manhattan distances. The Euclidean distance is the normal, everyday distance given by Pythagoras’ Theorem. The Manhattan distance between points (x1, y1) and (x2, y2) is the distance that must be travelled while moving only horizontally or vertically, namely |x1 – x2| + |y1 - y2|. It is called the Manhattan distance because the roads in Manhattan are laid out in a grid and so the Manhattan distance is the distance that must be travelled by road (it is also called the “taxicab distance,” or more formally the L1 metric).

In addition, a balanced binary tree is used in some of the algorithms. Generally you can just use a set in C++ or a TreeSet in Java, but in some cases this is insufficient because it is necessary to store extra information in the internal nodes.

Closest Pair
Problem: Find the closest pair of points in the given array of $N$ distinct points
This problem can be solved by comparing all pairs of points , but then its complexity is $O(N^2)$
So, we need a better algorithm for this . Here, we'll discuss it using line sweep technique.

https://baptiste-wicht.com/posts/2010/04/closest-pair-of-point-plane-sweep-algorithm.html

1. We sort the list of points from left to right in the x axis
2. And then for each point :
   1. We remove from the candidates all the point that are further in x axis that the current min distance
   2. We take all the candidates that are located more or less current min distance from the current point in y axis
   3. We test for the min distance all the founded candidates with the current point
   4. And finally we add the current point to the list of candidates

Union Of Rectangles
Problem: Given a set of $N$ axis aligned rectangles(edges of rectangles parallel to x axis or y axis), find the area of union of all of the rectangles. A rectangle is represented by two points , one lower-left point and one upper-right point.
https://stomachache007.wordpress.com/2017/10/29/九章算法高级班笔记4-二分法深入和扫描线-2/
扫描问题的思路
事件往往是以区间的形式存在
区间两端代表事件的开始和结束
需要排序

https://www.topcoder.com/community/competitive-programming/tutorials/line-sweep-algorithms/

BoxUnion
This is the union of area of rectangles problem above. In this instance there are at most three rectangles which makes simpler solutions feasible, but you can still use this to practice.

CultureGrowth
While written in a misleading fashion, the task is just to compute the area of the convex hull of a set of points.

PowerSupply
For each power line orientation, sweep the power line in the perpendicular direction. Consumers are added D units ahead of the sweep and dropped D units behind the sweep. In fact, the low constraints mean that the connected set can be computed from scratch for each event.

ConvexPolygons
The events of interest are the vertices of the two polygons, and the intersection points of their edges. Between consecutive events, the section cut by the sweep line varies linearly. Thus, we can sample the cut area at the mid-point X value of each of these regions to get the average for the whole region. Sampling at these mid-points also eliminates a lot of special-case handling, because the sweep line is guaranteed not to pass anywhere near a vertex. Unlike the solution proposed in the match editorial, the only geometric tool required is line-line intersection.