Access Restriction

Author Asano, Takao ♦ Asano, Tetsuo ♦ Imai, Hiroshi
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1986
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Abstract The problem of partitioning a polygonal region into a minimum number of trapezoids with two horizontal sides is discussed. A triangle with a horizontal side is considered to be a trapezoid with two horizontal sides one of which is degenerate. First, a method of achieving a minimum partition is presented. The number $\textit{M}*$ of the trapezoids in the minimum partition of a polygonal region $\textit{P}$ is shown to be $\textit{M}*$ = $\textit{n}$ + $\textit{w}$ - $\textit{h}$ - $\textit{d}$ - 1, where $\textit{n},$ $\textit{w},$ and $\textit{h}$ are the number of vertices, windows (holes), and horizontal edges of $\textit{P},$ respectively, and $\textit{d}$ is the cardinality of a maximum independent set of the straight-lines-in-the-plane graph associated with $\textit{P}.$ Next, this problem is shown to be polynomially equivalent to the problem of finding a maximum independent set of a straight-lines-in-the-plane graph, and consequently, it is shown to be NP-complete. However, for a polygonal region without windows, an $\textit{O}(\textit{n}2)-time$ algorithm for partitioning it into a minimum number of trapezoids is presented. Finally, an $\textit{O}(\textit{n}$ log $\textit{n})-time$ approximation algorithm with the performance bound 3 is presented.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1986-04-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 33
Issue Number 2
Page Count 23
Starting Page 290
Ending Page 312

Open content in new tab

   Open content in new tab
Source: ACM Digital Library