Optimization of Visibility Graph Construction Algorithm

Authors

  • Maxim Barinov Entroforce Company, 16 liniya V. O. 7 lit. B, St. Petersburg, 199034, Russian Federation , Saint Petersburg State Electrotechnical University image/svg+xml
  • Dmitry Pavlov Saint Petersburg State Electrotechnical University image/svg+xml

DOI:

https://doi.org/10.32603/2071-2340-2026-2-20-33

Keywords:

visibility graph, path planning, Lee's algorithm, sweeping ray, computational geometry, reduced visibility graph, memory defragmentation.

Abstract

Optimizations of Lee's algorithm for constructing a visibility graph on a plane with polygonal obstacles are proposed. The optimizations include elimination of provably minor edges, vertex pruning based on geometric properties, defragmented graph storage in memory, and parallel processing of source vertices. Various graph representation methods and their impact on performance are considered.

Author Biographies

  • Maxim Barinov, Entroforce Company, 16 liniya V. O. 7 lit. B, St. Petersburg, 199034, Russian Federation, Saint Petersburg State Electrotechnical University

    Software Engineer at Entroforce Company; 3rd-year student at the Department of Algorithmic Mathematics, ETU "LETI", mbarinov@entroforce.ru

  • Dmitry Pavlov, Saint Petersburg State Electrotechnical University

    Cand. Sci. (Phys.-Math.), Associate professor at the Department of Algorithmic Mathematics, ETU "LETI", dapavlov@etu.ru

References

N. J. Nilsson, "A mobile automaton: An application of artificial intelligence techniques," in Proceedings of the 1st International Joint Conference on Artificial Intelligence (IJCAI'69), D. E. Walker and L. M. Norton, Eds., 1969, pp. 509-520.

D. T. Lee, "Proximity and reachability in the plane," Ph.D. dissertation, University of Illinois at Urbana-Champaign, 1978.

D. Coleman, "Lee's O(n2log n) visibility graph algorithm: Implementation and analysis," University of Colorado at Boulder, Technical report, 2012.

S. K. Ghosh and D. M. Mount, "An output-sensitive algorithm for computing visibility graphs," in Proceedings of the 28th Annual Symposium on Foundations of Computer Science (FOCS'87). IEEE, 1987, pp. 11-19, doi: 10.1109/SFCS.1987.6.

M. H. Overmars and E. Welzl, "New methods for computing visibility graphs," in Proceedings of the fourth annual symposium on Computational geometry (SCG'88), 1988, pp. 164-171, doi: 10.1145/73393.73410.

K. Daniel, A. Nash, S. Koenig, and A. Felner, "Theta*: Any-angle path planning on grids," Journal of Artificial Intelligence Research, vol. 39, pp. 533-579, 2010, doi: 10.1613/jair.2994.

A. Nash, S. Koenig, and C. Tovey, "Lazy Theta*: Any-angle path planning and path length analysis in 3D," in Proc. of the AAAI Conference on Artificial Intelligence, M. Fox and D. Poole, Eds., vol. 24. Palo Alto, California USA: AAAI Press, 2010, pp. 147-154, doi: 10.1609/aaai.v24i1.7566.

D. Harabor and A. Grastien, "An optimal any-angle pathfinding algorithm," in Proc. of the International Conference on Automated Planning and Scheduling (ICAPS), D. Borrajo, S. Kambhampati, A. Oddi, and S. Fratini, Eds., vol. 23, 2013, pp. 308-311, doi: 10.1609/icaps.v23i1.13609.

D. Ferguson and A. Stentz, "Field D*: An interpolation-based path planner and replanner," in Robotics Research, S. Thrun, R. Brooks, and H. Durrant-Whyte, Eds. Berlin, Heidelberg: Springer, 2007, pp. 239–253, doi: 10.1007/978-3-540-48113-3_22.

J. O'Rourke and I. Streinu, "The vertex-edge visibility graph of a polygon," Computational Geometry, vol. 10, no. 2, pp. 105–120, 1998, doi: 10.1016/S0925-7721(97)00011-4.

Boost graph library: Adjacency list. [Online]. Available: https://www.boost.org/doc/libs/1_91_0/libs/graph/doc/adjacency_list.html

Boost graph library: Compressed sparse row. [Online]. Available: https://www.boost.org/doc/libs/1_91_0/libs/graph/doc/compressed_sparse_row.html

M. Besta, D. Stanojevic, T. Zivic, J. Singh, M. Hoerold, and T. Hoefler, "Log(graph): a near-optimal high-performance graph representation," in Proceedings of the 27th International Conference on Parallel Architectures and Compilation Techniques, 2018, doi: 10.1145/3243176.3243198.

Egerváry Research Group. Lemon - library for efficient modeling and optimization in networks. [Online]. Available: http://lemon.cs.elte.hu/trac/lemon

D. Pavlov, M. Rybalkin, B. Karulin, M. Kozhevnikov, A. Savelyev, and A. Churinov, "Indigo: universal cheminformatics api," J Cheminform, vol. 3, no. Suppl 1, p. P4, 2011, doi: 10.1186/1758-2946-3-S1-P4.

EPAM Systems. Indigo github repository. [Online]. Available: https://github.com/epam/Indigo

U.S. Office of Coast Survey. NOAA ENC electronic navigational charts. [Online]. Available: https://charts.noaa.gov/ENCs/ENCsIndv.shtml

Published

2026-06-30

Issue

No. 2 (2026)

Section

Algorithmic mathematics and mathematical modelling

License

Copyright (c) 2026 Maxim Barinov, Dmitry Pavlov

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

How to Cite

[1]
M. Barinov and D. Pavlov, “Optimization of Visibility Graph Construction Algorithm”, Computer Tools in Education, no. 2, pp. 20–33, Jun. 2026, doi: 10.32603/2071-2340-2026-2-20-33.

Similar Articles

1-10 of 543

You may also start an advanced similarity search for this article.

Most read articles by the same author(s)