论文标题
正交解剖分为几个矩形
Orthogonal dissection into few rectangles
论文作者
论文摘要
我们描述了一种多项式时间算法，该算法将其作为具有轴平行侧但非理性顶点坐标的多边形输入，并输出一组尽可能少的矩形可以通过轴平行的切割和翻译来剖析的矩形。矩形的数量是多边形的DEHN不变的等级。同样的方法也可以用来将轴平行的多边形剖分为简单的多边形，而边缘数量最小。当允许旋转或反射时，我们可以将最小矩形数量近似于两个倍。
We describe a polynomial time algorithm that takes as input a polygon with axis-parallel sides but irrational vertex coordinates, and outputs a set of as few rectangles as possible into which it can be dissected by axis-parallel cuts and translations. The number of rectangles is the rank of the Dehn invariant of the polygon. The same method can also be used to dissect an axis-parallel polygon into a simple polygon with the minimum possible number of edges. When rotations or reflections are allowed, we can approximate the minimum number of rectangles to within a factor of two.
