Paper Info
Title
Upper bounds for minimum dilation triangulation in two special cases.
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.
Year
DOI
Venue
2018
10.1016/j.ipl.2018.01.001
Information Processing Letters
Keywords
Field
DocType
Computational geometry,Triangulation,Dilation,Point set
Discrete mathematics,Combinatorics,Dilation (morphology),Shortest path problem,Upper and lower bounds,Euclidean distance,Regular polygon,Triangulation (social science),Point set,Mathematics
Journal
Volume
ISSN
Citations 
133
0020-0190
0
PageRank 
References 
Authors
0.34
5
2
Name
Order
Citations
PageRank
Sattar Sattari100.68
Mohammad Izadi252.57