{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,30]],"date-time":"2026-04-30T03:35:45Z","timestamp":1777520145021,"version":"3.51.4"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2018,4,16]],"date-time":"2018-04-16T00:00:00Z","timestamp":1523836800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"ERC","award":["306992 (S.S.)"],"award-info":[{"award-number":["306992 (S.S.)"]}]},{"name":"European Research Council under the European Union's Seventh Framework Programme","award":["FP\/2007-2013"],"award-info":[{"award-number":["FP\/2007-2013"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2018,4,30]]},"abstract":"<jats:p>\n            Given a 1.5-dimensional terrain\n            <jats:italic>T<\/jats:italic>\n            , also known as an\n            <jats:italic>x<\/jats:italic>\n            -monotone polygonal chain, the T\n            <jats:sc>errain<\/jats:sc>\n            G\n            <jats:sc>uarding<\/jats:sc>\n            problem seeks a set of points of minimum size on\n            <jats:italic>T<\/jats:italic>\n            that\n            <jats:italic>guards<\/jats:italic>\n            all of the points on\n            <jats:italic>T<\/jats:italic>\n            . Here, we say that a point\n            <jats:italic>p<\/jats:italic>\n            guards a point\n            <jats:italic>q<\/jats:italic>\n            if no point of the line segment\n            <jats:italic>pq<\/jats:italic>\n            is strictly below\n            <jats:italic>T<\/jats:italic>\n            . The T\n            <jats:italic>errain<\/jats:italic>\n            G\n            <jats:italic>uarding<\/jats:italic>\n            problem has been extensively studied for over 20 years. In 2005 it was already established that this problem admits a constant-factor approximation algorithm (SODA 2005). However, only in 2010 King and Krohn (SODA 2010) finally showed that T\n            <jats:sc>errain<\/jats:sc>\n            G\n            <jats:sc>uarding<\/jats:sc>\n            is NP-hard. In spite of the remarkable developments in approximation algorithms for T\n            <jats:sc>errain<\/jats:sc>\n            G\n            <jats:sc>uarding<\/jats:sc>\n            , next to nothing is known about its parameterized complexity. In particular, the most intriguing open questions in this direction ask whether, if parameterized by the size\n            <jats:italic>k<\/jats:italic>\n            of a solution guard set, it admits a subexponential-time algorithm and whether it is fixed-parameter tractable. In this article, we answer the first question affirmatively by developing an\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\n              <jats:italic>O<\/jats:italic>\n              (\u221a\n              <jats:italic>k<\/jats:italic>\n              )\n            <\/jats:sup>\n            -time algorithm for both D\n            <jats:sc>iscrete<\/jats:sc>\n            T\n            <jats:sc>errain<\/jats:sc>\n            G\n            <jats:sc>uarding<\/jats:sc>\n            and C\n            <jats:sc>ontinuous<\/jats:sc>\n            T\n            <jats:sc>errain<\/jats:sc>\n            G\n            <jats:sc>uarding<\/jats:sc>\n            . We also make non-trivial progress with respect to the second question: we show that D\n            <jats:sc>iscrete<\/jats:sc>\n            O\n            <jats:sc>rthogonal<\/jats:sc>\n            T\n            <jats:sc>errain<\/jats:sc>\n            G\n            <jats:sc>uarding<\/jats:sc>\n            , a well-studied special case of T\n            <jats:sc>errain<\/jats:sc>\n            G\n            <jats:sc>uarding<\/jats:sc>\n            , is fixed-parameter tractable.\n          <\/jats:p>","DOI":"10.1145\/3186897","type":"journal-article","created":{"date-parts":[[2018,4,18]],"date-time":"2018-04-18T17:21:50Z","timestamp":1524072110000},"page":"1-20","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":11,"title":["Exact Algorithms for Terrain Guarding"],"prefix":"10.1145","volume":"14","author":[{"given":"Pradeesha","family":"Ashok","sequence":"first","affiliation":[{"name":"International Institute of Information Technology Bangalore, Bengaluru, Karnataka, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fedor V.","family":"Fomin","sequence":"additional","affiliation":[{"name":"University of Bergen, Bergen, Norway"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sudeshna","family":"Kolay","sequence":"additional","affiliation":[{"name":"Eindhoven University of Technology, Netherlands, Eindhoven, Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[{"name":"University of Bergen and Institute of Mathematical Sciences, Tharamani, Chennai, Tamil Nadu, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Meirav","family":"Zehavi","sequence":"additional","affiliation":[{"name":"Ben-Gurion University, Beersheba, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,4,16]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02570710"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0116-5"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704446384"},{"key":"e_1_2_1_4_1","unstructured":"\u00c9douard Bonnet and Panos Giannopoulos. 2017. Orthogonal terrain guarding is NP-complete. CoRR abs\/1710.00386. http:\/\/arxiv.org\/abs\/1710.00386.  \u00c9douard Bonnet and Panos Giannopoulos. 2017. Orthogonal terrain guarding is NP-complete. CoRR abs\/1710.00386. http:\/\/arxiv.org\/abs\/1710.00386."},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the 24th Annual European Symposium on Algorithms, ESA (LIPIcs)","volume":"57","author":"Bonnet \u00c9douard","year":"2016","unstructured":"\u00c9douard Bonnet and Tillmann Miltzow . 2016 . Parameterized hardness of art gallery problems . In Proceedings of the 24th Annual European Symposium on Algorithms, ESA (LIPIcs) , Vol. 57 . 19:1--19:17. \u00c9douard Bonnet and Tillmann Miltzow. 2016. Parameterized hardness of art gallery problems. In Proceedings of the 24th Annual European Symposium on Algorithms, ESA (LIPIcs), Vol. 57. 19:1--19:17."},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the 7th Canadian Conference on Computational Geometry (CCCG). 133--138","author":"Chen Danny Z.","year":"1995","unstructured":"Danny Z. Chen , Vladimir Estivill-Castro , and Jorge Urrutia . 1995 . Optimal guarding of polygons and monotone chains . In Proceedings of the 7th Canadian Conference on Computational Geometry (CCCG). 133--138 . Danny Z. Chen, Vladimir Estivill-Castro, and Jorge Urrutia. 1995. Optimal guarding of polygons and monotone chains. In Proceedings of the 7th Canadian Conference on Computational Geometry (CCCG). 133--138."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-006-1273-8"},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","unstructured":"M. Cygan F. V. Fomin L. Kowalik D. Lokshtanov D. Marx M. Pilipczuk M. Pilipczuk and S. Saurabh. 2015. Parameterized Algorithms. Springer.   M. Cygan F. V. Fomin L. Kowalik D. Lokshtanov D. Marx M. Pilipczuk M. Pilipczuk and S. Saurabh. 2015. Parameterized Algorithms. Springer.","DOI":"10.1007\/978-3-319-21275-3"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1101821.1101823"},{"key":"e_1_2_1_10_1","volume-title":"Graph Theory","author":"Diestel R.","unstructured":"R. Diestel . 2012. Graph Theory ( 4 th ed.). Springer . R. Diestel. 2012. Graph Theory (4th ed.). Springer.","edition":"4"},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","unstructured":"R. Downey and M. R. Fellows. 2013. Fundamentals of Parameterized Complexity. Springer.   R. Downey and M. R. Fellows. 2013. Fundamentals of Parameterized Complexity. Springer.","DOI":"10.1007\/978-1-4471-5559-1"},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the 27th Canadian Conference on Computational Geometry (CCCG).","author":"Durocher Stephane","year":"2015","unstructured":"Stephane Durocher , Pak Ching Li , and Saeed Mehrabi . 2015 . Guarding orthogonal terrains . In Proceedings of the 27th Canadian Conference on Computational Geometry (CCCG). Stephane Durocher, Pak Ching Li, and Saeed Mehrabi. 2015. Guarding orthogonal terrains. In Proceedings of the 27th Canadian Conference on Computational Geometry (CCCG)."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/3118782.3119223"},{"key":"e_1_2_1_14_1","first-page":"108","article-title":"On characterizing terrain visibility graphs","volume":"6","author":"Evans William S.","year":"2015","unstructured":"William S. Evans and Noushin Saeedi . 2015 . On characterizing terrain visibility graphs . Journal of Computational Geometry 6 , 1 (2015), 108 -- 141 . William S. Evans and Noushin Saeedi. 2015. On characterizing terrain visibility graphs. Journal of Computational Geometry 6, 1 (2015), 108--141.","journal-title":"Journal of Computational Geometry"},{"key":"e_1_2_1_15_1","first-page":"256","article-title":"The continuous 1.5D terrain guarding problem: Discretization, optimal solutions, and PTAS","volume":"7","author":"Friedrichs S.","year":"2016","unstructured":"S. Friedrichs , M. Hemmer , J. King , and C. Schmidt . 2016 . The continuous 1.5D terrain guarding problem: Discretization, optimal solutions, and PTAS . Journal of Computational Geometry 7 , 1 (2016), 256 -- 284 . S. Friedrichs, M. Hemmer, J. King, and C. Schmidt. 2016. The continuous 1.5D terrain guarding problem: Discretization, optimal solutions, and PTAS. Journal of Computational Geometry 7, 1 (2016), 256--284.","journal-title":"Journal of Computational Geometry"},{"key":"e_1_2_1_16_1","volume-title":"Visibility Algorithms in the Plane","author":"Ghosh S. K.","unstructured":"S. K. Ghosh . 2007. Visibility Algorithms in the Plane . Cambridge University Press . S. K. Ghosh. 2007. Visibility Algorithms in the Plane.Cambridge University Press."},{"key":"e_1_2_1_17_1","volume-title":"Lorentz Workshop on Fixed-Parameter Computational Geometry","author":"Giannopoulos P.","year":"2016","unstructured":"P. Giannopoulos . 2016 . Open problems: Guarding problems . Lorentz Workshop on Fixed-Parameter Computational Geometry , Leiden, the Netherlands, 12. P. Giannopoulos. 2016. Open problems: Guarding problems. Lorentz Workshop on Fixed-Parameter Computational Geometry, Leiden, the Netherlands, 12."},{"key":"e_1_2_1_18_1","first-page":"168","article-title":"Guarding terrains via local search","volume":"5","author":"Gibson M.","year":"2014","unstructured":"M. Gibson , G. Kanade , E. Krohn , and K. Varadarajan . 2014 . Guarding terrains via local search . Journal of Computational Geometry 5 , 1 (2014), 168 -- 178 . M. Gibson, G. Kanade, E. Krohn, and K. Varadarajan. 2014. Guarding terrains via local search. Journal of Computational Geometry 5, 1 (2014), 168--178.","journal-title":"Journal of Computational Geometry"},{"key":"e_1_2_1_19_1","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"Golumbic M. C.","unstructured":"M. C. Golumbic . 1980. Algorithmic Graph Theory and Perfect Graphs . Academic Press , New York . M. C. Golumbic. 1980. Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1774"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2007.02.002"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.06.028"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/11682462_58"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/100791506"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-012-9653-3"},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the 28th Canadian Conference on Computational Geometry (CCCG). 161--167","author":"Lyu Yangdi","year":"2016","unstructured":"Yangdi Lyu and Alper \u00dcng\u00f6r . 2016 . A fast 2-approximation algorithm for guarding orthogonal terrains . In Proceedings of the 28th Canadian Conference on Computational Geometry (CCCG). 161--167 . Yangdi Lyu and Alper \u00dcng\u00f6r. 2016. A fast 2-approximation algorithm for guarding orthogonal terrains. In Proceedings of the 28th Canadian Conference on Computational Geometry (CCCG). 161--167."},{"key":"e_1_2_1_27_1","unstructured":"S. Mehrabi. 2015. Guarding the vertices of an orthogonal terrain using vertex guards. arXiv:1512.08292.  S. Mehrabi. 2015. Guarding the vertices of an orthogonal terrain using vertex guards. arXiv:1512.08292."},{"key":"e_1_2_1_28_1","volume-title":"Art Gallery Theorems and Algorithms","author":"O\u2019Rourke J.","unstructured":"J. O\u2019Rourke . 1987. Art Gallery Theorems and Algorithms . Oxford University Press . J. O\u2019Rourke. 1987. Art Gallery Theorems and Algorithms. Oxford University Press."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19950410212"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/B978-044482537-7\/50023-1"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3186897","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3186897","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T19:07:32Z","timestamp":1750273652000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3186897"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,4,16]]},"references-count":30,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,4,30]]}},"alternative-id":["10.1145\/3186897"],"URL":"https:\/\/doi.org\/10.1145\/3186897","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,4,16]]},"assertion":[{"value":"2017-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-04-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}