Chan's algorithm

<p>In <a href="/facts/Computational_geometry/eeaotQtl">computational geometry</a>, Chan's algorithm, named after <a href="/facts/Timothy_M._Chan/6fax6RRM">Timothy M. Chan</a>, is an optimal <a href="/facts/Output-sensitive_algorithm/5vAv585y">output-sensitive algorithm</a> to compute the <a href="/facts/Convex_hull/D4Id3JDS">convex hull</a> of a set 
  
    
      
        P
      
    
    {\displaystyle P}
  
 of 
  
    
      
        n
      
    
    {\displaystyle n}
  
 points, in 2- or 3-dimensional space. 
The algorithm takes 
  
    
      
        O
        (
        n
        log
        ⁡
        h
        )
      
    
    {\displaystyle O(n\log h)}
  
 time, where 
  
    
      
        h
      
    
    {\displaystyle h}
  
 is the number of vertices of the output (the convex hull). In the planar case, the algorithm combines an 
  
    
      
        O
        (
        n
        log
        ⁡
        n
        )
      
    
    {\displaystyle O(n\log n)}
  
 algorithm (<a href="/facts/Graham_scan/WmFuJzEg">Graham scan</a>, for example) with <a href="/facts/Jarvis_march/4V8z8eHC">Jarvis march</a> (
  
    
      
        O
        (
        n
        h
        )
      
    
    {\displaystyle O(nh)}
  
), in order to obtain an optimal 
  
    
      
        O
        (
        n
        log
        ⁡
        h
        )
      
    
    {\displaystyle O(n\log h)}
  
 time. Chan's algorithm is notable because it is much simpler than the <a href="/facts/Kirkpatrick%E2%80%93Seidel_algorithm/h2E4vCMN">Kirkpatrick–Seidel algorithm</a>, and it naturally extends to 3-dimensional space. This paradigm has been independently developed by Frank Nielsen in his Ph.D. thesis.
</p>

Chan's algorithm open-in-new

Chan's algorithm