|
|
a degree 3 plane 5.19-spanner for points in convex position
|
|
|
|
|
نویسنده
|
bakhshesh d. ,farshi m.
|
منبع
|
scientia iranica - 2021 - دوره : 28 - شماره : 6-D - صفحه:3324 -3331
|
چکیده
|
Let s be a set of n points in the plane that is in convex position. using the well-known path-greedy spanner algorithm, this study presents an algorithm that constructs a plane 3+4π/ 3 -spanner g of degree 3 on the point set s. recently, biniaz et al. [biniaz, a., bose, p., de carufel, j.-l., gavoille, c., maheshwari, a., and smid, m. towards plane spanners of degree 3, journal of computational geometry, 8(1), pp. 11{31 (2017).] proposed an algorithm that constructs a degree 3 plane 3+4π/ 3 -spanner g0 for s. it was found that there was no upper bound with a constant factor in the total weight of g0, but the total weight of g was asymptotically equal to that of the minimum spanning tree of s.
|
کلیدواژه
|
plane spanner; stretch factor; greedy spanner; minimum spanning tree; traveling salesperson tour
|
آدرس
|
university of bojnord, department of computer science, iran, yazd university, department of mathematical sciences, combinatorial and geometric algorithms lab., iran
|
پست الکترونیکی
|
mfarshi@yazd.ac.ir
|
|
|
|
|
|
|
|
|
|
|
|
Authors
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|