>
Fa   |   Ar   |   En
   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
  
 
 

Copyright 2023
Islamic World Science Citation Center
All Rights Reserved