{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T13:01:38Z","timestamp":1742994098546,"version":"3.40.3"},"publisher-location":"Cham","reference-count":44,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031389054"},{"type":"electronic","value":"9783031389061"}],"license":[{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023]]},"DOI":"10.1007\/978-3-031-38906-1_26","type":"book-chapter","created":{"date-parts":[[2023,7,27]],"date-time":"2023-07-27T16:05:14Z","timestamp":1690473914000},"page":"401-415","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Observation Routes and\u00a0External Watchman Routes"],"prefix":"10.1007","author":[{"given":"Adrian","family":"Dumitrescu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Csaba D.","family":"T\u00f3th","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,7,28]]},"reference":[{"key":"26_CR1","doi-asserted-by":"crossref","unstructured":"Abrahamsen, M., Adamaszek, A., Miltzow, T.: The art gallery problem is $$\\exists \\mathbb{R} $$-complete. J. ACM 69(1), 4:1\u20134:70 (2022)","DOI":"10.1145\/3486220"},{"key":"26_CR2","unstructured":"Absar, R., Whitesides, S.: On computing shortest external watchman routes for convex polygons. In: Proceedings 18th Canadian Conference on Computational Geometry (CCCG), Kingston, ON (2006)"},{"issue":"3","key":"26_CR3","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1016\/0166-218X(94)90008-6","volume":"55","author":"EM Arkin","year":"1994","unstructured":"Arkin, E.M., Hassin, R.: Approximation algorithms for the geometric covering salesman problem. Discret. Appl. Math. 55(3), 197\u2013218 (1994)","journal-title":"Discret. Appl. Math."},{"issue":"5","key":"26_CR4","doi-asserted-by":"publisher","first-page":"753","DOI":"10.1145\/290179.290180","volume":"45","author":"S Arora","year":"1998","unstructured":"Arora, S.: Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. J. ACM 45(5), 753\u2013782 (1998)","journal-title":"J. ACM"},{"issue":"4","key":"26_CR5","doi-asserted-by":"publisher","first-page":"42:1","DOI":"10.1145\/3398684","volume":"16","author":"\u00c9 Bonnet","year":"2020","unstructured":"Bonnet, \u00c9., Miltzow, T.: Parameterized hardness of art gallery problems. ACM Trans. Algorithms 16(4), 42:1-42:23 (2020)","journal-title":"ACM Trans. Algorithms"},{"issue":"3","key":"26_CR6","doi-asserted-by":"publisher","first-page":"377","DOI":"10.1007\/PL00009467","volume":"22","author":"S Carlsson","year":"1999","unstructured":"Carlsson, S., Jonsson, H., Nilsson, B.J.: Finding the shortest watchman route in a simple polygon. Discret. Comput. Geom. 22(3), 377\u2013402 (1999)","journal-title":"Discret. Comput. Geom."},{"key":"26_CR7","doi-asserted-by":"crossref","unstructured":"Chin, W.-P., Ntafos, S.: Optimum watchman routes. In: Proceedings of the 2nd ACM Symposium on Computational Geometry (SoCG), pp. 24\u201333 (1986)","DOI":"10.1145\/10515.10518"},{"key":"26_CR8","doi-asserted-by":"crossref","unstructured":"Chin, W.-P., Ntafos, S.: Optimum watchman routes. Inf. Process. Lett. 28(1), 39\u201344 (1988)","DOI":"10.1016\/0020-0190(88)90141-X"},{"issue":"1","key":"26_CR9","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1007\/BF02574671","volume":"6","author":"W-P Chin","year":"1991","unstructured":"Chin, W.-P., Ntafos, S.: Shortest watchman routes in simple polygons. Discrete Comput. Geom. 6(1), 9\u201331 (1991)","journal-title":"Discrete Comput. Geom."},{"key":"26_CR10","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1016\/j.jalgor.2005.01.010","volume":"57","author":"M de Berg","year":"2005","unstructured":"de Berg, M., Gudmundsson, J., Katz, M., Levcopoulos, C., Overmars, M., van der Stappen, A.: TSP with neighborhoods of varying size. J. Algorithms 57, 22\u201336 (2005)","journal-title":"J. Algorithms"},{"key":"26_CR11","doi-asserted-by":"crossref","unstructured":"Dinur, I., Steurer, D.: Analytical approach to parallel repetition. In: Proceedings of the 46th STOC, pp. 624\u2013633 (2014)","DOI":"10.1145\/2591796.2591884"},{"key":"26_CR12","doi-asserted-by":"crossref","unstructured":"Dror, M., Efrat, A., Lubiw, A., Mitchell, J.S.B.: Touring a sequence of polygons. In: Proceedings of the 35th ACM Symposium on Theory of Computing (STOC), pp. 473\u2013482 (2003)","DOI":"10.1145\/780542.780612"},{"issue":"4","key":"26_CR13","doi-asserted-by":"publisher","first-page":"1019","DOI":"10.1137\/050636589","volume":"21","author":"M Dror","year":"2008","unstructured":"Dror, M., Orlin, J.B.: Combinatorial optimization with explicit delineation of the ground set by a collection of subsets. SIAM J. Disc. Math. 21(4), 1019\u20131034 (2008)","journal-title":"SIAM J. Disc. Math."},{"issue":"1","key":"26_CR14","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1016\/j.comgeo.2005.07.004","volume":"36","author":"A Dumitrescu","year":"2007","unstructured":"Dumitrescu, A., Ebbers-Baumann, A., Gr\u00fcne, A., Klein, R., Rote, G.: On the geometric dilation of closed curves, graphs, and point sets. Comput. Geom. 36(1), 16\u201338 (2007)","journal-title":"Comput. Geom."},{"issue":"1","key":"26_CR15","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1016\/S0196-6774(03)00047-6","volume":"48","author":"A Dumitrescu","year":"2003","unstructured":"Dumitrescu, A., Mitchell, J.S.B.: Approximation algorithms for TSP with neighborhoods in the plane. J. Algorithms 48(1), 135\u2013159 (2003)","journal-title":"J. Algorithms"},{"issue":"3","key":"26_CR16","doi-asserted-by":"publisher","first-page":"188","DOI":"10.1016\/j.comgeo.2004.12.009","volume":"37","author":"A Ebbers-Baumann","year":"2007","unstructured":"Ebbers-Baumann, A., Gr\u00fcne, A., Klein, R.: Geometric dilation of closed planar curves: New lower bounds. Comput. Geom. 37(3), 188\u2013208 (2007)","journal-title":"Comput. Geom."},{"issue":"1","key":"26_CR17","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1007\/s00453-001-0040-8","volume":"31","author":"SJ Eidenbenz","year":"2001","unstructured":"Eidenbenz, S.J., Stamm, C., Widmayer, P.: Inapproximability results for guarding polygons and terrains. Algorithmica 31(1), 79\u2013113 (2001)","journal-title":"Algorithmica"},{"issue":"2","key":"26_CR18","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1142\/S0218195909002897","volume":"19","author":"KM Elbassioni","year":"2009","unstructured":"Elbassioni, K.M., Fishkin, A.V., Sitters, R.: Approximation algorithms for the Euclidean traveling salesman problem with discrete and continuous neighborhoods. Int. J. Comput. Geom. Appl. 19(2), 173\u2013193 (2009)","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"26_CR19","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U Feige","year":"1998","unstructured":"Feige, U.: A threshold of $$\\ln n$$ for approximating set cover. J. ACM 45, 634\u2013652 (1998)","journal-title":"J. ACM"},{"key":"26_CR20","doi-asserted-by":"crossref","unstructured":"Garey, M.R., Graham, R.L., Johnson, D.S.: Some NP-complete geometric problems. In: Proceedings of the 8th ACM Symposium on Theory of Computing (STOC), pp. 10\u201322 (1976)","DOI":"10.1145\/800113.803626"},{"key":"26_CR21","volume-title":"Computers and Intractability: A Guide to the Theory of $$ NP$$-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of $$ NP$$-Completeness. W. H. Freeman and Company, New York (1979)"},{"issue":"1\u20134","key":"26_CR22","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1016\/S0020-0255(97)10033-0","volume":"105","author":"LP Gewali","year":"1998","unstructured":"Gewali, L.P., Ntafos, S.C.: Watchman routes in the presence of a pair of convex polygons. J. Inf. Sci. 105(1\u20134), 123\u2013149 (1998)","journal-title":"J. Inf. Sci."},{"issue":"4","key":"26_CR23","first-page":"469","volume":"6","author":"J Gudmundsson","year":"1999","unstructured":"Gudmundsson, J., Levcopoulos, C.: A fast approximation algorithm for TSP with neighborhoods. Nord. J. Comput. 6(4), 469 (1999)","journal-title":"Nord. J. Comput."},{"issue":"2","key":"26_CR24","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1007\/s00454-014-9656-8","volume":"53","author":"DG Kirkpatrick","year":"2015","unstructured":"Kirkpatrick, D.G.: An $$o(\\lg \\lg )$$-approximation algorithm for multi-guarding galleries. Discret. Comput. Geom. 53(2), 327\u2013343 (2015)","journal-title":"Discret. Comput. Geom."},{"key":"26_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1007\/3-540-13883-8_78","volume-title":"Foundations of Software Technology and Theoretical Computer Science","author":"C Levcopoulos","year":"1984","unstructured":"Levcopoulos, C., Lingas, A.: Bounds on the length of convex partitions of polygons. In: Joseph, M., Shyamasundar, R. (eds.) FSTTCS. LNCS, vol. 181, pp. 279\u2013295. Springer, Heidelberg (1984). https:\/\/doi.org\/10.1007\/3-540-13883-8_78"},{"issue":"5","key":"26_CR26","doi-asserted-by":"publisher","first-page":"960","DOI":"10.1145\/185675.306789","volume":"41","author":"C Lund","year":"1994","unstructured":"Lund, C., Yannakakis, M.: On the hardness of approximating minimization problems. J. ACM 41(5), 960\u2013981 (1994)","journal-title":"J. ACM"},{"key":"26_CR27","doi-asserted-by":"crossref","unstructured":"Mata, C.S., Mitchell, J.S.B.: Approximation algorithms for geometric tour and network design problems. In: Proceedings of the 11th ACM Symposium on Computational Geometry (SoCG), pp. 360\u2013369 (1995)","DOI":"10.1145\/220279.220318"},{"issue":"4","key":"26_CR28","doi-asserted-by":"publisher","first-page":"1298","DOI":"10.1137\/S0097539796309764","volume":"28","author":"JSB Mitchell","year":"1999","unstructured":"Mitchell, J.S.B.: Guillotine subdivisions approximate polygonal subdivisions: a simple polynomial-time approximation scheme for geometric TSP, $$k$$-MST, and related problems. SIAM J. Comput. 28(4), 1298\u20131309 (1999)","journal-title":"SIAM J. Comput."},{"key":"26_CR29","doi-asserted-by":"crossref","unstructured":"Mitchell, J.S.B.: Geometric shortest paths and network optimization. In: Handbook of Computational Geometry, pp. 633\u2013701. Elsevier (2000)","DOI":"10.1016\/B978-044482537-7\/50016-4"},{"key":"26_CR30","doi-asserted-by":"crossref","unstructured":"Mitchell, J.S.B.: Approximating watchman routes. In: Proceedings of the 24th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 844\u2013855 (2013)","DOI":"10.1137\/1.9781611973105.60"},{"key":"26_CR31","unstructured":"Mitchell, J.S.B.: Shortest paths and networks. In: Handbook of Discrete and Computational Geometry, 3rd (edn.), vol. 31, pp. 811\u2013848. CRC Press (2017)"},{"key":"26_CR32","doi-asserted-by":"crossref","unstructured":"Moshkovitz, D.: The projection games conjecture and the $${\\sf NP}$$-hardness of $$\\ln n$$-approximating set-cover. Theory Comput. 11, 221\u2013235 (2015)","DOI":"10.4086\/toc.2015.v011a007"},{"key":"26_CR33","unstructured":"Nelson, J.: A note on set cover inapproximability independent of universe size. In: Electronic Colloquium Computational Complexity TR07-105 (2007)"},{"issue":"2","key":"26_CR34","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1142\/S0218195920500053","volume":"30","author":"BJ Nilsson","year":"2020","unstructured":"Nilsson, B.J., \u017byli\u0144ski, P.: How to keep an eye on small things. Int. J. Comput. Geom. Appl. 30(2), 97\u2013120 (2020)","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"26_CR35","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/0925-7721(92)90014-J","volume":"1","author":"SC Ntafos","year":"1992","unstructured":"Ntafos, S.C.: Watchman routes under limited visibility. Comput. Geom. 1, 149\u2013170 (1992)","journal-title":"Comput. Geom."},{"issue":"8","key":"26_CR36","doi-asserted-by":"publisher","first-page":"474","DOI":"10.1007\/BF01910637","volume":"10","author":"SC Ntafos","year":"1994","unstructured":"Ntafos, S.C., Gewali, L.P.: External watchman routes. Vis. Comput. 10(8), 474\u2013483 (1994)","journal-title":"Vis. Comput."},{"key":"26_CR37","unstructured":"O\u2019Rourke, J.: Visibility. In: Handbook of Discrete and Computational Geometry, 3rd (edn.) vol. 33, pp. 875\u2013896. CRC Press (2017)"},{"key":"26_CR38","unstructured":"O\u2019Rourke, J., Suri, S., T\u00f3th, C.D.: Polygons. In: Handbook of Discrete and Computational Geometry, 3rd (edn.), vol. 30, pp. 787\u2013810. CRC Press (2017)"},{"issue":"3","key":"26_CR39","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0304-3975(77)90012-3","volume":"4","author":"CH Papadimitriou","year":"1977","unstructured":"Papadimitriou, C.H.: The Euclidean traveling salesman problem is NP-complete. Theor. Comput. Sci. 4(3), 237\u2013244 (1977)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"26_CR40","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1007\/s00037-005-0200-3","volume":"14","author":"S Safra","year":"2006","unstructured":"Safra, S., Schwartz, O.: On the complexity of approximating tsp with neighborhoods and related problems. Comput. Complex. 14(4), 281\u2013307 (2006)","journal-title":"Comput. Complex."},{"key":"26_CR41","first-page":"6","volume":"1","author":"PR Scott","year":"2000","unstructured":"Scott, P.R., Awyong, P.W.: Inequalities for convex sets. J. Inequalities Pure Appl. Math. 1, 6 (2000)","journal-title":"J. Inequalities Pure Appl. Math."},{"issue":"1","key":"26_CR42","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/S0020-0190(00)00146-0","volume":"77","author":"X Tan","year":"2001","unstructured":"Tan, X.: Fast computation of shortest watchman routes in simple polygons. Inf. Process. Lett. 77(1), 27\u201333 (2001)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"26_CR43","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1016\/j.tcs.2007.05.021","volume":"384","author":"X Tan","year":"2007","unstructured":"Tan, X.: A linear-time 2-approximation algorithm for the watchman route problem for simple polygons. Theor. Comput. Sci. 384(1), 92\u2013103 (2007)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"26_CR44","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1142\/S0218195999000212","volume":"9","author":"X Tan","year":"1999","unstructured":"Tan, X., Hirata, T., Inagaki, Y.: Corrigendum to \u201cAn incremental algorithm for constructing shortest watchman routes\u2019\u2019. Int. J. Comput. Geom. Appl. 9(3), 319\u2013323 (1999)","journal-title":"Int. J. Comput. Geom. Appl."}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-38906-1_26","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,7,27]],"date-time":"2023-07-27T16:08:13Z","timestamp":1690474093000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-38906-1_26"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"ISBN":["9783031389054","9783031389061"],"references-count":44,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-38906-1_26","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2023]]},"assertion":[{"value":"28 July 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WADS","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Algorithms and Data Structures Symposium","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Montreal, QC","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Canada","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2023","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"31 July 2023","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2 August 2023","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"18","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"wads2023","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/wads.org\/","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":"92","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":"47","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":"51% - 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.1","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":"10","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)"}}]}}