Pseudo-triangle visibility graph: Characterization and reconstruction

Document Type : Article

Authors

Department of Mathematical Sciences, Sharif University of Technology, P.O. Box 11155-9415, Tehran, Iran

Abstract

The visibility graph of a simple polygon represents visibility relations between its vertices. Knowing the correct order of the vertices around the boundary of a polygon and its visibility graph, it is an open problem to locate the vertices in a plane such that it will be consistent with this visibility graph. This problem has been solved for special cases when we know that the target is a tower, a spiral, or an anchor polygon. Knowing that a given visibility graph belongs to a simple polygon with at most three concave chains on its boundary, a pseudo-triangle, we propose a linear-time algorithm for reconstructing one of its corresponding polygons. Moreover, we introduce a set of necessary and sucient properties for characterizing visibility graphs of pseudo-triangles and propose polynomial algorithms for checking these properties.

Keywords

Main Subjects

References

References:
1. Asano, T., Asano, T., Guibas, L., et al. "Visibility of disjoint polygons", Algorithmica, 1, pp. 49-63 (1986). DOI: 10.1007/BF01840436.
2. Welzl, E. "Constructing the visibility graph for n-nline segments in o(n2) time", Information Processing Letters, 20(4), pp. 167-171 (1985). DOI: 10.1016/0020- 0190(85)90059-3.
3. Hershberger, J. "Finding the visibility graph of a simple polygon in time proportional to its size", Third Annual Symposium on Computational Geometry, pp. 11-20 (1987). DOI: 10.1145/41958.41960.
4. Chazelle, B. "Triangulating a simple polygon in linear time", Discrete and Computational Geometry, 6, pp. 485-424 (1991). DOI: 10.1007/BF02574689.
5. Davies, J., Krawczyk, T., McCarty, R., et al. "Coloring polygon visibility graphs and their generalizations", Journal of Combinatorial Theory, Series B, 161, pp. 268-300 (2023). DOI: 10.1016/j.jctb.2023.01.001.
6. Caughman, J.S., Dunn, C.L., Laison, J.D., et al. "Area, perimeter, height, and width of rectangle visibility graphs", Journal of Combinatorial Optimization, 46(3), p. 18 (2023). DOI: 10.1007/s10878-022-00864-5.
7. Schmidt, J. and Kohne, D. "A simple scalable linear time algorithm for horizontal visibility graphs", Physica A: Statistical Mechanics and its Applications, 616, pp. 128-601 (2023). DOI: 10.1016/j.physa.2022.128601.
8. Lee, W., Choi, G.-H., and Wan Kim, T. "Visibility graph-based path-planning algorithm with quadtree representation", Applied Ocean Research, 117, pp. 102-887 (2021). DOI: 10.1016/j.apor.2021.102887.
9. Everett, H. "Visibility graph recognition", PhD thesis, University of Toronto, Department of Computer Science (1990). DOI: 10.5683/SP2/8ZQZ9H.
10. Ameer, S., Gibson-Lopez, M., Krohn, E., et al. "On the visibility graphs of pseudo-polygons: Recognition and reconstruction", 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022), 227, of Leibniz International Proceedings in Informatics (LIPIcs), pp. 7:1-7:13 (2022). DOI: 10.4230/LIPIcs.SWAT.2022.7.
11. Gibson, M., Krohn, E., and Wang, Q. "A characterization of visibility graphs for pseudo-polygons", 23rd Annual European Symposium (ESA 2015), pp. 607-618 (2015). DOI: 10.4230/LIPIcs.ESA.2015.607.
12. O'Rourke, J. and Streinu, I. "Vertex-edge pseudovisibility graphs: Characterization and recognition", 13'th Annual Symposium on Computational Geometry (SoCG 1997), pp. 119-128 (1997). DOI: 10.1145/262839.262858.
13. O'Rourke, J. and Streinu, I. "The vertex-edge visibility graph of a polygon", Computational Geometry, 10(2), pp. 105-120 (1998). DOI: 10.1016/S0925- 7721(97)00026-2.
14. Streinu, I. "Non-stretchable pseudo-visibility graphs", Computational Geometry, 31(3), pp. 195-206 (2005). DOI: 10.1016/j.comgeo.2004.11.001.
15. Casel, K., Fernau, H., and Grigoriev, A. "Combinatorial properties and recognition of unit square visibility graphs", Discrete Computational Geometry, 69, pp. 937-980 (2023). DOI: 10.1007/s00454-023-00345-2.
16. Boomari, H., Ostovari, M., and Zarei, A. "Recognizing visibility graphs of triangulated irregular networks", Fundamenta Informaticae, 179(4), pp. 345-360 (2021). DOI: 10.3233/FI-2021-2045.
17. Cardinal, J. and Homann, U. "Recognition and complexity of point visibility graphs", 31st International Symposium on Computational Geometry (SoCG 2015), 34, pp. 171-185 (2015). DOI: 10.4230/LIPIcs.SOCG.2015.171.
18. Abrahamsen, M., Adamaszek, A., and Miltzow, T. "The art gallery problem is 9r-complete", Journal of the ACM, 69(1), pp. 1-70 (2021). DOI: 10.1145/3447242.
19. Schaefer, M. "RAC-drawability is 9R-complete and related results", Journal of Graph Algorithms and Applications, 27(9), pp. 803-841 (2024). DOI: 10.7155/jgaa.00591.
20. Everett, H. and Corneil, D.G. "Recognizing visibility graphs of spiral polygons", Journal of Algorithms, 11(1), pp. 1-26 (1990). DOI: 10.1016/0196- 6774(90)90002-4.
21. Colley, P., Lubiw, A., and Spinrad, J. "Visibility graphs of towers", Computational Geometry, 7, pp. 161-172 (1997). DOI: 10.1016/S0925-7721(96)00025-6.
22. Boomari, H. and Zarei, A. "Visibility graphs of anchor polygons", J. Graph Algorithms Appl., 26(1), pp. 15- 34 (2022). DOI: 10.7155/jgaa.00591.
23. Abello, J., Egecioglu, O., and Kumar, K. "Visibility graphs of staircase polygons and the weak Bruhat order I: From visibility graphs to maximal chains", Discrete & Computational Geometry, 14(3), pp. 331- 358 (1995). DOI: 10.1007/BF02570718.
24. Coullard, C.R. and Lubiw, A. "Distance visibility graphs", International Journal of Computational Geometry & Applications, 2(4), pp. 349-362 (1992). DOI: 10.1142/S0218195992000201.
25. ElGindy, H. "Hierarchical decomposition of polygons with applications", PhD thesis, McGill University, Department of Computer Science (1985). DOI: 10.5683/SP2/8ZQZ9H.
26. Ghosh, S.K. "On recognizing and characterizing visibility graphs of simple polygons", 1st Scandinavian Workshop on Algorithm Theory (SWAT 88), Springer Berlin Heidelberg, pp. 96-104 (1988). DOI: 10.1007/3- 540-19487-8 10.
27. Ghosh, S.K. "On recognizing and characterizing visibility graphs of simple polygons", Discrete & Computational Geometry 17(2), pp. 143-162 (1997). DOI: 10.1007/PL00009321.
28. Abello, J., Lin, H., and Pisupati, S. "On visibility graphs of simple polygons", Congressus Numerantium, (90), pp. 119-128 (1992). DOI: 10.1007/BF02574689.
Scientia Iranica
Volume 31, Issue 21
Transactions on Computer Science & Engineering and Electrical Engineering (D)
November and December 2024
Pages 1948-1962

Files

History

  • Receive Date: 02 October 2023
  • Revise Date: 05 February 2024
  • Accept Date: 18 May 2024

Share

How to cite

Statistics