{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,8]],"date-time":"2025-07-08T12:51:32Z","timestamp":1751979092716,"version":"3.37.3"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2024,2,10]],"date-time":"2024-02-10T00:00:00Z","timestamp":1707523200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,2,10]],"date-time":"2024-02-10T00:00:00Z","timestamp":1707523200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000780","name":"European Union","doi-asserted-by":"crossref","award":["Robotics and advanced industrial production (reg. no. CZ.02.01.01\/00\/22_008\/0004590)"],"award-info":[{"award-number":["Robotics and advanced industrial production (reg. no. CZ.02.01.01\/00\/22_008\/0004590)"]}],"id":[{"id":"10.13039\/501100000780","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Grant Agency of the Czech Technical University in Prague","award":["SGS23\/175\/OHK3\/3T\/13"],"award-info":[{"award-number":["SGS23\/175\/OHK3\/3T\/13"]}]},{"DOI":"10.13039\/100007655","name":"Czech Technical University in Prague","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100007655","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["SN COMPUT. SCI."],"abstract":"<jats:title>Abstract<\/jats:title><jats:p>This paper addresses the problem of improving the query performance of the <jats:italic>triangular expansion algorithm<\/jats:italic> (TEA) for computing <jats:italic>visibility regions<\/jats:italic> by finding the most advantageous instance of the <jats:italic>triangular mesh<\/jats:italic>, the preprocessing structure. The TEA recursively traverses the mesh while keeping track of the visible region\u2014the set of all points visible from a query point in a polygonal world. We show that the measured query time is approximately proportional to the number of triangle edge expansions during the mesh traversal. We propose a new type of triangular mesh that minimizes the expected number of expansions assuming the query points are drawn from a known probability distribution. We design a heuristic method to approximate the mesh and evaluate the approach on many challenging instances that resemble real-world environments. The proposed mesh improves the mean query times by 12\u201316% compared to the reference <jats:italic>constrained Delaunay triangulation<\/jats:italic>. The approach is suitable to boost offline applications that require computing millions of queries without addressing the preprocessing time. The implementation is publicly available to replicate our experiments and serve the community.<\/jats:p>","DOI":"10.1007\/s42979-023-02561-y","type":"journal-article","created":{"date-parts":[[2024,2,10]],"date-time":"2024-02-10T15:03:32Z","timestamp":1707577412000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Optimizing Mesh to Improve the Triangular Expansion Algorithm for Computing Visibility Regions"],"prefix":"10.1007","volume":"5","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3404-8742","authenticated-orcid":false,"given":"Jan","family":"Mikula","sequence":"first","affiliation":[]},{"given":"Miroslav","family":"Kulich","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,2,10]]},"reference":[{"issue":"1","key":"2561_CR1","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/0146-664X(79)90076-5","volume":"11","author":"LS Davis","year":"1979","unstructured":"Davis LS, Benedikt ML. Computational models of space: Isovists and isovist fields. Comp Graphics Image Process. 1979;11(1):49\u201372.","journal-title":"Comp Graphics Image Process"},{"issue":"9","key":"2561_CR2","first-page":"557","volume":"68","author":"T Asano","year":"1985","unstructured":"Asano T. An efficient algorithm for finding the visibility polygon for a polygonal region with holes. IEICE Trans. 1985;68(9):557\u20139.","journal-title":"IEICE Trans"},{"key":"2561_CR3","unstructured":"Bungiu F, Hemmer M, Hershberger J, Huang K, Kr\u00f6ller A. Efficient Computation of Visibility Polygons. 2014. arXiv:1403.3905"},{"key":"2561_CR4","doi-asserted-by":"crossref","unstructured":"Mikula J, Kulich M. Triangular expansion revisited: which triangulation is the best? In: Proceedings of the 19th International Conference on Informatics in Control, Automation and Robotics. 2022, pp. 313\u2013319","DOI":"10.5220\/0011278700003271"},{"issue":"1","key":"2561_CR5","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/S0925-7721(01)00047-5","volume":"22","author":"JR Shewchuk","year":"2002","unstructured":"Shewchuk JR. Delaunay refinement algorithms for triangular mesh generation. Comput Geometry. 2002;22(1):21\u201374.","journal-title":"Comput Geometry"},{"key":"2561_CR6","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1609\/socs.v15i1.21770","volume":"15","author":"D Harabor","year":"2022","unstructured":"Harabor D, Hechenberger R, Jahn T. Benchmarks for pathfinding search: iron harvest. Proc Int Symp Combinatorial Search. 2022;15:218\u201322.","journal-title":"Proc Int Symp Combinatorial Search"},{"issue":"4","key":"2561_CR7","doi-asserted-by":"publisher","first-page":"458","DOI":"10.1007\/BF01937271","volume":"27","author":"B Joe","year":"1987","unstructured":"Joe B, Simpson RB. Corrections to Lee\u2019s visibility polygon algorithm. BIT. 1987;27(4):458\u201373.","journal-title":"BIT"},{"issue":"1","key":"2561_CR8","doi-asserted-by":"publisher","first-page":"184","DOI":"10.1137\/S0097539791221505","volume":"24","author":"PJ Heffernan","year":"1995","unstructured":"Heffernan PJ, Mitchell JSB. An optimal algorithm for computing visibility in the plane. SIAM J Comput. 1995;24(1):184\u2013201.","journal-title":"SIAM J Comput"},{"issue":"2","key":"2561_CR9","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1016\/j.comgeo.2007.02.005","volume":"39","author":"A Zarei","year":"2008","unstructured":"Zarei A, Ghodsi M. Query point visibility computation in polygons with holes. Comput Geometry. 2008;39(2):78\u201390.","journal-title":"Comput Geometry"},{"issue":"9","key":"2561_CR10","doi-asserted-by":"publisher","first-page":"852","DOI":"10.1016\/j.comgeo.2009.02.004","volume":"42","author":"R Inkulu","year":"2009","unstructured":"Inkulu R, Kapoor S. Visibility queries in a polygonal region. Comput Geometry. 2009;42(9):852\u201364.","journal-title":"Comput Geometry"},{"issue":"2","key":"2561_CR11","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1016\/j.comgeo.2014.08.003","volume":"48","author":"DZ Chen","year":"2015","unstructured":"Chen DZ, Wang H. Visibility and ray shooting queries in polygonal domains. Comput Geometry. 2015;48(2):31\u201341.","journal-title":"Comput Geometry."},{"key":"2561_CR12","doi-asserted-by":"crossref","unstructured":"Kulich M, P\u0159eu\u010dil L, Miranda-Bront JJ. Single robot search for a stationary object in an unknown environment. In: Proceedings of 2014 IEEE International Conference on Robotics and Automation. 2014, pp. 5830\u20135835.","DOI":"10.1109\/ICRA.2014.6907716"},{"key":"2561_CR13","doi-asserted-by":"publisher","first-page":"178","DOI":"10.1016\/j.cor.2016.04.029","volume":"84","author":"M Kulich","year":"2017","unstructured":"Kulich M, Miranda-Bront JJ, P\u0159eu\u010dil L. A meta-heuristic based goal-selection strategy for mobile robot search in an unknown environment. Comput Oper Res. 2017;84:178\u201387.","journal-title":"Comput Oper Res."},{"issue":"6","key":"2561_CR14","doi-asserted-by":"publisher","first-page":"1400","DOI":"10.3390\/s19061400","volume":"19","author":"M Kulich","year":"2019","unstructured":"Kulich M, Kubal\u00edk J, P\u0159eu\u010dil L. An Integrated Approach to Goal Selection in Mobile Robot Exploration. Sensors. 2019;19(6):1400.","journal-title":"Sensors."},{"key":"2561_CR15","volume-title":"Art gallery theorems and algorithms","author":"J O\u2019Rourke","year":"1987","unstructured":"O\u2019Rourke J. Art gallery theorems and algorithms. Oxford: Oxford University Press; 1987."},{"issue":"3","key":"2561_CR16","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/0925-7721(92)90014-J","volume":"1","author":"S Ntafos","year":"1992","unstructured":"Ntafos S. Watchman routes under limited visibility. Comput Geometry Theory Appl. 1992;1(3):149\u201370.","journal-title":"Comput Geometry Theory Appl"},{"key":"2561_CR17","doi-asserted-by":"crossref","unstructured":"Guibas LJ, Latombe J-C, LaValle SM, Lin D, Motwani R. Visibility-based pursuit-evasion in a polygonal environment. In: Workshop on Algorithms and Data Structures. Berlin: Springer; 1997, pp. 17\u201330","DOI":"10.1007\/3-540-63307-3_45"},{"issue":"3","key":"2561_CR18","doi-asserted-by":"publisher","first-page":"5934","DOI":"10.1109\/LRA.2022.3159824","volume":"7","author":"J Mikula","year":"2022","unstructured":"Mikula J, Kulich M. Towards a continuous solution of the d-visibility watchman route problem in a polygon with holes. IEEE Robot Autom Lett. 2022;7(3):5934\u201341.","journal-title":"IEEE Robot Autom Lett"},{"key":"2561_CR19","unstructured":"CGAL: computational geometry algorithms library. https:\/\/www.cgal.org\/"},{"issue":"2","key":"2561_CR20","first-page":"77","volume":"7","author":"EM Arkin","year":"2016","unstructured":"Arkin EM, Efrat A, Knauer C, Mitchell JS, Polishchuk V, Rote G, Schlipf L, Talvitie T. Shortest path to a segment and quickest visibility queries. J Comp Geometry. 2016;7(2):77\u2013100.","journal-title":"J Comp Geometry"},{"key":"2561_CR21","doi-asserted-by":"crossref","unstructured":"Cui M, Harabor DD, Grastien A. Compromise-free pathfinding on a navigation mesh. In: Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI-17. 2017, pp. 496\u2013502","DOI":"10.24963\/ijcai.2017\/70"},{"key":"2561_CR22","doi-asserted-by":"crossref","unstructured":"Shen B, Cheema MA, Harabor D, Stuckey PJ. Euclidean pathfinding with compressed path databases. In: Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI-20. 2020, pp. 4229\u20134235","DOI":"10.24963\/ijcai.2020\/584"},{"key":"2561_CR23","unstructured":"Keynes JM. The principle of indifference. In: A treatise on probability, vol. 4. London: Macmillan and Co;1921, pp. 41\u201364."},{"issue":"03","key":"2561_CR24","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1142\/S0218195908002581","volume":"18","author":"M Grantson","year":"2008","unstructured":"Grantson M, Borgelt C, Levcopoulos C. Fixed parameter algorithms for the minimum weight triangulation problem. Int J Comput Geometry Appl. 2008;18(03):185\u2013220.","journal-title":"Int J Comput Geometry Appl"},{"issue":"2","key":"2561_CR25","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1346330.1346336","volume":"55","author":"W Mulzer","year":"2008","unstructured":"Mulzer W, Rote G. Minimum-weight triangulation is NP-hard. J ACM (JACM). 2008;55(2):1\u201329.","journal-title":"J ACM (JACM)"},{"issue":"3","key":"2561_CR26","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1007\/PL00009321","volume":"18","author":"JR Shewchuk","year":"1997","unstructured":"Shewchuk JR. Adaptive precision floating-point arithmetic and fast robust geometric predicates. Discrete Comput Geometry. 1997;18(3):305\u201363.","journal-title":"Discrete Comput Geometry"},{"key":"2561_CR27","doi-asserted-by":"publisher","first-page":"72","DOI":"10.1016\/j.neucom.2012.10.004","volume":"104","author":"D Fi\u0161er","year":"2013","unstructured":"Fi\u0161er D, Faigl J, Kulich M. Growing neural gas efficiently. Neurocomputing. 2013;104:72\u201382.","journal-title":"Neurocomputing"},{"issue":"2","key":"2561_CR28","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1145\/357337.357338","volume":"3","author":"M Edahiro","year":"1984","unstructured":"Edahiro M, Kokubo I, Asano T. A new point-location algorithm and its practical efficiency: comparison with existing algorithms. ACM Trans Graphics (TOG). 1984;3(2):86\u2013109.","journal-title":"ACM Trans Graphics (TOG)"},{"key":"2561_CR29","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1007\/BFb0014497","volume":"1148","author":"JR Shewchuk","year":"1996","unstructured":"Shewchuk JR. Triangle: engineering a 2D quality mesh generator and delaunay triangulator. Appl Comput Geometry Towards Geometr Eng. 1996;1148:203\u201322.","journal-title":"Appl Comput Geometry Towards Geometr Eng"}],"container-title":["SN Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s42979-023-02561-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s42979-023-02561-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s42979-023-02561-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,10]],"date-time":"2024-02-10T15:17:35Z","timestamp":1707578255000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s42979-023-02561-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,2,10]]},"references-count":29,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2024,2]]}},"alternative-id":["2561"],"URL":"https:\/\/doi.org\/10.1007\/s42979-023-02561-y","relation":{},"ISSN":["2661-8907"],"issn-type":[{"type":"electronic","value":"2661-8907"}],"subject":[],"published":{"date-parts":[[2024,2,10]]},"assertion":[{"value":"3 November 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 December 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 February 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"On behalf of all authors, the corresponding author states that there is no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"262"}}