科研之友
微信
新浪微博
Facebook
分享链接
摘要
Give a triangulation of a set of points on the plane, dilation of any two points is defined as the ratio between the length of the shortest path of these points and their Euclidean distance. Minimum dilation triangulation is a triangulation in which the maximum dilation between any pair of the points is minimized. We give upper bounds on the dilation of the minimum dilation triangulation for two kinds of point sets: An upper bound of n sin(pi/n)/2 for a centrally symmetric convex point set containing n points, and an upper bound of 1.19098 for a set of points on the boundary of a semicircle.
- 出版日期2018-5
