| dc.creator (作者) | Liou,Wen-Ching;Tan J. J. M.;Lee, R. C. T | en_US |
| dc.creator (作者) | 劉文卿 | - |
| dc.date (日期) | 1990-07 | en_US |
| dc.date.accessioned | 17-Jan-2009 15:59:24 (UTC+8) | - |
| dc.date.available | 17-Jan-2009 15:59:24 (UTC+8) | - |
| dc.date.issued (上傳時間) | 17-Jan-2009 15:59:24 (UTC+8) | - |
| dc.identifier.uri (URI) | https://nccur.lib.nccu.edu.tw/handle/140.119/26982 | - |
| dc.description.abstract (摘要) | An O(n log log n) algorithm is proposed for minimally rectangular partitioning a simple rectilinear polygon. For any simple rectilinear polygon P, a vertex-edge visible pair is a vertex and an edge that can be connected by a horizontal or vertical line segment that lies entirely inside P. It is shown that, if the vertex-edge visible pairs are found, the maximum matching and the maximum independent set of the bipartite graph derived from the chords of a simple rectilinear polygon can be found in linear time without constructing the bipartite graph. Using this algorithm, the minimum partition problem for convex rectilinear polygons and vertically (horizontally) convex rectilinear polygons can be solved in O(n) time | - |
| dc.format | application/ | en_US |
| dc.language | en | en_US |
| dc.language | en-US | en_US |
| dc.language.iso | en_US | - |
| dc.relation (關聯) | IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 9(7), 720-733 | en_US |
| dc.title (題名) | Minimum Rectangular Partition Problem for Simple Rectilinear Polygons | en_US |
| dc.type (資料類型) | article | en |
