CLOTH MEASURE - A SOFTWARE TOOL FOR ESTIMATING THE MEMORY REQUIREMENTS OF CORNER STITCHING DATA-STRUCTURES

In a previous paper [1], we derived formulae for estimating the storag e requirements of the Rectangular and L-shaped Corner Stitching data s tructures [2, 3] for a given layout. These formulae require the comput ation of quantities called violations, which are geometric properties of the layout. In this paper, we present optimal Theta(n log n) algori thms for computing violations, where n is the number of rectangles in the layout. These algorithms are incorporated into a software tool cal led CLOTH MEASURE. Experiments conducted with CLOTH MEASURE show that it is a viable tool for estimating the memory requirements of a layout without having to implement the corner stitching data structures, whi ch is a tedious and time-consuming task.