Abstract
We describe a new parallel polygon-clipping algorithm based on a novel technique that allows a processor to compute output vertices independently of the results of the other processors. The basis for the method is a collision-free labeling scheme to compute the labels of the vertices of the output polygon. This labeling scheme depends only on the id of the vertex in the input polygon. This procedure allows us to defer the synchronization between processors to the final stages of the algorithm, reduces the amount of overhead due to fine-grain synchronization, and helps makes the algorithm efficient.