in vlsi artwork processing systems, it is often required to partition a polygonal region into the minimum number of trapezoids, with two horizontal sides. a triangle with a horizontal side is considered to be a trapezoid with two horizontal sides one of which is degenerate. for a hole-free polygon with formula_1 sides, a smallest such partition can be found in time formula_5.