Partitioning a polygonal region into trapezoidsPartitioning a polygonal region into trapezoids

Access Restriction
Subscribed

 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

Source: ACM Digital Library