{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:05:22Z","timestamp":1740107122063,"version":"3.37.3"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2023,9,14]],"date-time":"2023-09-14T00:00:00Z","timestamp":1694649600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,9,14]],"date-time":"2023-09-14T00:00:00Z","timestamp":1694649600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"name":"NFS","award":["DMS-1800734"],"award-info":[{"award-number":["DMS-1800734"]}]},{"name":"PAPIIT","award":["IN105221"],"award-info":[{"award-number":["IN105221"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Graphs and Combinatorics"],"published-print":{"date-parts":[[2023,10]]},"DOI":"10.1007\/s00373-023-02707-y","type":"journal-article","created":{"date-parts":[[2023,9,14]],"date-time":"2023-09-14T13:50:11Z","timestamp":1694699411000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Minimizing Visible Edges in Polyhedra"],"prefix":"10.1007","volume":"39","author":[{"given":"Csaba D.","family":"T\u00f3th","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jorge","family":"Urrutia","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6145-4602","authenticated-orcid":false,"given":"Giovanni","family":"Viglietta","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,9,14]]},"reference":[{"issue":"1","key":"2707_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3188745.3188868","volume":"69","author":"M Abrahamsen","year":"2022","unstructured":"Abrahamsen, M., Adamaszek, A., Miltzow, T.: The art gallery problem is $$\\exists \\mathbb{R} $$-complete. J. ACM 69(1), 1\u201370 (2022). https:\/\/doi.org\/10.1145\/3188745.3188868","journal-title":"J. ACM"},{"issue":"1","key":"2707_CR2","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1007\/s004540010058","volume":"24","author":"A Below","year":"2000","unstructured":"Below, A., Brehm, U., De Loera, J.A., Richter-Gebert, J.: Minimal simplicial dissections and triangulations of convex 3-polytopes. Discrete Comput. Geom. 24(1), 35\u201348 (2000). https:\/\/doi.org\/10.1007\/s004540010058","journal-title":"Discrete Comput. Geom."},{"issue":"2","key":"2707_CR3","doi-asserted-by":"publisher","first-page":"134","DOI":"10.1016\/S0196-6774(03)00092-0","volume":"50","author":"A Below","year":"2004","unstructured":"Below, A., De Loera, J.A., Richter-Gebert, J.: The complexity of finding small triangulations of convex 3-polytopes. J. Algorithms 50(2), 134\u2013167 (2004). https:\/\/doi.org\/10.1016\/S0196-6774(03)00092-0","journal-title":"J. Algorithms"},{"unstructured":"Benbernou, N.\u00a0M., Demaine, E.\u00a0D., Demaine, M.\u00a0L., Kurdia, A., O\u2019Rourke, J., Toussaint, G.\u00a0T., Urrutia, J., Viglietta, G.: Edge-guarding orthogonal polyhedra. In: Proceedings of the 23rd Canadian Conference on Computational Geometry (CCCG 2011), pp. 461\u2013466, Toronto, ON (2011). http:\/\/2011.cccg.ca\/PDFschedule\/papers\/paper50.pdf","key":"2707_CR4"},{"key":"2707_CR5","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1007\/s13366-015-0248-4","volume":"57","author":"A Bezdek","year":"2016","unstructured":"Bezdek, A., Carrigan, B.: On nontriangulable polyhedra. Contrib. Algebra Geom. 57, 51\u201366 (2016). https:\/\/doi.org\/10.1007\/s13366-015-0248-4","journal-title":"Contrib. Algebra Geom."},{"key":"2707_CR6","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511816574","volume-title":"The Art of Mathematics: Coffee Time in Memphis","author":"B Bollob\u00e1s","year":"2006","unstructured":"Bollob\u00e1s, B.: The Art of Mathematics: Coffee Time in Memphis. Cambridge University Press, Cambridge (2006). https:\/\/doi.org\/10.1017\/CBO9780511816574"},{"doi-asserted-by":"publisher","unstructured":"Bonnet, \u00c9., Miltzow, T.: An approximation algorithm for the art gallery problem. In: Proceedings of the 33rd International Symposium on Computational Geometry (SoCG 2017), volume\u00a077 of LIPIcs, pp. 20:1\u201320:15. Schloss Dagstuhl (2017). https:\/\/doi.org\/10.4230\/LIPIcs.SoCG.2017.20","key":"2707_CR7","DOI":"10.4230\/LIPIcs.SoCG.2017.20"},{"key":"2707_CR8","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1016\/j.cam.2015.04.018","volume":"288","author":"MN Bygi","year":"2015","unstructured":"Bygi, M.N., Daneshpajouh, S., Alipour, S., Ghodsi, M.: Weak visibility counting in simple polygons. J. Comput. Appl. Math. 288, 215\u2013222 (2015). https:\/\/doi.org\/10.1016\/j.cam.2015.04.018","journal-title":"J. Comput. Appl. Math."},{"key":"2707_CR9","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2022.101859","volume":"104","author":"J Cano","year":"2022","unstructured":"Cano, J., T\u00f3th, C.D., Urrutia, J., Viglietta, G.: Edge guards for polyhedra in three-space. Comput. Geom. 104, 101859 (2022). https:\/\/doi.org\/10.1016\/j.comgeo.2022.101859","journal-title":"Comput. Geom."},{"issue":"3","key":"2707_CR10","doi-asserted-by":"publisher","first-page":"488","DOI":"10.1137\/0213031","volume":"13","author":"B Chazelle","year":"1984","unstructured":"Chazelle, B.: Convex partitions of polyhedra: A lower bound and worst-case optimal algorithm. SIAM J. Comput. 13(3), 488\u2013507 (1984). https:\/\/doi.org\/10.1137\/0213031","journal-title":"SIAM J. Comput."},{"issue":"1","key":"2707_CR11","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/0095-8956(75)90061-1","volume":"18","author":"V Chv\u00e1tal","year":"1975","unstructured":"Chv\u00e1tal, V.: A combinatorial theorem in plane geometry. J. Comb. Theory B 18(1), 39\u201341 (1975). https:\/\/doi.org\/10.1016\/0095-8956(75)90061-1","journal-title":"J. Comb. Theory B"},{"issue":"5","key":"2707_CR12","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1016\/0925-7721(95)00008-9","volume":"5","author":"M de Berg","year":"1996","unstructured":"de Berg, M.: Generalized hidden surface removal. Comput. Geom. 5(5), 249\u2013276 (1996). https:\/\/doi.org\/10.1016\/0925-7721(95)00008-9","journal-title":"Comput. Geom."},{"issue":"03","key":"2707_CR13","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1142\/S0218195997000120","volume":"7","author":"M de Berg","year":"1997","unstructured":"de Berg, M., Halperin, D., Overmars, M., van Kreveld, M.: Sparse arrangements and the number of views of polyhedral scenes. Int. J. Comput. Geom. Appl. 7(03), 175\u2013195 (1997). https:\/\/doi.org\/10.1142\/S0218195997000120","journal-title":"Int. J. Comput. Geom. Appl."},{"issue":"8","key":"2707_CR14","doi-asserted-by":"publisher","first-page":"758","DOI":"10.1016\/j.comgeo.2008.04.007","volume":"42","author":"J Demouth","year":"2009","unstructured":"Demouth, J., Devillers, O., Everett, H., Glisse, M., Lazard, S., Seidel, R.: On the complexity of umbra and penumbra. Comput. Geom. 42(8), 758\u2013771 (2009). https:\/\/doi.org\/10.1016\/j.comgeo.2008.04.007","journal-title":"Comput. Geom."},{"issue":"02","key":"2707_CR15","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1142\/S0218195999000145","volume":"9","author":"EF Grove","year":"1999","unstructured":"Grove, E.F., Murali, T.M., Vitter, J.S.: The object complexity model for hidden-surface removal. Int. J. Comput. Geom. Appl. 9(02), 207\u2013217 (1999). https:\/\/doi.org\/10.1142\/S0218195999000145","journal-title":"Int. J. Comput. Geom. Appl."},{"doi-asserted-by":"publisher","unstructured":"Gudmundsson, J., Morin, P.: Visibility, Planar: Testing and counting. In: Proceedings of the 26th Annual Symposium on Computational Geometry (SoCG 2010), pp. 77\u201386. ACM Press (2010). https:\/\/doi.org\/10.1145\/1810959.1810973","key":"2707_CR16","DOI":"10.1145\/1810959.1810973"},{"issue":"7","key":"2707_CR17","doi-asserted-by":"publisher","first-page":"1521","DOI":"10.1587\/transinf.2016EDL8251","volume":"100","author":"C Iwamoto","year":"2017","unstructured":"Iwamoto, C.: Finding the minimum number of open-edge guards in an orthogonal polygon is NP-hard. IEICE Trans. Inf. Syst. 100(7), 1521\u20131525 (2017). https:\/\/doi.org\/10.1587\/transinf.2016EDL8251","journal-title":"IEICE Trans. Inf. Syst."},{"issue":"2","key":"2707_CR18","doi-asserted-by":"publisher","first-page":"435","DOI":"10.2197\/ipsjjip.20.435","volume":"7","author":"C Iwamoto","year":"2012","unstructured":"Iwamoto, C., Kishi, J., Morita, K.: Lower bound of face guards of polyhedral terrains. Inf. Media Technol. 7(2), 435\u2013437 (2012). https:\/\/doi.org\/10.2197\/ipsjjip.20.435","journal-title":"Inf. Media Technol."},{"issue":"11","key":"2707_CR19","doi-asserted-by":"publisher","first-page":"2716","DOI":"10.1587\/transinf.e95.d.2716","volume":"95","author":"C Iwamoto","year":"2012","unstructured":"Iwamoto, C., Kitagaki, Y., Morita, K.: Finding the minimum number of face guards is NP-hard. IEICE Trans. Inf. Syst. 95(11), 2716\u20132719 (2012). https:\/\/doi.org\/10.1587\/transinf.e95.d.2716","journal-title":"IEICE Trans. Inf. Syst."},{"issue":"2","key":"2707_CR20","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1137\/0604020","volume":"4","author":"J Kahn","year":"1983","unstructured":"Kahn, J., Klawe, M., Kleitman, D.: Traditional galleries require fewer watchmen. SIAM J. Algebraic Discrete Methods 4(2), 194\u2013206 (1983). https:\/\/doi.org\/10.1137\/0604020","journal-title":"SIAM J. Algebraic Discrete Methods"},{"issue":"5","key":"2707_CR21","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1016\/S0020-0190(01)00228-9","volume":"81","author":"N Kitsios","year":"2002","unstructured":"Kitsios, N., Makris, C., Sioutas, S., Tsakalidis, A.K., Tsaknakis, J., Vassiliadis, B.: An optimal algorithm for reporting visible rectangles. Inf. Process. Lett. 81(5), 283\u2013288 (2002). https:\/\/doi.org\/10.1016\/S0020-0190(01)00228-9","journal-title":"Inf. Process. Lett."},{"unstructured":"Kokado, K., T\u00f3th, C.\u00a0D.: Nonrealizable planar and spherical occlusion diagrams. In: Abstract of the 24th Japan Conference on Discrete and Computational Geometry, Graphs, and Games (JCDCG$$^3$$ 2022), pp. 60\u201361 (2022)","key":"2707_CR22"},{"key":"2707_CR23","first-page":"415","volume-title":"Handbook of Discrete and Computational Geometry","author":"CW Lee","year":"2017","unstructured":"Lee, C.W., Santos, F.: Subdivisions and triangulations of polytopes. In: Goodman, J.E., O\u2019Rourke, J., T\u00f3th, C.D. (eds.) Handbook of Discrete and Computational Geometry, 3rd edn., pp. 415\u2013447. Chapman and Hall\/CRC, Boca Raton (2017)","edition":"3"},{"issue":"2","key":"2707_CR24","doi-asserted-by":"publisher","first-page":"276","DOI":"10.1109\/TIT.1986.1057165","volume":"32","author":"D-T Lee","year":"1986","unstructured":"Lee, D.-T., Lin, A.K.: Computational complexity of art gallery problems. IEEE Trans. Inf. Theory 32(2), 276\u2013282 (1986). https:\/\/doi.org\/10.1109\/TIT.1986.1057165","journal-title":"IEEE Trans. Inf. Theory"},{"key":"2707_CR25","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-12971-1","volume-title":"Triangulations: Structures for Algorithms and Applications, Volume 25 of Algorithms and Computation in Mathematics","author":"JA Loera","year":"2010","unstructured":"Loera, J.A., Rambau, J., Santos, F.: Triangulations: Structures for Algorithms and Applications, Volume 25 of Algorithms and Computation in Mathematics. Springer, Berlin (2010)"},{"issue":"1","key":"2707_CR26","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1145\/27625.27627","volume":"6","author":"M McKenna","year":"1987","unstructured":"McKenna, M.: Worst-case optimal hidden-surface removal. ACM Trans. Graphics (TOG) 6(1), 19\u201328 (1987). https:\/\/doi.org\/10.1145\/27625.27627","journal-title":"ACM Trans. Graphics (TOG)"},{"issue":"3","key":"2707_CR27","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1016\/j.comgeo.2006.11.001","volume":"39","author":"E Moet","year":"2008","unstructured":"Moet, E., Knauer, C., van Kreveld, M.: Visibility maps of segments and triangles in 3D. Comput. Geom. 39(3), 163\u2013177 (2008). https:\/\/doi.org\/10.1016\/j.comgeo.2006.11.001","journal-title":"Comput. Geom."},{"key":"2707_CR28","volume-title":"Art Gallery Theorems and Algorithms, Volume 3 of International Series of Monographs on Computer Science","author":"J O\u2019Rourke","year":"1987","unstructured":"O\u2019Rourke, J.: Art Gallery Theorems and Algorithms, Volume 3 of International Series of Monographs on Computer Science. Oxford University Press, New York (1987)"},{"key":"2707_CR29","first-page":"875","volume-title":"Handbook of Discrete and Computational Geometry","author":"J O\u2019Rourke","year":"2017","unstructured":"O\u2019Rourke, J.: Visibility. In: Goodman, J.E., O\u2019Rourke, J., T\u00f3th, C.D. (eds.) Handbook of Discrete and Computational Geometry, 3rd edn., pp. 875\u2013896. Chapman and Hall\/CRC, Boca Raton (2017)","edition":"3"},{"key":"2707_CR30","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1007\/BF02187840","volume":"7","author":"J Ruppert","year":"1992","unstructured":"Ruppert, J., Seidel, R.: On the difficulty of triangulating three-dimensional nonconvex polyhedra. Discrete Comput. Geom. 7, 227\u2013253 (1992). https:\/\/doi.org\/10.1007\/BF02187840","journal-title":"Discrete Comput. Geom."},{"key":"2707_CR31","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1007\/BF01451597","volume":"98","author":"E Sch\u00f6nhardt","year":"1928","unstructured":"Sch\u00f6nhardt, E.: \u00dcber die Zerlegung von Dreieckspolyedern in Tetraeder. Math. Ann. 98, 309\u2013312 (1928). https:\/\/doi.org\/10.1007\/BF01451597","journal-title":"Math. Ann."},{"unstructured":"Souvaine, D.\u00a0L., Veroy, R., Winslow, A.: Face guards for art galleries. In: Proceedings of the XIV Spanish Meeting on Computational Geometry, pp. 39\u201342, Alcal\u00e1 de Henares (2011)","key":"2707_CR32"},{"key":"2707_CR33","doi-asserted-by":"publisher","first-page":"973","DOI":"10.1016\/B978-044482537-7\/50023-1","volume-title":"Handbook of Computational Geometry","author":"J Urrutia","year":"2000","unstructured":"Urrutia, J.: Art gallery and illumination problems. In: Handbook of Computational Geometry, pp. 973\u20131027. North-Holland, Amsterdam (2000)"},{"issue":"8","key":"2707_CR34","doi-asserted-by":"publisher","first-page":"833","DOI":"10.1016\/j.comgeo.2014.04.009","volume":"47","author":"G Viglietta","year":"2014","unstructured":"Viglietta, G.: Face-guarding polyhedra. Comput. Geom. 47(8), 833\u2013846 (2014). https:\/\/doi.org\/10.1016\/j.comgeo.2014.04.009","journal-title":"Comput. Geom."},{"key":"2707_CR35","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2019.101589","volume":"86","author":"G Viglietta","year":"2020","unstructured":"Viglietta, G.: Optimally guarding 2-reflex orthogonal polyhedra by reflex edge guards. Comput. Geom. 86, 101589 (2020). https:\/\/doi.org\/10.1016\/j.comgeo.2019.101589","journal-title":"Comput. Geom."},{"doi-asserted-by":"publisher","unstructured":"Viglietta, G.: A theory of spherical diagrams. Comput. Geom. Topol. 2(2), 2:1\u20132:24 (2023). https:\/\/doi.org\/10.57717\/cgt.v2i2.30","key":"2707_CR36","DOI":"10.57717\/cgt.v2i2.30"}],"container-title":["Graphs and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-023-02707-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00373-023-02707-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-023-02707-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,12]],"date-time":"2023-10-12T04:05:37Z","timestamp":1697083537000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00373-023-02707-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,9,14]]},"references-count":36,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2023,10]]}},"alternative-id":["2707"],"URL":"https:\/\/doi.org\/10.1007\/s00373-023-02707-y","relation":{},"ISSN":["0911-0119","1435-5914"],"issn-type":[{"type":"print","value":"0911-0119"},{"type":"electronic","value":"1435-5914"}],"subject":[],"published":{"date-parts":[[2023,9,14]]},"assertion":[{"value":"2 June 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 August 2023","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 August 2023","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 September 2023","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no relevant financial or non-financial interests to disclose.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"111"}}