Minimum partition of polygonal regions into trapezoids

This paper shows the problem of partitioning a polygonal region into a minimum number of trapezoids with two horizontal sides to be NP-complete, and presents an O(n log n) natural approximation algorithm which uses only horizontal chords to partition a polyagonal region P into trapezoid, where n is the number of vertices of P.

Abstract

We consider the problem of partitioning a polygonal region into a minimum number of trapezoids with two horizontal sides. Triangles with a horizontal side are considered to be trapezoids with two horizontal sides one of which is degenerate. In this paper we show that this problem is equivalent to the problem of finding a maximum independent set of a straight-lines-in-the-plane graph. Thus it is shown to be NP-complete. Next we present an O(n log n) natural approximation algorithm which uses only horizontal chords to partition a polygonal region P into trapezoids, where n is the number of vertices of P. We show that the absolute performance ratio of the algorithm is three. We can also design another approximation algorithm with the ratio (1 + 2/c) if we have a (1 - 1/c) approximation algorithm for the maximum independent set problem on straight-lines-in-the-plane graphs, where c is some constant. Finally, we give an O(n3) exact algorithm for polygonal regions without windows.