@InProceedings{LPRS82,
  author = 	 { Andrzej Lingas and Ron Y. Pinter and Ronald L. Rivest and Adi Shamir },
  title = 	 { Minimum Edge-Length Partitioning of Rectilinear Polygons },
  pages = 	 { 53--63 },
  booktitle =    { Proceedings 20th Annual Allerton Conference on Communication,
                   Control, and Computing },
  date =         { 1982-10 },                  
  editor = 	 { H. V. Poor and W. K. Jenkins },
  publisher =    { University of Illinois (Urbana, Illinois), Department of Electrical
                   Engineering and Coordinated Science Laboratory },
  OPTyear = 	 { 1982 },
  OPTmonth = 	 { October },
  eventdate =    { 1982-10-06/1982-10-08 },
  eventtitle =   { Allerton '82 },
  venue =        { Monticello, Illinois },                  
  abstract =     {
        We consider the problem of partitioning a rectilinear polygon
        into disjoint rectangles using the minimum amount of ``ink''.
        The given polygonal figure may or may not have holes in it,
        and the complexity of the problem is shown to depend on this very
        fact: For hole-free figures, we provide a polynomial-time algorithm,
        whereas for figures containing holes the problem is shown to be
        NP-complete.
        \par
        For the hole-free case, the time complexity of the partitioning
        algorithm is $O(n^4)$ for arbitrary rectilinear shapes, but for
        nontrivial special cases the complexity can be reduced to $O(n^3)$.
        In the general case it turns out that even degenerate holes, i.e.
        points through which the decomposing edges have to go, are enough
        to render the problem intractable.
        \par
        More interestingly, the proof techniques for the NP-completeness
        results can be applied to an even more general case, namely where
        the polygons are no longer rectilinear and a partitioning into
        convex polygons with minimum edge length is sought.                  
                },
}