Chan's algorithm

A single pass of the algorithm requires a parameter $m$ which is between 0 and $n$ (number of points of our set $P$). Ideally, $m\; =\; h$ but $h$, the number of vertices in the output convex hull, is not known at the start. Multiple passes with increasing values of $m$ are done which then terminates when $m\; \backslash geq\; h$(see below on choosing parameter $m$).

The algorithm starts by arbitrarily partitioning the set of points $P$ into $K\; =\; \backslash lceil\; n/m\; \backslash rceil$ subsets $(Q\_k)\_\{k=1,2,...K\}$ with at most $m$ points each; notice that $K=O(n/m)$.

For each subset $Q\_k$, it computes the convex hull, $C\_k$, using an $O(p\; \backslash log\; p)$ algorithm (for example, Graham scan), where $p$ is the number of points in the subset. As there are $K$ subsets of $O(m)$ points each, this phase takes $K\backslash cdot\; O(m\; \backslash log\; m)\; =\; O(n\; \backslash log\; m)$ time.

During the second phase, Jarvis's march is executed, making use of the precomputed (mini) convex hulls, $(C\_k)\_\{k=1,2,...K\}$. At each step in this Jarvis's march algorithm, we have a point $p\_\{i\}$ in the convex hull (at the beginning, $p\_\{i\}$ may be the point in $P$ with the lowest y coordinate, which is guaranteed to be in the convex hull of $P$), and need to find a point $p\_\{i+1\}\; =\; f(p\_\{i\},P)$ such that all other points of $P$ are to the right of the line $p\_\{i\}p\_\{i+1\}${{clarify|reason=Why to the right and not to the left?|date=March 2018}}, where the notation $p\_\{i+1\}\; =\; f(p\_\{i\},P)$ simply means that the next point, that is $p\_\{i+1\}$, is determined as a function of $p\_\{i\}$ and $P$. The convex hull of the set $Q\_k$, $C\_k$, is known and contains at most $m$ points (listed in a clockwise or counter-clockwise order), which allows to compute $f(p\_\{i\},Q\_k)$ in $O(\backslash log\; m)$ time by binary search{{how|date=March 2018}}. Hence, the computation of $f(p\_\{i\},Q\_k)$ for all the $K$ subsets can be done in $O(K\; \backslash log\; m)$ time. Then, we can determine $f(p\_\{i\},P)$ using the same technique as normally used in Jarvis's march, but only considering the points $(f(p\_\{i\},Q\_k))\_\{1\backslash leq\; k\backslash leq\; K\}$ (i.e. the points in the mini convex hulls) instead of the whole set $P$. For those points, one iteration of Jarvis's march is $O(K)$ which is negligible compared to the computation for all subsets. Jarvis's march completes when the process has been repeated $O(h)$ times (because, in the way Jarvis march works, after at most $h$ iterations of its outermost loop, where $h$ is the number of points in the convex hull of $P$, we must have found the convex hull), hence the second phase takes $O(Kh\; \backslash log\; m)$ time, equivalent to $O(n\; \backslash log\; h)$ time if $m$ is close to $h$ (see below the description of a strategy to choose $m$ such that this is the case).

By running the two phases described above, the convex hull of $n$ points is computed in $O(n\; \backslash log\; h)$ time.

If an arbitrary value is chosen for $m$, it may happen that

At that moment, $O(n\; \backslash log\; m)$ time will have been spent, and the convex hull will not have been calculated.

The idea is to make multiple passes of the algorithm with increasing values of $m$; each pass terminates (successfully or unsuccessfully) in $O(n\; \backslash log\; m)$ time. If $m$ increases too slowly between passes, the number of iterations may be large; on the other hand, if it rises too quickly, the first $m$ for which the algorithm terminates successfully may be much larger than $h$, and produce a complexity $O(n\; \backslash log\; m)\; >\; O(n\; \backslash log\; h)$.

One possible strategy is to square the value of $m$ at each iteration, up to a maximum value of $n$ (corresponding to a partition in singleton sets).{{cite journal

| last1=Chazelle | first1=Bernard | authorlink1=Bernard Chazelle

| last2=Matoušek | first2=Jiří | authorlink2=Jiří Matoušek (mathematician)

| title=Derandomizing an output-sensitive convex hull algorithm in three dimensions

| journal=Computational Geometry

| volume=5

| pages=27–32

| date=1995

| doi=10.1016/0925-7721(94)00018-Q | doi-access=free}} Starting from a value of 2, at iteration $t$, $m\; =\; \backslash min\; \backslash left(n,2^\{2^t\}\; \backslash right)$ is chosen. In that case, $O(\backslash log\backslash log\; h)$ iterations are made, given that the algorithm terminates once we have

:$m\; =\; 2^\{2^t\}\; \backslash geq\; h\; \backslash iff\; \backslash log\; \backslash left(\; 2^\{2^t\}\; \backslash right)\; \backslash geq\; \backslash log\; h\; \backslash iff\; 2^t\; \backslash geq\; \backslash log\; h\; \backslash iff\; \backslash log\; \{2^t\}\; \backslash geq\; \backslash log\; \{\backslash log\; h\}\; \backslash iff\; t\; \backslash geq\; \backslash log\; \{\backslash log\; h\},$

with the logarithm taken in base $2$, and the total running time of the algorithm is

:$\backslash sum\_\{t=0\}^\{\backslash lceil\; \backslash log\backslash log\; h\; \backslash rceil\}\; O\backslash left(n\; \backslash log\; \backslash left(2^\{2^t\}\; \backslash right)\backslash right)\; =\; O(n)\; \backslash sum\_\{t=0\}^\{\backslash lceil\; \backslash log\backslash log\; h\; \backslash rceil\}\; 2^t\; =\; O\backslash left(n\; \backslash cdot\; 2^\{1+\backslash lceil\; \backslash log\backslash log\; h\; \backslash rceil\}\backslash right)\; =\; O(n\; \backslash log\; h).$

To generalize this construction for the 3-dimensional case, an $O(n\; \backslash log\; n)$ algorithm to compute the 3-dimensional convex hull by Preparata and Hong should be used instead of Graham scan, and a 3-dimensional version of Jarvis's march needs to be used. The time complexity remains $O(n\; \backslash log\; h)$.

In the following pseudocode, text between parentheses and in italic are comments. To fully understand the following pseudocode, it is recommended that the reader is already familiar with Graham scan and Jarvis march algorithms to compute the convex hull, $C$, of a set of points,

$P$.

:Input: Set $P$ with $n$ points .

:Output: Set $C$ with $h$ points, the convex hull of $P$.

:: (Pick a point of $P$ which is guaranteed to be in $C$: for instance, the point with the lowest y coordinate.)

:: (This operation takes $\backslash mathcal\{O\}(n)$ time: e.g., we can simply iterate through $P$.)

::$p\_1\; :=\; PICK\backslash \_START(P)$

::($p\_0$ is used in the Jarvis march part of this Chan's algorithm,

:: so that to compute the second point, $p\_2$, in the convex hull of $P$.)

:: (Note: $p\_0$ is not a point of $P$.)

::(For more info, see the comments close to the corresponding part of the Chan's algorithm.)

::$p\_0\; :=\; (-\backslash infty,\; 0)$

:: (Note: $h$, the number of points in the final convex hull of $P$, is not known.)

:: (These are the iterations needed to discover the value of $m$, which is an estimate of $h$.)

:: ($h\; \backslash leq\; m$ is required for this Chan's algorithm to find the convex hull of $P$.)

:: (More specifically, we want $h\; \backslash leq\; m\; \backslash leq\; h^2$, so that not to perform too many unnecessary iterations

:: and so that the time complexity of this Chan's algorithm is $\backslash mathcal\{O\}(n\; \backslash log\; h)$.)

:: (As explained above in this article, a strategy is used where at most $\backslash log\; \backslash log\; n$ iterations are required to find $m$.)

:: (Note: the final $m$ may not be equal to $h$, but it is never smaller than $h$ and greater than $h^2$.)

:: (Nevertheless, this Chan's algorithm stops once $h$ iterations of the outermost loop are performed,

:: that is, even if $m\; \backslash neq\; h$, it doesn't perform $m$ iterations of the outermost loop.)

:: (For more info, see the Jarvis march part of this algorithm below, where $C$ is returned if $p\_\{i+1\}\; ==\; p\_1$.)

::for $1\backslash leq\; t\backslash leq\; \backslash log\; \backslash log\; n$ do

::: (Set parameter $m$ for the current iteration. A "squaring scheme" is used as described above in this article.

::: There are other schemes: for example, the "doubling scheme", where $m\; =\; 2^t$, for $t=1,\; \backslash dots,\; \backslash left\; \backslash lceil\; \backslash log\; h\; \backslash right\backslash rceil$.

::: If the "doubling scheme" is used, though, the resulting time complexity of this Chan's algorithm is $\backslash mathcal\{O\}(n\; \backslash log^2\; h)$.)

::: $m:=2^\{2^t\}$

::: (Initialize an empty list (or array) to store the points of the convex hull of $P$, as they are found.)

::: $C\; :=\; ()$

::: $ADD(C,\; p\_1)$

::: (Arbitrarily split set of points $P$ into $K\; =\; \backslash left\backslash lceil\; \backslash frac\{n\}\{m\}\; \backslash right\backslash rceil$ subsets of roughly $m$ elements each.)

:::$Q\_1,\; Q\_2,\; \backslash dots\; ,\; Q\_K\; :=\; SPLIT(P,\; m)$

::: (Compute the convex hull of all $K$ subsets of points, $Q\_1,Q\_2,\; \backslash dots\; ,\; Q\_K$.)

::: (It takes $\backslash mathcal\{O\}(K\; m\; \backslash log\; m)\; =\; \backslash mathcal\{O\}(n\; \backslash log\; m)$ time.)

::: If $m\; \backslash leq\; h^2$, then the time complexity is $\backslash mathcal\{O\}(n\; \backslash log\; h^2)\; =\; \backslash mathcal\{O\}(n\; \backslash log\; h)$.)

:::for $1\backslash leq\; k\backslash leq\; K$ do

:::: (Compute the convex hull of subset $k$, $Q\_k$, using Graham scan, which takes $\backslash mathcal\{O\}(m\; \backslash log\; m)$ time.)

:::: ($C\_k$ is the convex hull of the subset of points $Q\_k$.)

:::: $C\_k\; :=\; GRAHAM\backslash \_SCAN(Q\_k)$

::: (At this point, the convex hulls $C\_1,\; C\_2,\; \backslash dots,\; C\_K$ of respectively the subsets of points $Q\_1,\; Q\_2,\; \backslash dots\; ,\; Q\_K$ have been computed.)

::: (Now, use a modified version of the Jarvis march algorithm to compute the convex hull of $P$.)

::: (Jarvis march performs in $\backslash mathcal\{O\}(nh)$ time, where $n$ is the number of input points and $h$ is the number of points in the convex hull.)

::: (Given that Jarvis march is an output-sensitive algorithm, its running time depends on the size of the convex hull, $h$.)

::: (In practice, it means that Jarvis march performs $h$ iterations of its outermost loop.

::: At each of these iterations, it performs at most $n$ iterations of its innermost loop.)

::: (We want $h\; \backslash leq\; m\; \backslash leq\; h^2$, so we do not want to perform more than $m$ iterations in the following outer loop.)

::: (If the current $m$ is smaller than $h$, i.e. , the convex hull of $P$ cannot be found.)

::: (In this modified version of Jarvis march, we perform an operation inside the innermost loop which takes $\backslash mathcal\{O\}(\backslash log\; m)$ time.

::: Hence, the total time complexity of this modified version is

::: $\backslash mathcal\{O\}(m\; K\; \backslash log\; m)\; =\; \backslash mathcal\{O\}(m\; \backslash left\backslash lceil\; \backslash frac\{n\}\{m\}\; \backslash right\backslash rceil\; \backslash log\; m)\; =\; \backslash mathcal\{O\}(n\; \backslash log\; m)\; =\; \backslash mathcal\{O\}(n\; \backslash log\; 2^\{2^t\})\; =\; \backslash mathcal\{O\}(n\; 2^t).$

::: If $m\; \backslash leq\; h^2$, then the time complexity is $\backslash mathcal\{O\}(n\; \backslash log\; h^2)\; =\; \backslash mathcal\{O\}(n\; \backslash log\; h)$.)

:::for $1\backslash leq\; i\backslash leq\; m$ do

:::: (Note: here, a point in the convex hull of $P$ is already known, that is $p\_1$.)

:::: (In this inner for loop, $K$ possible next points to be on the convex hull of $P$, $q\_\{i,1\},\; q\_\{i,2\},\; \backslash dots,\; q\_\{i,K\}$, are computed.)

:::: (Each of these $K$ possible next points is from a different $C\_k$:

:::: that is, $q\_\{i,k\}$ is a possible next point on the convex hull of $P$ which is part of the convex hull of $C\_k$.)

:::: (Note: $q\_\{i,1\},\; q\_\{i,2\},\; \backslash dots,\; q\_\{i,K\}$ depend on $i$: that is, for each iteration $i$, there are $K$ possible next points to be on the convex hull of $P$.)

:::: (Note: at each iteration $i$, only one of the points among $q\_\{i,1\},\; q\_\{i,2\},\; \backslash dots,\; q\_\{i,K\}$ is added to the convex hull of $P$.)

:::: for $1\backslash leq\; k\backslash leq\; K$ do

::::: ($JARVIS\backslash \_BINARY\backslash \_SEARCH$ finds the point $d\; \backslash in\; C\_k$ such that the angle $\backslash measuredangle\; p\_\{i-1\}p\_id$ is maximized {{why|date=March 2018}},

::::: where $\backslash measuredangle\; p\_\{i-1\}p\_id$ is the angle between the vectors $\backslash overrightarrow\{p\_ip\_\{i-1\}\}$ and $\backslash overrightarrow\{p\_i\; d\}$. Such $d$ is stored in $q\_\{i,k\}$.)

::::: (Angles do not need to be calculated directly: the orientation test can be used {{how|date=March 2018}}.)

::::: ($JARVIS\backslash \_BINARY\backslash \_SEARCH$ can be performed in $\backslash mathcal\{O\}(\backslash log\; m)$ time{{how|date=March 2018}}.)

::::: (Note: at the iteration $i\; =\; 1$, $p\_\{i-1\}\; =\; p\_0\; =\; (-\backslash infty,\; 0)$ and $p\_1$ is known and is a point in the convex hull of $P$:

::::: in this case, it is the point of $P$ with the lowest y coordinate.)

::::: $q\_\{i,k\}\; :=\; JARVIS\backslash \_BINARY\backslash \_SEARCH(p\_\{i-1\},\; p\_i,\; C\_k)$

:::: (Choose the point $z\; \backslash in\; \backslash \{\; q\_\{i,1\},\; q\_\{i,2\},\; \backslash dots,\; q\_\{i,K\}\; \backslash \}$ which maximizes the angle $\backslash measuredangle\; p\_\{i-1\}p\_iz$ {{why|date=March 2018}} to be the next point on the convex hull of $P$.)

:::: $p\_\{i+1\}\; :=\; JARVIS\backslash \_NEXT\backslash \_CH\backslash \_POINT(p\_\{i-1\},\; p\_i,\; (q\_\{i,1\},\; q\_\{i,2\},\; \backslash dots,\; q\_\{i,K\}))$

:::: (Jarvis march terminates when the next selected point on the convext hull, $p\_\{i+1\}$, is the initial point, $p\_\{1\}$.)

::::if $p\_\{i+1\}\; ==\; p\_1$

::::: (Return the convex hull of $P$ which contains $i\; =\; h$ points.)

::::: (Note: of course, no need to return $p\_\{i+1\}$ which is equal to $p\_\{1\}$.)

::::: return $C\; :=\; (p\_1,\; p\_2,\; \backslash dots,\; p\_\{i\})$

::::else

:::::$ADD(C,\; p\_\{i+1\})$

::: (If after $m$ iterations a point $p\_\{i+1\}$ has not been found so that $p\_\{i+1\}\; ==\; p\_1$, then .)

::: (We need to start over with a higher value for $m$.)

Chan's paper contains several suggestions that may improve the practical performance of the algorithm, for example:

• When computing the convex hulls of the subsets, eliminate the points that are not in the convex hull from consideration in subsequent executions.
• The convex hulls of larger point sets can be obtained by merging previously calculated convex hulls, instead of recomputing from scratch.
• With the above idea, the dominant cost of algorithm lies in the pre-processing, i.e., the computation of the convex hulls of the groups. To reduce this cost, we may consider reusing hulls computed from the previous iteration and merging them as the group size is increased.

Chan's paper contains some other problems whose known algorithms can be made optimal output sensitive using his technique, for example:

• Computing the lower envelope $L(S)$ of a set $S$ of $n$ line segments, which is defined as the lower boundary of the unbounded trapezoid of formed by the intersections.
• Hershberger{{cite journal

| last1=Hershberger | first1=John

| title=Finding the upper envelope of n line segments in O(n log n) time

| journal=Information Processing Letters

| volume=33

| issue=4

| pages=169–174

| date=1989

| doi=10.1016/0020-0190(89)90136-1}} gave an $O(n\backslash log\; n)$ algorithm which can be sped up to $O(n\backslash log\; h)$, where h is the number of edges in the envelope

• Constructing output sensitive algorithms for higher dimensional convex hulls. With the use of grouping points and using efficient data structures, $O(n\backslash log\; h)$ complexity can be achieved provided h is of polynomial order in $n$.

• Convex hull algorithms

{{reflist}}

Category:Convex hull algorithms