1. Problem

  BOJ_1708 is the convex hull problems solved by Convex Hull algorithm. The levels of problem are Platinum 5.(Link of the problem of BOJ)

Inputs

  • The number of the points $N (3\leq N \leq 100,000)$
  • x-coordinate and y-coordinate of points $| x|, | y| \leq 40,000 $

Outputs

  • The number of points of the convex hull covering all input points.

Time & Space Limit

  • Time limit: 2 sec
  • Space limit: 128 MB



2. Convex Hull Algorithms

Fig 1. Convex, Convex Hull

  Convex is a subset $S$ of the plane if and only if for any pair of points $p, q \in S$ the line segment $\overline{pq}$ is completely contained in $S$. In the Fig 1., the left yellow plane is not convex, since the left black line between two points is not included in the plane. On the contrary, the right yellow plane is the convex of $S$. Convex Hull of $S$ is the smallest convex set that contains $S$.

Naive Algorithm

Fig 2. The upper lines and lower lines of the convex hull

  Think about the upper lines of the convex hull. If upper lines start from left, then the direction of the lines is from left to right. And, all points of $S$ except the points on the upper line have to be right side of upper lines. So, check the each pssible line whether all points are on the right side of that. When checking whether a point is on the left side or the right side of a line, use CCW algorithm. If the result of the algorithm is negative, then a point is on the left side of a line, else on the right side. About the lower lines, do same process reverse.
Sadly, its running time is $O(N^3)$.

With Sorting the points

Fig 3. an example of the process, when checking the $i$th point

  To optimize this algorithm, we sort the points left to right. By sorting the points of $S$ in increasing order according to x-coordinate(if points are on the same vertical slab, sort in increasing order according to y-coordinate), we can scan points from left to right. If the sequence of the points is $p_1, p_2, … ,p_N$ in lexicographic order, check the points one by one whether the each point is on the line of the convex hull. If we compute the points on the upper lines, $p_1, … p_{i-1}$ is the sequence of the points on the upper lines before considering the $i$th point. If $p_i$ is on the left side of the line $\overline{p_{i-2}p_{i-1}}$, the line $\overline{p_{i-2}p_{i-1}}$ is not on the upper lines of the convex hull. Then, drop out the $p_{i-1}$, and check iteratively the line $\overline{p_{i-3}p_{i-2}}$. Else, $p_i$ is the point on the upper lines(until it will be dropped). For referring the points, use the stack consisting of the points on the line of convex hull.

Fig 4. the degenerate case

  Since points are already sorted in increasing order according to x-coordinate, the direction of $\overline{p_{i-1}p_i}$ is always from left to right. Furtheremore, it is important to sort the points, whose x-coordinate is same, in increasing order according to y-coordinate. As you can see in Fig 4., if the last accessed point is the last point in each order, using below one(descending order acoording to y-coordinate) cannot drop the last point which is not the point of the convex hull. Focus on that we have to keep the property, “The points not of the convex hull have to be on the left side of the last edge we consider.
  Time complexity of this algorithm is $O(nlog{n})$. It depends on the preprocessing(points sorting). In main process, each point is checked only one time in linear traversal. And, each points can be dropped only one time. So, running time of main process is $O(n)$.

Optimization

Fig 5. The sequence of the points in descending order according to CCW for the pivot.

  The above way to compute the convex hull need to compute upper lines and lower lines respectively. It does not affect the total time complexity of the algorithm, but we have to operate the process twice. We can reduce running time by running the process only one time. For this, the points are sorted in descending order according to CCW for the point $p_{pivot}$. $p_{pivot}$ is the lowest and leftmost point. Descending order according to CCW for $p_{pivot}$ is similar with the order of the outermost. If CCW of points is same, then sort the points in descending order according to y-coordinate. And, run same process above with checking whether $p_i$ is on left side. It makes the lines of the convex hull rotating counterclockwise. As you can see in Fig 5., $p_i$ does not exist behind the direction of $\overline{p_{i-2}p_{i-1}}$. The ccw of some points for the pivot can be same. For handling this degenerate case, the points have to be sorted in increasing order according to the distance with the pivot. Think the dash line of Fig 5 like a vertical slab in Fig 4. Then you can understand why the order is chosen.

Psuedocode

Input A set $P$ of points in the plane $S$
Output A list containing the points of the convex hull of $S$
$pivot \leftarrow the lowest and leftmost point$
Sort the points in descending order according to CCW for $pivot$.
$stk \leftarrow \text{empty stack}$
$stk.push(p_1); stk.push(p_2)$
$i \leftarrow 3$
while $i \leq N$ do
       while not $stk.empty()$ do
              $p_{i-1} \leftarrow stk.top(); stk.pop()$
              $p_{i-2} \leftarrow stk.top();$
              if ccw between $p_i$ and $\overline{p_{i-2}p_{i-1}} > 0$
                     $stk.push(p_{i-1}); break$
       $stk.push(p_i)$
return elements of $stk$



3. Source code



Refers

Mark Berg, Otfried Cheong, Marc Kreveld, Mark Overmars, “Computational Geometry: Algorithms and applications 3rd”
rbdud96, “문제 해결 기법 - 11일차 - 계산 기하 - Convex Hull, Graham scan, Quick Hull”