Premium
Quadrilaterizing an Orthogonal Polygon in Parallel
Author(s) -
Dietel Jana,
Hecker HansDietrich
Publication year - 1998
Publication title -
mathematical logic quarterly
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.473
H-Index - 28
eISSN - 1521-3870
pISSN - 0942-5616
DOI - 10.1002/malq.19980440104
Subject(s) - rectangle , combinatorics , polygon (computer graphics) , mathematics , regular polygon , convex polygon , polygon covering , rectilinear polygon , decomposition , simple polygon , computer science , geometry , telecommunications , ecology , frame (networking) , biology
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 result is optimal if the polygon is allowed to contain holes.