Chan's algorithm

Chan's algorithm (engl .: Chan's algorithm ) is in the computational geometry an output sensitive paradigm for calculating the convex hull of a set of points of the Euclidean plane or space. In a divide-and-conquer approach, it combines various well-known algorithms in order to achieve an asymptotically optimal runtime. The algorithm is named after Timothy M. Chan, at the same time and independently of him, Frank Nielsen developed the same method in his dissertation .

Problem

Given a set of points in the Euclidean plane, the convex hull has to be calculated. Here the envelope is identified with the corner points of its edge , with this settlement then applies . Usually one describes the thickness of the envelope with , so it is . Various solutions are known for the problem of the convex hull. These always fall into one of two categories: In the case of output-sensitive algorithms, both the input and the output variable influence the running time; In the case of the non-output-sensitive algorithms, on the other hand, the runtime depends exclusively on the input size. A well-known example of an output-sensitive method is Jarvis' March , which runs in time ; the best-known non-output-sensitive algorithm is Graham's scan with runtime (see also Landau notation ). ${\displaystyle S\subset E^{2}}$ ${\displaystyle n}$ ${\displaystyle \operatorname {conv} (S)}$ ${\displaystyle \operatorname {conv} (S)\subseteq S}$ ${\displaystyle |\operatorname {conv} (S)|}$ ${\displaystyle h}$ ${\displaystyle h\leq n}$ ${\displaystyle O(nh)}$ ${\displaystyle O(n\log n)}$

Ideally, one would like to choose an output-sensitive solution for instances with a small envelope, while one would rather prefer a non-output-sensitive algorithm for inputs with many points on the envelope. However, the magnitude of the output is usually unknown. In addition, in the output-sensitive case, a lower term limit can be proven, which is still well below the term of Jarvis' March. Chan's algorithm now specifies a common method for all inputs that also achieves the optimal runtime of . ${\displaystyle \Omega (n\log h)}$ ${\displaystyle O(n\log h)}$

algorithm

The way Chan's algorithm works is based on the following observation: If the convex hull of a set is to be determined by Jarvis' March, a further point is always searched for, starting from an already known point of the convex hull , so that it is on the far left of the line . Usually this requires computing time in . But if it is already known, the effort is reduced by binary search to . The definition from the left refers to the orientation of the Euclidean plane and must be adapted accordingly in the three-dimensional case. ${\displaystyle P\subset E^{2}}$ ${\displaystyle p_{i}}$ ${\displaystyle p_{i+1}\in P}$ ${\displaystyle P}$ ${\displaystyle {\overline {p_{i}\,p_{i+1}}}}$ ${\displaystyle O(|P|)}$ ${\displaystyle \operatorname {conv} (P)}$ ${\displaystyle O(\log |P|)}$

This results in the following calculation rule:

Let there be a natural number . ${\displaystyle m\leq n}$

1. Divide into (approx.) Subsets with a maximum of points each . ${\displaystyle S}$ ${\displaystyle n/m}$ ${\displaystyle S_{j}}$ ${\displaystyle m}$
2. For each of the quantities calculate via Graham's scan. ${\displaystyle S_{j}}$ ${\displaystyle \operatorname {conv} (S_{j})}$
3. Set partial solutions via Jarvis' March of the following: As long as valid, ${\displaystyle i\leq m}$
   1. determine a candidate for the current point of the convex hull and each subset such that it lies completely to the left of the segment ; ${\displaystyle s_{i}}$ ${\displaystyle S_{j}}$ ${\displaystyle s_{i+1,j}}$ ${\displaystyle S_{j}}$ ${\displaystyle {\overline {s_{i}\,s_{i+1,j}}}}$
   2. determine a point from the candidates so that the set lies completely to the left of the line . ${\displaystyle s_{i+1}}$ ${\displaystyle \{s_{i+1,j}\mid 1\leq j\leq n/m\}}$ ${\displaystyle {\overline {s_{i}\,s_{i+1}}}}$

For are obtained by this calculation, the entire convex hull of the original amount , otherwise the algorithm stops too early. It is crucial that the occurrence of this case can be detected without knowing. The calculation in step 3 only returns to the fixed starting point if the entire envelope has been found. ${\displaystyle m\geq h}$ ${\displaystyle S}$ ${\displaystyle h}$ ${\displaystyle s_{1}}$

A preliminary runtime analysis can now be carried out as a function of . As a non-output-sensitive algorithm, Graham's scan needs in the 2nd step for each of the time in , so in total . Since the convex hulls of the subsets are already available, the calculation of all candidates is accelerated in step 3.1 to a total . Step 3.2 even only takes linear time in and is therefore asymptotically negligible. Both partial steps are carried out each time, so there is also a runtime for the 3rd step in . Overall, the calculation therefore takes time . ${\displaystyle m}$ ${\displaystyle S_{j}}$ ${\displaystyle O(m\log m)}$ ${\displaystyle n/m\cdot O(m\log m)=O(n\log m)}$ ${\displaystyle O((n/m)\log m)}$ ${\displaystyle n/m}$ ${\displaystyle m}$ ${\displaystyle O(n\log m)}$ ${\displaystyle O(n\log m)}$

If you could now simply set, you would get an optimal algorithm, but as mentioned at the beginning, the size of the output is unknown. This problem can be countered by iterative runs with ever larger values ​​for . As soon as the first time has been selected, the calculation can be ended. The speed of the increase is relevant for the total running time, you do not want too many iterations (by increasing too slowly) or too long iterations (by increasing too quickly). Chan's algorithm starts with a constant value for and squares it in each run. Accordingly, only (approximately) many iterations are required before the output size exceeds the first time. For the final term this now results ${\displaystyle m=h}$ ${\displaystyle m}$ ${\displaystyle m\geq h}$ ${\displaystyle m}$ ${\displaystyle \log \log h}$ ${\displaystyle m}$

${\displaystyle \sum _{t=1}^{\log \log h}O(n\log 2^{2^{t}})=O(n)\cdot \sum _{t=1}^{\log \log h}O(2^{t})=O(n\cdot 2^{\log \log h})=O(n\log h)}$,

as required.

Individual evidence

1. ↑ TM Chan: Optimal output-sensitive convex hull algorithms in two and three dimensions . In: Discrete & Computational Geometry . 16, No. 4, 1996, pp. 361-368.
2. ^ F. Nielsen: Algorithmes géométriques adaptatifs . Dissertation (French), Université de Nice Sophia-Antipolis, 1996.
3. ^ F. Nielsen: Grouping and Querying: A Paradigm to Get Output-Sensitive Algorithms . In: Discrete and Computational Geometry Japanese Conference (JCDCG'98) . Revised Papers. (=  Lecture Notes in Computer Science ). tape 1763 . Springer, Berlin, Heidelberg 2000, pp. 250-257 .
4. ↑ D. Kirkpatrick, R. Seidel: The Ultimate Planar Convex Hull Algorithm? . In: SIAM J. Comput. . 15, No. 1, 1983, pp. 287-299.