Space-efficient algorithms for triangulating a set of points in a plane

In this thesis we study some algorithms for the point set triangulation, that take only O(s) extra storage cells as work-space for any 1<s. We develop an optimal serial algorithm which takes O(n(n/s+log s)) time, and a parallel algorithm which takes O((n^2*log s)/(s*p)), where p is the number of processors available. The parallel algorithm works on our memory-constrained parallel computational model, which is based on the CREW PRAM model