Kirkpatrick–Seidel algorithm

<p>The Kirkpatrick–Seidel algorithm, proposed by its authors as a potential "ultimate planar convex hull algorithm", is an <a href="/facts/Algorithm/fnl5NmRt">algorithm</a> for computing the <a href="/facts/Convex_hull/D4Id3JDS">convex hull</a> of a set of points in the plane, with 
  
    
      
        
          
            O
          
        
        (
        n
        log
        ⁡
        h
        )
      
    
    {\displaystyle {\mathcal {O}}(n\log h)}
  
 <a href="/facts/Analysis_of_algorithms/pStoBgBn">time complexity</a>, where 
  
    
      
        n
      
    
    {\displaystyle n}
  
 is the number of input points and 
  
    
      
        h
      
    
    {\displaystyle h}
  
 is the number of points (non dominated or maximal points, as called in some texts) in the hull. Thus, the algorithm is <a href="/facts/Output-sensitive_algorithm/5vAv585y">output-sensitive</a>: its running time depends on both the input size and the output size. Another output-sensitive algorithm, the <a href="/facts/Gift_wrapping_algorithm/4V8z8eHC">gift wrapping algorithm</a>, was known much earlier, but the Kirkpatrick–Seidel algorithm has an asymptotic running time that is significantly smaller and that always improves on the 
  
    
      
        
          
            O
          
        
        (
        n
        log
        ⁡
        n
        )
      
    
    {\displaystyle {\mathcal {O}}(n\log n)}
  
 bounds of non-output-sensitive algorithms. The Kirkpatrick–Seidel algorithm is named after its inventors, <a href="/facts/David_G._Kirkpatrick/2qE9tdxA">David G. Kirkpatrick</a> and <a href="/facts/Raimund_Seidel/u4XMgNom">Raimund Seidel</a>.
</p><p>Although the algorithm is asymptotically optimal, it is not very practical for moderate-sized problems.
</p>

Kirkpatrick–Seidel algorithm open-in-new

Kirkpatrick–Seidel algorithm