Quadrilaterizing an Orthogonal Polygon in Parallel

✍ Scribed by Jana Dietel; Hans-Dietrich Hecker

• Publisher: John Wiley and Sons
• Year: 1998
• Tongue: English
• Weight: 1000 KB
• Volume: 44
• Category: Article
• ISSN: 0044-3050
• DOI: 10.1002/malq.19980440104

✦ Synopsis

We consider the problem of quadrilaterizing an orthogonal polygon P , that is t o 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(1ogN) time using O(N/log N ) processors if the rectangle decomposition of P is given, and O ( N ) processors if not. Furthermore we will show that the latter result is optimal if the polygon is allowed t o contain holes.