Parallel computational geometry algorithms

This page contains a collection of parallel computational geometry algorithm. It includes a brief description of each algorithm along with the NESL code. These algorithms have been developed by the Scandal project.

If you have arrived here via a search engine, we suggest going to the toplevel algorithms page.

Quickhull

This is a parallel version of Quickhull. Quickhull is a divide and conquer algorithm for finding a convex hull and has an expected complexity of O(n log n) work and O(log n) depth.

Kirkpatric and Seidel Convex Hull

This is the algorithm from the Kirkpatrick and Seidel paper "The Ultimate Planar Convex Hull Algorithm?". For f points in the result it does O(n log f) work and has O(log^2 n log f) depth.

function pick_pairs(S) =
let
    n2 = #S/2;
    remain = drop(S,2*n2);
    E = S->[0:n2*2:2];
    O = S->[1:n2*2:2];
    pairs = {if x_0 < x_1 then (x_0,y_0),(x_1,y_1) 
             else (x_1,y_1),(x_0,y_0)
	     : (x_0,y_0) in E ; (x_1,y_1) in O 
	     | x_0 /= x_1};
    remain = {if y_0 < y_1 then (x_1,y_1) else (x_0,y_0)
	      : (x_0,y_0) in E ; (x_1,y_1) in O 
	      | x_0 == x_1} ++ remain;
in remain,pairs $

function slope((x0,y0),(x1,y1)) = (y1-y0)/(x1-x0) $

function bridge(S,a) =
let remain,pairs = pick_pairs(S)
in if #S == 2 then pairs[0]
   else let
       K = median({slope(p_i,p_j): (p_i,p_j) in pairs});
       p_k,p_m = supporting_points(K,S);
   in
       if first(p_k)<=a and first(p_m)>a then p_k,p_m
       else 
	   let
	       S_n = if first(p_k) <= a 
	             then flatten({if slope(p_i,p_j) >= K
	                           then [p_j] else [p_i,p_j]
				   : (p_i,p_j) in pairs})
                     else flatten({if slope(p_i,p_j) <= K
                                   then [p_i] else [p_i,p_j]
				   :  (p_i,p_j) in pairs})
	in bridge(S_n++remain,a) $

function kirkpatrick_seidel_upper_hull(S) =
let x = {x : (x,y) in S};
    p_min = S[min_index(x)];
    p_max = S[max_index(x)];
in connect(p_min,p_max,S) $

points = [(3.,3.),(2.,7.),(0.,0.),(8.,5.),
          (4.,6.),(5.,3.),(9.,6.),(10.,0.)];

kirkpatrick_seidel_upper_hull(points);