The VC-Dimension of Visibility on the Boundary of a Simple Polygon

1. 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–310. Society for Industrial and Applied Mathematics, Philadelphia, PA (2009)

   Google Scholar 

2. Aronov, B., Ezra, E., Sharir, M.: Small-size epsilon-nets for axis-parallel rectangles and boxes. SIAM J. Comput. 39(7), 3248–3282 (2010)

   Article  MathSciNet  MATH  Google Scholar 

3. 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–304. ACM, New York (1993)

   Google Scholar 

4. Brönnimann, H., Goodrich, M.: Almost optimal set covers in finite VC-dimension. Discrete Comput. Geom 14, 463 (1995)

   Article  MathSciNet  MATH  Google Scholar 

5. Feige, U., Halldórsson, M.M., Kortsarz, G., Srinivasan, A.: Approximating the domatic number. SIAM J. Comput. 32(1), 172–195 (2003)

   Article  MathSciNet  MATH  Google Scholar 

6. Gibson, M., Krohn, E., Wang, Q.: On the VC-dimension of visibility in monotone polygons. In: 26th Canadian Conference on Computational Geometry (CCCG) (2014)

   Google Scholar 

7. Gilbers, A.: VC-dimension of perimeter visibility domains. Inf. Process. Lett. 114(12), 696–699 (2014)

   Article  MathSciNet  MATH  Google Scholar 

8. Gilbers, A., Klein, R.: A new upper bound for the VC-dimension of visibility regions. Comput. Geom. 47(1), 61–74 (2014)

   Article  MathSciNet  MATH  Google Scholar 

9. Johnson, D.S.: Approximation algorithms for combinatorial problems. In: Proceedings of the Fifth Annual ACM Symposium on Theory of Computing, STOC 1973, pp. 38–49. ACM, New York (1973)

   Google Scholar 

10. King, J.: VC-dimension of visibility on terrains. In: CCCG (2008)

    Google Scholar 

11. Lund, C., Yannakakis, M.: On the hardness of approximating minimization problems. J. ACM 41(5), 960–981 (1994)

    Article  MathSciNet  MATH  Google Scholar 

12. 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–484. ACM, New York (1997)

    Google Scholar 

13. Valtr, P.: Guarding galleries where no point sees a small area. Israel J. Math. 104(1), 1–16 (1998)

    Article  MathSciNet  MATH  Google Scholar 

14. Varadarajan, K.R.: Epsilon nets and union complexity. In: Symposium on Computational Geometry, pp. 11–16 (2009)

    Google Scholar 

Download references