Heuristics for minimum decompositions of polygons
Heuristics for minimum decompositions of polygons
复制标题
多边形最小分解的启发式
DOI：
--
复制
发表时间：
1987
期刊：
影响因子：
--
通讯作者：
C. Levcopoulos
中科院分区：
文献类型：
--
作者：
C. Levcopoulos
考虑了多边形的最小分解问题：（1）将多边形分解为最小数目的矩形，（2）通过插入最小总长度的边将多边形划分为矩形，（3）通过插入最大的不相交对角线集将多边形划分为三角形，使得它们的总长度最小.
第一个问题应用于制造集成电路的掩模。严格的上限和下限示出的最大数量的矩形，可能需要覆盖任何多边形。此外，一个快速的启发式，实现这些上限。
第二个问题在VLSI设计中有一个应用，将布线区域划分为通道。提出了几种算法，这些算法在适度的恒定因子内产生最优解。此外，通过采用不寻常的分治方法，一个已知的启发式的时间性能大大降低。
第三个问题在数值分析和构造最优搜索树中有应用。在这里，论文的贡献涉及分析所谓的贪婪三角剖分。改进了贪婪三角剖分长度的上下界。此外，一个线性时间算法计算贪婪三角剖分的一类有趣的多边形。
The following problems of minimally decomposing polygons are considered: (1) decompose a polygon into a minimum number of rectangles, (2) partition a polygon into rectangles by inserting edges of minimum total length and (3) partition a polygon into triangles by inserting a maximal set of non-intersecting diagonals, such that their total length is minimized.
The first problem has an application in fabricating masks for integrated circuits. Tight upper and lower bounds are shown for the maximal number of rectangles which may be required to cover any polygon. Also, a fast heuristic which achieves these upper bounds is presented.
The second problem has an application in VLSI design, in dividing routing regions into channels. Several heuristics are proposed, which produce solutions within moderate constant factors from the optimum. Also, by employing an unusual divide-and-conquer method, the time performance of a known heuristic is substantially reduced.
The third problem has an application in numerical analysis and in constructing optimal search trees. Here, the contribution of the thesis concerns analysis of the so-called greedy triangulation. Previous upper and lower bounds on the length of the greedy triangulation are improved. Also, a linear-time algorithm computing greedy triangulations for an interesting class of polygons is presented.