Angle-monotonicity of theta-graphs for points in convex position

Document Type : Article

Authors

1 Department of Computer Science, University of Bojnord, Bojnord, Iran

2 Combinatorial and Geometric Algorithms Lab., Department of Computer Science, Yazd University, Yazd, P.O. Box 89195-741, Iran

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

Main Subjects

References

References:
1. Narasimhan, G. and Smid, M., Geometric Spanner Networks, Cambridge University Press (2007).
2. Bakhshesh, D. and Farshi, M. "A lower bound on the stretch factor of Yao graph Y4", Scientia Iranica, 29(6), pp. 3244-3248 (2022).
3. Abam, M.A. and Seraji, M.J.R. "Geodesic spanners for points in R3 amid axis-parallel boxes", Inform Process Lett., 166, 106063 (2021).
4. Abam, M.A. and Borouny, M.S. "Local geometric spanners", Algorithmica, 83, pp. 3629-3648 (2021).
5. Akitaya, H.A., Biniaz, A., and Bose, P. "On the spanning and routing ratios of the directed 6-graph", Comp. Geom-Theor. App., 105(106), 101881 (2022).
6. De Carufel, J.L., Bose, P., Paradis, F., et al. "Local routing in WSPD-based spanners", Journal of Computational Geometry, 12, pp. 1-34 (2021).
7. van Renssen, A. and Wong, G. "Bounded-degree spanners in the presence of polygonal obstacle", Theor. Comput. Sci., 854, pp. 159-173 (2021).
8. Bakhshesh, D. and Farshi, M. "(Weakly) selfapproaching geometric graphs and spanners", Comp. Geom-Theor. App., 78, pp. 20-36 (2019).
9. Bakhshesh, D. and Farshi, M. "A degree 3 plane 5:19-spanner for points in convex position", Scientia Iranica, 28, pp. 3324-3331 (2021).
10. Iranfar, B. and Farshi, M. "On the expected weight of the theta graph on uncertain points", Journal of Algorithms and Computation, 52(1), pp. 163-174 (2020).
11. Dehkordi, H.R., Frati, F., and Gudmundsson, J. "Increasing-chord graphs on point sets", Journal of Graph Algorithms and Applications, 19(2), pp. 761- 778 (2015).
12. Bonichon, N., Bose, P., Carmi, P., et al. "Gabriel triangulations and angle-monotone graphs: Local routing and recognition", In Proceedings of the 24th International Symposium on Graph drawing (GD 2016), pp. 519-531 (2016).
13. Lubiw, A. and Mondal, D. "Construction and local routing for angle-monotone graphs", Journal of Graph Algorithms and Applications, 23(2), pp. 345- 369 (2019).
14. Bakhshesh, D. and Farshi, M. "Angle-monotonicity of Delaunay  triangulation", Comp. Geom-Theor. App., 94(10), 1711 (2021).
15. Bakhshesh, D. and Farshi, M. "On the plane angle-monotone graphs", Comp. Geom-Theor. App., 100(10), 1818 (2022).
16. Clarkson, K. "Approximation algorithms for shortest path motion planning", In Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, STOC'87, pp. 56-65, New York, NY, USA,. ACM (1987).
17. Keil, J.M., Approximating the Complete Euclidean Graph, R. Karlsson and A. Lingas, Editors, SWAT 88, pp. 208-213, Berlin, Heidelberg (1988).
18. Bose, P., D. Carufel, J.-L., Morin, P., et al. "Towards tight bounds on theta-graphs: More is not always better", Theor. Comput. Sci., 616, pp. 70-93 (2016).
Scientia Iranica
Volume 30, Issue 6
Transactions on Computer Science & Engineering and Electrical Engineering (D)
November and December 2023
Pages 2116-2123

Files

History

  • Receive Date: 26 August 2022
  • Revise Date: 18 May 2023
  • Accept Date: 17 July 2023

Share

How to cite

Statistics