{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,2]],"date-time":"2025-11-02T16:58:43Z","timestamp":1762102723897,"version":"3.40.3"},"publisher-location":"Cham","reference-count":18,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030967307"},{"type":"electronic","value":"9783030967314"}],"license":[{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022]]},"DOI":"10.1007\/978-3-030-96731-4_33","type":"book-chapter","created":{"date-parts":[[2022,3,16]],"date-time":"2022-03-16T00:03:49Z","timestamp":1647389029000},"page":"409-421","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["On Approximating Shortest Paths in\u00a0Weighted Triangular Tessellations"],"prefix":"10.1007","author":[{"given":"Prosenjit","family":"Bose","sequence":"first","affiliation":[]},{"given":"Guillermo","family":"Esteban","sequence":"additional","affiliation":[]},{"given":"David","family":"Orden","sequence":"additional","affiliation":[]},{"given":"Rodrigo I.","family":"Silveira","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,3,16]]},"reference":[{"key":"33_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1007\/BFb0054351","volume-title":"Algorithm Theory \u2014 SWAT\u201998","author":"L Aleksandrov","year":"1998","unstructured":"Aleksandrov, L., Lanthier, M., Maheshwari, A., Sack, J.-R.: An $$\\varepsilon $$ \u2014 approximation algorithm for weighted shortest paths on polyhedral surfaces. In: Arnborg, S., Ivansson, L. (eds.) SWAT 1998. LNCS, vol. 1432, pp. 11\u201322. Springer, Heidelberg (1998). https:\/\/doi.org\/10.1007\/BFb0054351"},{"key":"33_CR2","doi-asserted-by":"crossref","unstructured":"Aleksandrov, L., Maheshwari, A., Sack, J.-R.: Approximation algorithms for geometric shortest path problems. In: Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, pp. 286\u2013295 (2000)","DOI":"10.1145\/335305.335339"},{"issue":"1","key":"33_CR3","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1145\/1044731.1044733","volume":"52","author":"L Aleksandrov","year":"2005","unstructured":"Aleksandrov, L., Maheshwari, A., Sack, J.-R.: Determining approximate shortest paths on weighted polyhedral surfaces. J. ACM 52(1), 25\u201353 (2005)","journal-title":"J. ACM"},{"issue":"10","key":"33_CR4","doi-asserted-by":"publisher","first-page":"4149","DOI":"10.1007\/s00500-015-1750-1","volume":"20","author":"A Ammar","year":"2015","unstructured":"Ammar, A., Bennaceur, H., Ch\u00e2ari, I., Koub\u00e2a, A., Alajlan, M.: Relaxed Dijkstra and $$ {A}^{*} $$ with linear complexity for robot path planning problems in large-scale grid environments. Soft Comput. 20(10), 4149\u20134171 (2015). https:\/\/doi.org\/10.1007\/s00500-015-1750-1","journal-title":"Soft Comput."},{"key":"33_CR5","doi-asserted-by":"crossref","unstructured":"Bailey, J., Tovey, C., Uras, T., Koenig, S., Nash, A.: Path planning on grids: the effect of vertex placement on path length. In: Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, vol. 11 (2015)","DOI":"10.1609\/aiide.v11i1.12808"},{"key":"33_CR6","doi-asserted-by":"crossref","unstructured":"Bose, P., Esteban, G., Orden, D., Silveira, R.I.: On approximating shortest paths in weighted triangular tessellations. arXiv preprint arXiv:2111.13912 (2021)","DOI":"10.1007\/978-3-030-96731-4_33"},{"key":"33_CR7","doi-asserted-by":"crossref","unstructured":"Chang, H.C., Erickson, J., Xu, C.: Detecting weakly simple polygons. In: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1655\u20131670. SIAM (2014)","DOI":"10.1137\/1.9781611973730.110"},{"issue":"4","key":"33_CR8","doi-asserted-by":"publisher","first-page":"1223","DOI":"10.1137\/S0097539796307194","volume":"29","author":"DZ Chen","year":"2000","unstructured":"Chen, D.Z., Klenk, K.S., Tu, H.: Shortest path queries among weighted obstacles in the rectilinear plane. SIAM J. Comput. 29(4), 1223\u20131246 (2000)","journal-title":"SIAM J. Comput."},{"key":"33_CR9","doi-asserted-by":"crossref","unstructured":"Cheng, S., Jin, J., Vigneron, A.: Triangulation refinement and approximate shortest paths in weighted regions. In: Indyk, P. (ed.) Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, 4\u20136 January 2015, pp. 1626\u20131640. SIAM (2015)","DOI":"10.1137\/1.9781611973730.108"},{"issue":"7","key":"33_CR10","doi-asserted-by":"publisher","first-page":"724","DOI":"10.1016\/j.comgeo.2014.02.004","volume":"47","author":"JL de Carufel","year":"2014","unstructured":"de Carufel, J.L., Grimm, C., Maheshwari, A., Owen, M., Smid, M.: A note on the unsolvability of the weighted region shortest path problem. Comput. Geom. 47(7), 724\u2013727 (2014)","journal-title":"Comput. Geom."},{"issue":"3","key":"33_CR11","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1287\/ijoc.2.3.253","volume":"2","author":"L Gewali","year":"1990","unstructured":"Gewali, L., Meng, A.C., Mitchell, J.S.B., Ntafos, S.C.: Path planning in 0\/1\/$$\\infty $$ weighted regions with applications. INFORMS J. Comput. 2(3), 253\u2013272 (1990)","journal-title":"INFORMS J. Comput."},{"key":"33_CR12","unstructured":"Jaklin, N.S.: On weighted regions and social crowds: autonomous-agent navigation in virtual worlds. Ph.D. thesis, Utrecht University (2016)"},{"key":"33_CR13","unstructured":"Mitchell, J.: Shortest paths among obstacles, zero-cost regions, and roads. Technical report, Cornell University Operations Research and Industrial Engineering (1987)"},{"issue":"1","key":"33_CR14","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1145\/102782.102784","volume":"38","author":"J Mitchell","year":"1991","unstructured":"Mitchell, J., Papadimitrou, C.: The weighted region problem: finding shortest paths through a weighted planar subdivision. J. ACM 38(1), 18\u201373 (1991)","journal-title":"J. ACM"},{"key":"33_CR15","unstructured":"Mitchell, J.S.B.: Shortest paths and networks. In: Goodman, J.E., O\u2019Rourke, J., Toth, C.D. (eds.) Handbook of Discrete and Computational Geometry, 2nd edn., pp. 811\u2013848. Chapman and Hall\/CRC (2017)"},{"issue":"2","key":"33_CR16","doi-asserted-by":"publisher","first-page":"111","DOI":"10.2498\/cit.2003.02.04","volume":"11","author":"BN Nagy","year":"2003","unstructured":"Nagy, B.N.: Shortest paths in triangular grids with neighbourhood sequences. J. Comput. Inf. Technol. 11(2), 111\u2013122 (2003)","journal-title":"J. Comput. Inf. Technol."},{"key":"33_CR17","unstructured":"Nash, A.: Any-angle path planning. Ph.D. thesis, University of Southern California (2012)"},{"key":"33_CR18","doi-asserted-by":"crossref","unstructured":"Van Toll, W., et al.: A comparative study of navigation meshes. In: Proceedings of the 9th International Conference on Motion in Games, pp. 91\u2013100 (2016)","DOI":"10.1145\/2994258.2994262"}],"container-title":["Lecture Notes in Computer Science","WALCOM: Algorithms and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-96731-4_33","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,29]],"date-time":"2023-01-29T06:57:08Z","timestamp":1674975428000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-96731-4_33"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"ISBN":["9783030967307","9783030967314"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-96731-4_33","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2022]]},"assertion":[{"value":"16 March 2022","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WALCOM","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference and Workshops on Algorithms and Computation","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Jember","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Indonesia","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2022","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"24 March 2022","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"26 March 2022","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"16","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"walcom2022","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/walcom2022.unej.ac.id\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"89","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"30","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"34% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"2-9","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"The proceedings also include 3 invited papers.","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}