Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6874213 | Information Processing Letters | 2018 | 6 Pages |
Abstract
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 nsinâ¡(Ï/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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Sattar Sattari, Mohammad Izadi,