Fast algorithm for polygon decomposition

An O( k log( k )+ n ) algorithm is developed, where n is the number of versions, to decompose rectilinear polygons into rectangles. This algorithm uses horizontal cuts only and reports nonoverlapping rectangles the union of which is the original rectilinear polygon. This algorithm has been programmed in Pascal on an Apollo DN320 workstation. Experimentation with rectilinear polygons from VLSI artwork indicate that the present algorithm is significantly faster than the plane sweep algorithm and the algorithm proposed by K.D. Gourley and D.M. Green (1983)