An Upper Bound for Min-Max Angle of Polygons

Document Type : Original Scientific Paper

Authors

1 Department of Computer Science, University of Kashan, Kashan, I. R. Iran

2 Department of Mathematics and computer Science, Amirkabir university of Technology, Tehran, I. R. Iran

Abstract

‎Let $S$ be a set of $n$ points in the plane‎, ‎$\nabla(S)$ the set of all simple polygons crossing $S$‎, ‎$\gamma_P$ the maximum angle of polygon $P \in \nabla(S)$ and $\theta =min_{P\in\nabla(S)} \gamma_P$‎. ‎In this paper‎, ‎we prove that $\theta\leq 2\pi-\frac{2\pi}{r.m}$ where $m$ and $r$ are the number of edges and inner points of the convex hull of $S$‎, ‎respectively‎. ‎We also propose an algorithm to construct a polygon with the upper bound on its angles‎. ‎Constructing a simple polygon with the angular constraint on a given set of points in the plane can be used for path planning in robotics‎. ‎Moreover‎, ‎we improve our upper bound on $\theta$ and prove that this is tight for $r=1$‎.

Keywords

Main Subjects

References

[1] S. Marchand-Maillet and Y. M. Sharaiha, Binary Digital Image Processing: A Discrete Approach, Elsevier, 1999.
[2] M. K. Pakhira, Digital Image Processing and Pattern Recognition, PHI Learning Pvt. Limited, 2011.
[3] T. Pavlidis, Structural Pattern Recognition, Springer, 2013.
[4] A. Galton and M. Duckham, What is the region occupied by a set of points?, Geogr. Inf. Sci. (2006) 81 - 98.
[5] A. Garcıa, M. Noy and J. Tejel, Lower bounds on the number of crossing-free subgraphs of KN, Comput. Geom. 16 (4) (2000) 211 - 221, https://doi.org/10.1016/S0925-7721(00)00010-9.
[6] H. Meijer, Upper and lower bounds for the number of monotone crossing free hamiltonian cycles from a set of points, Ars Combin. 30 (1990) 203 - 208.
[7] A. Nourollah and M. Movahedinejad, Use of simple polygonal chains in generating random simple polygons, Japan J. Indust. Appl. Math. 34 (2017) 407 - 428, https://doi.org/10.1007/s13160-017-0258-8.
[8] M. Wettstein, Counting and enumerating crossing-free geometric graphs, in: Proceedings of the thirtieth annual symposium on Computational geometry, (2014) 1 - 10, https://doi.org/10.1145/2582112.2582145.
[9] C. Zhu, G. Sundaram, J. Snoeyink and J. S. B. Mitchell, Generating random polygons with given vertices, Comput. Geom. 6 (5) (1996) 277 - 290, https://doi.org/10.1016/0925-7721(95)00031-3.
[10] S. P. Fekete and W. R. Pulleyblank, Area optimization of simple polygons, in: Proceedings of the ninth annual symposium on Computational geometry, ACM (1993) 173 - 182.
[11] S. P. Fekete, On simple polygonalizations with optimal area, Discrete Comput. Geom. 23 (1) (2000) 73 - 110, https://doi.org/10.1007/PL00009492.
[12] J. Peethambaran, A. D. Parakkat and R. Muthuganapathy, An empirical study on randomized optimal area polygonization of planar point sets, ACM J. Exp. Algorithmics 21 (1) (2016) 1 - 24, https://doi.org/10.1145/2896849.
[13] M. T. Taranilla, E. O. Gagliardi and G. Hernández Peñalver, Approaching minimum area polygonization, In XVII Congreso Argentino de Ciencias de la Computación; Universidad Nacional de La Plata: La Plata, Argentina (2011)
161 - 170.
[14] Y. Bartal, L.-A. Gottlieb and R. Krauthgamer, The traveling salesman problem: low-dimensionality implies a polynomial time approximation scheme, SIAM J. Comput. 45 (4) (2016) 1563 - 1581, https://doi.org/10.1137/130913328.
[15] A. E. Moylett, N. Linden and A. Montanaro, Quantum speedup of the traveling-salesman problem for bounded-degree graphs, Phys. Rev. A 95 (3) (2017) p. 032323, https://doi.org/10.1103/PhysRevA.95.032323.
[16] S. Dudycz, J. Marcinkowski, K. Paluch and B. Rybicki, A 4/5-approximation algorithm for the maximum traveling salesman problem, in: International Conference on Integer Programming and Combinatorial Optimization,
Springer (2017) 173 - 185.
[17] A. Aggarwal, D. Coppersmith, S. Khanna, R. Motwani and B. Schieber, The angular-metric traveling salesman problem, SIAM J. Comput. 29 (3) (2000) 697 - 711, https://doi.org/10.1137/S0097539796312721.
[18] S. P. Fekete and G. J.Woeginger, Angle-restricted tours in the plane, Comput. Geom. 8 (4) (1997) 195-218, https://doi.org/10.1016/S0925-7721(96)00012-0.
[19] S. Asaeedi, F. Didehvar and A. Mohades,  -concave hull, a generalization of convex hull, Theoret. Comput. Sci. 702 (2017) 48 - 59, https://doi.org/10.1016/j.tcs.2017.08.014.
[20] E. M. Arkin, J. S. B. Mitchell, S. P. Fekete, F. Hurtado, M. Noy, V. Sacristán and S. Sethia, On the reflexivity of point sets, Discrete and Computational Geometry, Springer (2003) 139 - 156.
[21] E. Ackerman, O. Aichholzer and B. Keszegh, Improved upper bounds on the reflexivity of point sets, Comput. Geom. 42 (3) (2009) 241 - 249, https://doi.org/10.1016/j.comgeo.2008.05.004.
[22] J.-M. Lien and N. M. Amato, Approximate convex decomposition of polyhedra and its applications, Comput. Aided Geom. Design 25 (7) (2008) 503-522, https://doi.org/10.1016/j.cagd.2008.05.003.
[23] S. Asaeedi, F. Didehvar and A. Mohades, NLP formulation for polygon optimization problems, Mathematics 7 (1) (2019) p. 24, https://doi.org/10.3390/math7010024.
[24] A. Javad, A. Mohades, M. Davoodi and F. Sheikhi, Convex hull of imprecise points modeled by segments in the plane, EuroCG (2010) 193 - 196.
[25] T. M. Chan, Optimal output-sensitive convex hull algorithms in two and three dimensions, Discrete Comput Geom. 16 (1996) 361 - 368, https://doi.org/10.1007/BF02712873.
[26] R. Jarvis, Computing the shape hull of points in the plane, in: Proc. of the IEEE Camp. Sot. Conf. on Pattern Recoanition and Image Processing, New York (1977) 231 - 241.
[27] H. Edelsbrunner, D. Kirkpatrick and R. Seidel, On the shape of a set of points in the plane, IEEE Trans. Inf. Theory. 29 (4) (1983) 551 - 559, https://doi.org/10.1109/TIT.1983.1056714.
[28] D. Krasnoshchekov and V. Polishchuk, Order-k  -hulls and-shapes, Inform. Process. Lett. 114 (1-2) (2014) 76 - 83,
https://doi.org/10.1016/j.ipl.2013.07.023.
[29] F. Sheikhi, A. Mohades, M. de Berg and M. Davoodi, Separating bichromatic point sets by l-shapes, Comput. Geom. 48 (9) (2015) 673 - 687, https://doi.org/10.1016/j.comgeo.2015.06.008.
[30] F. Sheikhi and A. Mohades, Planar maximum-box problem revisited, Theoret. Comput. Sci. 729 (2018) 57 - 67, https://doi.org/10.1016/j.tcs.2017.12.038.
[31] F. Sheikhi and A. Mohades, Maximum separability by l-shapes, in: 2020 25th International Computer Conference, Computer Society of Iran (CSICC), IEEE (2020) 1 - 7, https://doi.org/10.1109/CSICC49403.2020.9050086.
[32] F. Harary, Graph Theory, Addison-Wesley, Reading, Mass. 1969.
Mathematics Interdisciplinary Research
Volume 8, Issue 3
September 2023
Pages 247-260

Files

Share

How to cite

Statistics