{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,24]],"date-time":"2025-03-24T07:39:46Z","timestamp":1742801986992},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662489703"},{"type":"electronic","value":"9783662489710"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-662-48971-0_46","type":"book-chapter","created":{"date-parts":[[2015,11,26]],"date-time":"2015-11-26T04:00:57Z","timestamp":1448510457000},"page":"541-551","source":"Crossref","is-referenced-by-count":4,"title":["The VC-Dimension of Visibility on the Boundary of a Simple Polygon"],"prefix":"10.1007","author":[{"given":"Matt","family":"Gibson","sequence":"first","affiliation":[]},{"given":"Erik","family":"Krohn","sequence":"additional","affiliation":[]},{"given":"Qing","family":"Wang","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,11,27]]},"reference":[{"key":"46_CR1","doi-asserted-by":"crossref","unstructured":"Aloupis, G., Cardinal, J., Collette, S., Langerman, S., Orden, D., Ramos, P.: Decomposition of multiple coverings into more parts. In: Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2009, pp. 302\u2013310. Society for Industrial and Applied Mathematics, Philadelphia, PA (2009)","DOI":"10.1137\/1.9781611973068.34"},{"issue":"7","key":"46_CR2","doi-asserted-by":"publisher","first-page":"3248","DOI":"10.1137\/090762968","volume":"39","author":"B Aronov","year":"2010","unstructured":"Aronov, B., Ezra, E., Sharir, M.: Small-size epsilon-nets for axis-parallel rectangles and boxes. SIAM J. Comput. 39(7), 3248\u20133282 (2010)","journal-title":"SIAM J. Comput."},{"key":"46_CR3","doi-asserted-by":"crossref","unstructured":"Bellare, M., Goldwasser, S., Lund, C., Russell, A.: Efficient probabilistically checkable proofs and applications to approximations. In: Proceedings of the Twenty-fifth Annual ACM Symposium on Theory of Computing, STOC 1993, pp. 294\u2013304. ACM, New York (1993)","DOI":"10.1145\/167088.167174"},{"key":"46_CR4","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1007\/BF02570718","volume":"14","author":"H Br\u00f6nnimann","year":"1995","unstructured":"Br\u00f6nnimann, H., Goodrich, M.: Almost optimal set covers in finite VC-dimension. Discrete Comput. Geom 14, 463 (1995)","journal-title":"Discrete Comput. Geom"},{"issue":"1","key":"46_CR5","doi-asserted-by":"publisher","first-page":"172","DOI":"10.1137\/S0097539700380754","volume":"32","author":"U Feige","year":"2003","unstructured":"Feige, U., Halld\u00f3rsson, M.M., Kortsarz, G., Srinivasan, A.: Approximating the domatic number. SIAM J. Comput. 32(1), 172\u2013195 (2003)","journal-title":"SIAM J. Comput."},{"key":"46_CR6","unstructured":"Gibson, M., Krohn, E., Wang, Q.: On the VC-dimension of visibility in monotone polygons. In: 26th Canadian Conference on Computational Geometry (CCCG) (2014)"},{"issue":"12","key":"46_CR7","doi-asserted-by":"publisher","first-page":"696","DOI":"10.1016\/j.ipl.2014.06.011","volume":"114","author":"A Gilbers","year":"2014","unstructured":"Gilbers, A.: VC-dimension of perimeter visibility domains. Inf. Process. Lett. 114(12), 696\u2013699 (2014)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"46_CR8","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1016\/j.comgeo.2013.08.012","volume":"47","author":"A Gilbers","year":"2014","unstructured":"Gilbers, A., Klein, R.: A new upper bound for the VC-dimension of visibility regions. Comput. Geom. 47(1), 61\u201374 (2014)","journal-title":"Comput. Geom."},{"key":"46_CR9","doi-asserted-by":"crossref","unstructured":"Johnson, D.S.: Approximation algorithms for combinatorial problems. In: Proceedings of the Fifth Annual ACM Symposium on Theory of Computing, STOC 1973, pp. 38\u201349. ACM, New York (1973)","DOI":"10.1145\/800125.804034"},{"key":"46_CR10","unstructured":"King, J.: VC-dimension of visibility on terrains. In: CCCG (2008)"},{"issue":"5","key":"46_CR11","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":"46_CR12","doi-asserted-by":"crossref","unstructured":"Raz, R., Safra, S.: A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP. In: Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, STOC 1997, pp. 475\u2013484. ACM, New York (1997)","DOI":"10.1145\/258533.258641"},{"issue":"1","key":"46_CR13","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF02897056","volume":"104","author":"P Valtr","year":"1998","unstructured":"Valtr, P.: Guarding galleries where no point sees a small area. Israel J. Math. 104(1), 1\u201316 (1998)","journal-title":"Israel J. Math."},{"key":"46_CR14","doi-asserted-by":"crossref","unstructured":"Varadarajan, K.R.: Epsilon nets and union complexity. In: Symposium on Computational Geometry, pp. 11\u201316 (2009)","DOI":"10.1145\/1542362.1542366"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-48971-0_46","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,31]],"date-time":"2019-05-31T18:03:54Z","timestamp":1559325834000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-48971-0_46"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662489703","9783662489710"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-48971-0_46","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]}}}