On Some Distance Problems in Fixed Orientations
On Some Distance Problems in Fixed Orientations
复制标题
关于固定方向上的一些距离问题
DOI：
10.1137/0216049
复制
发表时间：
1987
期刊：
影响因子：
--
通讯作者：
Chak
中科院分区：
文献类型：
--
作者：
P. Widmayer;Ying;Chak
在VLSI设计中，技术要求通常只使用两个正交方向，既确定对象的形状，又确定用于布线对象的距离函数，即$L_1$公制。最新的VLSI制造技术能够在垂直方向和对角方向上产生边和导线。我们将距离概念推广到允许任何固定方向集合的情况，并引入了一族自然诱导的度量以及随后的几何概念的推广。在这种情况下，两点之间的最短连接是由仅具有给定方向的线段组成的路径。在这种情况下，我们得到了各种基本平面距离问题的最优解，如Voronoi图、最小生成树和两个凸多边形之间的(最小和最大)距离的计算。许多其他理论上有趣和实际相关的问题仍有待解决。尤其是这个新的家庭。
In VLSI design, technology requirements often dictate the use of only two orthogonal orientations, determining both the shape of objects and the distance function, the $L_1 $-metric, to be used for wiring objects. More recent VLSI fabrication technology is capable of creating edges and wires in both the orthogonal and diagonal orientations.We generalize the distance concept to the case where any fixed set of orientations is allowed, and introduce a family of naturally induced metrics, and the subsequent generalization of geometrical concepts. A shortest connection between two points is in this case a path composed of line segments with only the given orientations. We derive optimal solutions for various basic planar distance problems in this setting, such as the computation of a Voronoi diagram, a minimum spanning tree, and the (minimum and maximum) distance between two convex polygons. Many other theoretically interesting and practically relevant problems remain to be solved. In particular, the new famil...