Quadrilaterizing an Orthogonal Polygon in Parallel

Abstract We consider the problem of quadrilaterizing an orthogonal polygon P, that is to decompose P into nonoverlapping convex quadrangles without adding new vertices. In this paper we present a CREW‐algorithm for this problem which runs in O(log N) time using Θ(N/log N) processors if the rectangle decomposition of P is given, and Θ(N) processors if not. Furthermore we will show that the latter r…