Approximability issues of guarding a set of segments

References

• Balaban , I. J. An Optimal Algorithm for Finding Segment Intersections . Proceeding of 11-th Annual ACM Symposium on Computational Geometry . pp. 211 – 219 . Vancouver , BC
   Google Scholar
• Bentley , J. L. and Ottmann , T. A. 1979 . Algorithms for reporting and counting geometric intersections . IEEE Trans. Comput. , 28 : 643 – 647 . (doi:10.1109/TC.1979.1675432)
   Web of Science ®Google Scholar
• Brimkov , V. E. 2011 . “ Complexity and approximability issues in combinatorial image analysis ” . In Combinatorial Image Analysis , Edited by: Aggarwal , J. K. , Barneva , R. P. , Brimkov , V. E. , Koroutchev , K. N. and Korutcheva , E. R. Vol. 6636 , 4 – 8 . Berlin : Springer . Lecture Notes in Computer Science
   Google Scholar
• Brimkov , V. E. , Leach , A. , Mastroianni , M. and Wu , J. 2010 . “ Experimental studies on approximation algorithms for guarding sets of line segments ” . In Advances in Visual Computing , Edited by: Bebis , G. , Boyle , R. , Parvin , B. , Koracin , D. , Chung , R. , Hammoud , R. , Hussain , M. , Kar-Han , T. , Crawfis , R. , Thalmann , D. , Kao , D. and Avila , L. Vol. 6453 , 592 – 601 . Berlin : Springer . ISVC 2010, Part I, Lecture Notes in Computer Science
   Google Scholar
• Brimkov , V. E. , Leach , A. , Mastroianni , M. and Wu , J. 2011 . Guarding a set of line segments in the plane . Theor. Comput. Sci. , 412 : 1313 – 1324 . (doi:10.1016/j.tcs.2010.08.014)
   Web of Science ®Google Scholar
• Brimkov , V. E. , Leach , A. , Wu , J. and Mastroianni , M. 2012 . Approximation algorithms for a geometric set cover problem . Discrete Appl. Math. , 160 : 1039 – 1052 . (doi:10.1016/j.dam.2011.11.023)
   Web of Science ®Google Scholar
• Chazelle , B. M. 1983 . Reporting and counting arbitrary planar intersections Rep. CS-83-16, Department of Computer Science, Brown University, Providence, RI
   Google Scholar
• Coppersmith , D. and Vishkin , U. 1985 . Solving NP-hard problems in ‘almost trees’: Vertex cover . Discrete Appl. Math. , 10 : 27 – 45 . (doi:10.1016/0166-218X(85)90057-5)
   Web of Science ®Google Scholar
• Cormen , Th. H. , Leiserson , Ch. E. , Rivest , R. L. and Stain , C. 2001 . Introduction to Algorithms , Cambridge , MA : MIT Press & McGraw Hill .
   Google Scholar
• De Fraysseix , H. , Pach , J. and Pollack , R. Small Sets Supporting Straight-Line Embeddings of Planar Graphs . Proceedings of 20th Annual Symposium on Theory of Computing . pp. 426 – 433 . Chicago , IL
   Google Scholar
• Feige , U. 1998 . A threshold of ln n for approximating set cover . J. ACM , 45 : 314 – 318 . (doi:10.1145/285055.285059)
   Google Scholar
• Garey , M. R. and Johnson , D. S. 1979 . Computers and Intractability , San Francisco , CA : W.H. Freeman & Company .
   Google Scholar
• Gurevich , Y. , Stockmeyer , L. and Vishkin , U. 1984 . Solving NP-hard problems on graphs that are almost trees and an application to facility location problems . J. ACM , 31 : 459 – 473 . (doi:10.1145/828.322439)
   Web of Science ®Google Scholar
• Harary , F. and Uhlenbeck , G. 1953 . On the number of Husimi trees, I . Proc. Natl. Acad. Sci. USA , 39 : 315 – 322 . (doi:10.1073/pnas.39.4.315)
   PubMed Web of Science ®Google Scholar
• Husimi , K. 1950 . Note on Mayers’ theory of cluster integrals . J. Chem. Phys. , 18 : 682 – 684 . (doi:10.1063/1.1747725)
   Web of Science ®Google Scholar
• Johnson , D. B. 1975 . Finding all the elementary circuits of a directed graph . SIAM J. Comput. , 4 : 77 – 84 . (doi:10.1137/0204007)
   Google Scholar
• Karp , R. 1972 . “ Reducibility among combinatorial problems ” . In Complexity of Computer Computation , Edited by: Miller , R. E. and Thatcher , J. W. 85 – 103 . New York : Plenum Press .
   Google Scholar
• Knuth , D. E. 1998 . The Art of Computer Programming. Vol. 2: Seminumerical Algorithms , 3 , Reading , MA : Addison-Wesley .
   Google Scholar
• L'Ecuyer , P. 1994 . Uniform random number generation . Ann. Oper. Res. , 53 : 77 – 120 . (doi:10.1007/BF02136827)
   Google Scholar
• Lund , C. and Yannakakis , M. 1994 . On the hardness of approximating minimization problems . J. ACM , 41 : 960 – 981 . (doi:10.1145/185675.306789)
   Web of Science ®Google Scholar
• Micali , S. and Vazirani , V. V. An O(√|V|·|E|) Algorithm for Finding Maximum Matching in General Graphs . Proceedings of the Twenty-First Annual Symposium on the Foundations of Computer Science . pp. 17 – 27 . Long Beach , CA : IEEE .
   Google Scholar
• O'Rourke , J. 1987 . Art Gallery Theorems and Algorithms , New York : Oxford University Press .
   Google Scholar
• Papadimitriou , Ch. K. and Steiglitz , K. 1982 . Combinatorial Optimization , Englewood Cliffs , NJ : Prentice-Hall .
   Google Scholar
• Preparata , F. and Shamos , M. I. 1985 . Computational Geometry: An Introduction , New York : Springer .
   Google Scholar
• Tiernan , J. C. 1970 . “ An efficient search algorithm to find the elementary circuits of a graph ” . In Commun. ACM Vol. 13 , 722 – 726 .
   Google Scholar
• Urrutia , J. 2000 . “ Art gallery and illumination problems ” . In Handbook of Computational Geometry , Edited by: Sack , J.-R. and Urrutia , J. North Holland, Amsterdam : Elsevier .
   Google Scholar