斯坦纳点/树、泰森多边形 |
您所在的位置:网站首页 › 托尔拆利 › 斯坦纳点/树、泰森多边形 |
斯坦纳点
斯坦纳点别名正等角中心、费尔马点、斯坦纳点 在三角形的三边各向其外侧作等边三角形,这三个等边三角形的外接圆交于一点T,该点T即称为托里拆利点(Torricelli’s point ),而三个等边三角形的外接圆称为托里拆利圆。在一定条件下,托里拆利点和正等角中心、费尔马点等是一回事。托里拆利点是由意大利物理学家托里拆利发现的。该问题是费马(1601-1665)作为“求一点,使它至一三角形三顶点的距离和最小"这一著名的极值问题而向意大利物理学家托里拆利(1608-1647)提出,并为托里拆利所解决的,当三角形内角均小于120°时点K即为所求,故称K为托里拆利点,也称费马点。以后,德国斯太纳((1796-1863)独立提出并推广了它,故又称斯太纳问题。 斯坦纳树问题是组合优化问题,与最小生成树相似,是最短网络的一种。最小生成树是在给定的点集和边中寻求最短网络使所有点连通。而最小斯坦纳树允许在给定点外增加额外的点,使生成的最短网络开销最小。 斯坦纳树问题的定义随着历史的发展在不断的扩展和推广: 瑞士数学家斯坦纳(J.Steiner,1796—1863)将问题推广成:在平面上求一点,使得这一点到平面 上给定的若干个点(称为所与点)的距离之和最小。这可以看作斯坦纳树问题的雏形。考虑到点的其他相关因素,加入了权重的表示。形成的推广定义,德国的两位数学家韦伯(H.Weber,1842—1913)和维斯菲尔德(E.Wieszfeld)分别在1909年和1937年将该问题作为工 厂选址问题提出来:某地有给定的若干个仓库,每个仓库的其他相关因素可以换算成一个权重表示,求一建造工厂的合适地点,使工厂到每个仓库的距离与权重乘积 的总和最小,则这个工厂的地址是最经济、便利的。库朗(R.Courant)和罗宾斯(H.Robbins)提出第一个定义中,斯坦纳对此问题的推广是一种平庸的推广。要得到一个有意义的推广,需要考虑的不是引进一个点,而应是引进若干个点,使引进的点与原来给定的点 连成的网络最小。他们将此新问题称为斯坦纳树问题。给出的定义为: 假设原来已经给定了n个点,库朗等指出需要引进的点数至多为n-2,此种点称为斯坦纳点。过每一斯坦纳点,至多有三条边通过。若为三条边,则它们两两交成 120°角;若为两条边,则此斯坦纳点必为某一已给定的点,且此两条边交成的角必大于或等于120°。其中最小的网络称为已给定点的集合的最小斯坦纳树, 记作SMT。若此SMT的斯坦纳点中有等于给定点的点,则称此SMT为退化的,此给定点称为退化点。 Steiner’s minimal treeSteiner’s minimal tree problem is this: Find the shortest possible network interconnecting a set of points in the Euclidean plane. If the points are linked directly to each other by straight line segments, we obtain the minimal spanning tree. But Steiner’s problem allows for additional points – now called Steiner points – to be added to the network, yielding Steiner’s minimal tree. This generally results in a reduction of the overall length of the network. Euclidean Steiner treeThe original problem was stated in the form that has become known as the Euclidean Steiner tree problem or geometric Steiner tree problem: Given N points in the plane, the goal is to connect them by lines of minimum total length in such a way that any two points may be interconnected by line segments either directly or via other points and line segments. It may be shown that the connecting line segments do not intersect each other except at the endpoints and form a tree, hence the name of the problem. Rectilinear Steiner treeThe rectilinear Steiner tree problem is a variant of the geometric Steiner tree problem in the plane, in which the Euclidean distance is replaced with the rectilinear distance. The problem arises in the physical design of electronic design automation. In VLSI circuits, wire routing is carried out by wires that are often constrained by design rules to run only in vertical and horizontal directions, so the rectilinear Steiner tree problem can be used to model the routing of nets with more than two terminals. Steiner ratioThe Steiner ratio is the supremum of the ratio of the total length of the minimum spanning tree to the minimum Steiner tree for a set of points in the Euclidean plane. 泰森多边形荷兰气候学家A·H·Thiessen提出了一种根据离散分布的气象站的降雨量来计算平均降雨量的方法,即将所有相邻气象站连成三角形,作这些三角形各边的垂直平分线,于是每个气象站周围的若干垂直平分线便围成一个多边形。用这个多边形内所包含的一个唯一气象站的降雨强度来表示这个多边形区域内的降雨强度,并称这个多边形为泰森多边形。 如图1,其中虚线构成的多边形就是泰森多边形。泰森多边形每个顶点是每个三角形的外接圆圆心。泰森多边形也称为Voronoi图,或dirichlet图。 Delaunay三角网的构建也称为不规则三角网的构建,就是由离散数据点构建三角网,如图2,即确定哪三个数据点构成一个三角形,也称为自动联接三角网。即对于平面上n个离散点,其平面坐标为(xi,yi),i=1,2,…,n,将其中相近的三点构成最佳三角形,使每个离散点都成为三角形的顶点。 https://blog.csdn.net/gdut2015go/article/details/48208983 https://desktop.arcgis.com/zh-cn/arcmap/10.3/tools/coverage-toolbox/how-thiessen-works.htm |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |