Minimum partition of polygonal regions into trapezoids
Authors:
- Tetsuo AsanoTATetsuo Asano
- Takao AsanoTATakao Asano
- 1 November 1983
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 233-241
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.Keywords
This publication has 8 references indexed in Scilit:
- The NP-completeness column: An ongoing guideJournal of Algorithms, 1982
- Planar Formulae and Their UsesSIAM Journal on Computing, 1982
- The power of non-rectilinear holes1982
- Algorithms for some intersection graphs1981
- Electron-beam exposure system AMDESComputer-Aided Design, 1979
- Intersection graphs of curves in the planeJournal of Combinatorial Theory, Series B, 1976
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite GraphsSIAM Journal on Computing, 1973
- Algorithms for a maximum clique and a maximum independent set of a circle graphNetworks, 1973