Angle-monotonicity of theta-graphs for points in convex position
Author(s):
Article Type:
Research/Original Article (دارای رتبه معتبر)
Abstract:
For $0<\gamma<180^{\circ}$, a geometric path $P=(p_1,\ldots, p_n)$ is called angle-monotone with width $\gamma$ from $p_1$ to $p_n$ if there exists a closed wedge of angle $\gamma$ such that every directed edge $\overrightarrow{p_ip_{i+1}}$ of~$P$ lies inside the wedge whose apex is $p_i$. A geometric graph $G$ is called angle-monotone with width $\gamma$ if for any two vertices $p$ and $q$ in $G$, there exists an angle-monotone path with width $\gamma$ from $p$ to $q$. In this paper, we show that for any integer $k\geq 1$ and any $i\in\{2, 3, 4, 5\}$, the theta-graph $\Theta_{4k+i}$ on a set of points in convex position is angle-monotone with width $90^\circ+\frac{i\theta}{4}$, where $\theta=\frac{360^{\circ}}{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<\gamma<180^\circ$, the graph $\Theta_4$ is not angle-monotone with width $\gamma$.
Keywords:
Language:
English
Published:
Scientia Iranica, Volume:30 Issue: 6, Nov-Dec 2023
Pages:
2116 to 2123
https://www.magiran.com/p2648480
سامانه نویسندگان
مقالات دیگری از این نویسنده (گان)
-
A lower bound on the stretch factor of Yao graph Y4
D. Bakhshesh *, M. Farshi
Scientia Iranica, Nov-Dec 2022 -
A degree 3 plane 5.19-spanner for points in convex position
D. Bakhshesh *, M. Farshi
Scientia Iranica, Nov-Dec 2021