>
Fa   |   Ar   |   En
   angle-monotonicity of theta-graphs for points in convex position  
   
نویسنده bakhshesh d. ,farshi m.
منبع scientia iranica - 2023 - دوره : 30 - شماره : 6-D - صفحه:2116 -2123
چکیده    For for 0 < < 180+-,+, a geometric path p = (p1; : : : ; pn) is called angle-monotone with width from p1 to pn if there exists a closed wedge of angle such that every directed edge pipi+ of p lies inside the wedge whose apex is pi. a geometric graph g is called angle-monotone with width if for any two vertices p and q in g, there exists an anglemonotone path with width from p to q. in this paper, we show that for any integer k  1 and any i 2 f2; 3; 4; 5g, the theta-graph 4k+i on a set of points in convex position is anglemonotone with width 90 + i+ 4 , where + = 360+ 4k+i . moreover, we present two sets of points in the plane, one in convex position and the other in non-convex position, to show that for every 0 < < 180+, the graph 4 is not angle-monotone with width . furthermore, we improve the stretch factor of graphs 4;5;7;9;11; y4, and y5, when the points are in convex position. finally, we provide a lower bound of 3.66 for y4 that solves an open problem.
کلیدواژه angle-monotone path ,theta-graph ,stretch factor ,convex position
آدرس university of bojnord, department of computer science, iran, yazd university, combinatorial and geometric algorithms lab., department of computer science, iran
پست الکترونیکی mfarshi@yazd.ac.ir
 
     
   
Authors
  
 
 

Copyright 2023
Islamic World Science Citation Center
All Rights Reserved