GPGPU Programming for Games and Science

CPU Computing 15

the set of k-tuples of real numbers is IR

k

, n and d are positive integers, m is

a nonnegative integer (if zero, then Y = C), and C is a discrete space that is

referred to as the combinatorial portion of the output.

A typical example is the problem of computing the convex hull of a finite

set of points in two dimensions. In the definition, d = 2, which is the dimension

of the space containing the points, n is the number of points in the set, and

m = 0. The input points are indexed with integers 1 through n,andC is the

set of all ordered subsets of {1,...,n}. The output of the convex hull algorithm

is an element of C,say,{i

1

,...,i

q

}, which represents the ordered vertices of

the convex polygon that is the convex hull boundary; mathematically ...