List of Publications

List of Publications

  • Books:

    1. S. K. Ghosh,  Visibility algorithms in the plane,  Cambridge University Press, Cambridge, United Kingdom, 2007.

    2. S. K. Ghosh and T. Tokuyama (Eds.),  WALCOM: Algorithms and Computation,  Proceedings of the Seventh International Workshop on Algorithms and Computations, Lecture Notes in Computer Science, vol. 7748, Springer, 2013.

    3. S. K. Ghosh (Ed.),  Guest Editorial: Selected Papers from WALCOM 2013,  Journal of Graph Algorithms and Applications, vol. 17, no. 6, pp. 597-598, 2013.

    4. S. K. Ghosh and T. Tokuyama (Eds.),   Guest Editorial: Special Issue on Algorithms and Computation,  Theoretical Computer Science, vol. 555, pp. 1, 2014.

  • In Journals/Edited Volumes:

    1. S. K. Ghosh and R. K. Shyamasundar,  A linear time algorithm for obtaining the convex hull of a simple polygon, Pattern Recognition, vol. 16, pp. 587-592, 1983.

    2. S. K. Ghosh and R. K. Shyamasundar,  A linear time algorithm for computing the convex hull of an ordered crossing polygon,  Pattern Recognition, vol. 17, pp. 351-358, 1984.

    3. A. Aggarwal, S. K. Ghosh and R. K. Shyamasundar, Computational complexity of restricted polygon decompositions, Computational Morphology  (edited by G.T.Toussaint), Machine Intelligence and Pattern Recognition, vol. 6, pp. 1-11, 1988.

    4. S. K. Ghosh and A. Maheshwari,  An optimal algorithm for computing a minimum nested nonconvex polygon,  Information Processing Letters, vol. 36, pp 277-280, 1990.

    5. S. K. Ghosh,  Computing the visibility polygon from a convex set and related problems,  Journal of Algorithms, vol. 12, no. 1, pp. 75-95, 1991.

    6. S. K. Ghosh and D. M. Mount,  An output sensitive algorithm for computing visibility graphs, SIAM Journal on Computing, vol. 20, no. 5, pp. 888-910, October, 1991.

    7. S. K. Ghosh and A. Maheshwari,  An optimal parallel algorithm for computing furthest neighbors in a tree, Information Processing Letters, vol. 44, pp. 155-160, 1992.

    8. S. K. Ghosh, A. Maheshwari, S. P. Pal, S. Saluja and C. E. Veni Madhavan,  Characterizing and recognizing weak visibility polygons, Computational Geometry: Theory and Applications, vol. 3, no. 4, pp. 213-233, 1993.

    9. S. K. Ghosh, A. Maheshwari, S. P. Pal and C. E. Veni Madhavan,  An algorithm for recognizing palm polygons , Visual Computer (Special issue), vol. 10, no. 8, pp. 443-451, 1994.

    10. V. Chandru, S. K. Ghosh, A. Maheshwari, V. T. Rajan and S. Saluja,  NC-Algorithms for minimum link path and related problems, Journal of Algorithms, vol. 19, no. 2, pp. 173-203, 1995.

    11. S. K. Ghosh,  On recognizing and  characterizing  visibility  graphs of simple polygons, Discrete and Computational Geometry, vol. 17, pp. 143-162, 1997.

    12. T. K. Dey, M. B. Dillencourt, S. K. Ghosh and J. M. Cahil, Triangulating with high connectivity, Computational Geometry: Theory and Applications, vol. 8, 39-56, 1997.

    13. S. K. Ghosh and S. Saluja,  Optimal on-line algorithms for walking with minimum number of turns in unknown streets,  Computational Geometry: Theory and Applications, vol. 8, 241-266, 1997.

    14. T. Asano, S. K. Ghosh and T. Shermer,  Visibility in the plane,  (Survey paper), Handbook in Computational Geometry (edited by J.-R Sack and J. Urrutia), Elsevier Science Publishers B.W., Chapter 19, pp. 829-876, 2000.

    15. B. Bhattacharya and S. K. Ghosh,  Characterizing LR-visibility polygons and related problems, Computational Geometry: Theory and Applications, vol. 18, 19-36, 2001.

    1. J-D. Boissonnat, S. K. Ghosh, T. Kavitha and S. Lazard,  An algorithm for computing a convex path of bounded curvature in a simple polygon,  Algorithmica, vol. 34, no. 2, 109-156, 2002.

    2. B. Bhattacharya, S. K. Ghosh and T. Shermer,  A linear time algorithm to remove winding of a simple polygon,  Computational Geometry: Theory and Applications, vol. 33, 165-173, 2006.

    3. R. Krishnamurti, D. R. Gaur, S. K. Ghosh and H. Sachs,  Berge's theorem for the maximum charge problem,  Discrete Optimization, vol.3, no.2, 174-178, 2006.

    4. S. K. Ghosh, T. Shermer, B. Bhattacharya and P. Goswami,   Computing the maximum clique in the visibility graph of a simple polygon,  Journal of Discrete Algorithms, vol. 5, pp. 524-532, 2007.

    5. S. K. Ghosh, J. W. Burdick, A. Bhattacharya and S. Sarkar,   Online algorithms with discrete visibility: Exploring unknown polygonal environments,  Special issue on Computational Geometry approaches in Path Planning, IEEE Robotics & Automation Magazine, vol. 15, no. 2, pp. 67-76, 2008.

    6. S. K. Ghosh,   Approximation algorithms for art gallery problems in polygons,   Discrete Applied Mathematics, vol. 158, pp. 718-722, 2010.

    7. S. K. Ghosh and R. Klein,   Online algorithms for searching and exploration in the plane,   (Survey Paper),   Computer Science Review, vol. 4, pp. 189-201, 2010.

    8. S. K. Ghosh, P. P. Goswami, A. Maheshwari, S. C. Nandy, S. P. Pal and Swami Sarvattomananda,   Algorithms for computing diffuse reflection paths in polygons, The Visual Computer, vol. 28, no. 12, pp. 1229-1237, 2012.

    9. S. K. Ghosh and P. E. Haxell,   Packing and covering tetrahedra,   Discrete Applied Mathematics, vol. 16, no. 9, pp. 1209-1215, 2013.

    10. S. K. Ghosh and P. P. Goswami,   Unsolved problems in visibility graphs of points, segments and polygons,   (Survey Paper), ACM Computing Surveys, vol. 46, no. 2, pp. 22:1-22:29, 2013.

    11. Y. Disser, S. K. Ghosh, M. Mihalák, P. Widmayer,   Mapping a polygon with holes using a compass,   Theoretical Computer Science, vol. 553, pp. 106-113, 2014.

    12. S. K. Ghosh and B. Roy,   Some results on point visibility graphs, Theoretical Computer Science, vol. 575, pp. 17-32, 2015.

    13. A. A. Diwan, S. K. Ghosh and B. Roy,   Four-connected triangulations of planar point sets, Discrete and Computatational Geometry, vol. 53, pp. 713-746, 2015.

    14. P. Bhattacharya, S. K. Ghosh and B. Roy,  Approximability of guarding weak visibility polygons, Discrete Applied Mathematics, vol 228, pp. 109-129, 2017.

    15. A. Diwan, B. Roy and S. K. Ghosh,   Two layer drawings of bipartite graphs , Electronic Notes in Discrete Mathematics, vol. 61, pp. 351-357, 2017.

    16. P. Bhattacharya, S. K. Ghosh, B. Roy,   Approximability of guarding weak visibility polygons , Discret. Appl. Math, vol. 228, pp. 109-129 2017.

    17. B. S. Panda, S. K. Ghosh,   Preface: CALDAM 2018 , Discret. Appl. Math, vol. 305, pp. 260, 2021.

  • In Proceedings/Lecture Notes/arXiv:

    1. S. K. Ghosh,  A linear time algorithm for decomposing a monotone polygon into star-shaped polygons, Proceedings of the Third Symposium on Foundation of Software Technology and Theoretical Computer Science, India,  pp.  505-519,  1983.

    2. S. K. Ghosh,  A linear time algorithm for determining the intersection type of two star polygons, Proceedings of the Fourth Symposium on Foundation of Software Technology and Theoretical Computer Science, Bangalore, Lecture Notes in Computer Science, No. 181, pp. 317-330, Springer Verlag, 1984.

    3. S. K. Ghosh,  Approximation algorithms for art gallery problems, Proceedings of the Canadian Information Processing Society Congress,  pp.  429-434,  1987.

    4. S. K. Ghosh and D. M. Mount,  An output sensitive algorithm for computing visibility graphs, Proceedings of the IEEE Symposium on Foundation of Computer Science,  pp.  11-19,  1987.

    5. S. K. Ghosh,  On recognizing and characterizing visibility graphs of simple polygons, Proceedings of the First Scandinavian Workshop on Algorithm Theory, Halmstad, Lecture Notes in Computer Science, No. 318, pp. 96-104, Springer Verlag, 1988.

    6. S. K. Ghosh,  Computing a viewpoint of a set of points inside a polygon, Proceedings of the Eighth Symposium on Foundation of Software Technology and Theoretical Computer Science, Pune, Lecture Notes in Computer Science, No. 338, pp. 18-29, Springer Verlag, 1988.

    7. S. K. Ghosh,  Shortest paths help in solving visibility problems,  Proceedings of the Indo-French Seminar on Theoretical Computer Science, Goa,  1989.

    8. S. K. Ghosh, A. Maheshwari, S. P. Pal, S. Saluja and C. E. Veni Madhavan,  Characterizing weak visibility polygons and related problems,  Proceedings of the Second Canadian Conference on Computational Geometry,  pp.  93-97,  1990.

    9. S. K. Ghosh, A. Maheshwari, S. P. Pal and C. E. Veni Madhavan, An algorithm for recognizing palm polygons, Proceedings of the Second Canadian Conference on Computational Geometry,  pp.  246-251,  1990.

    10. S. K. Ghosh,  A. Maheshwari,   S. P. Pal,  S. Saluja  and C. E. Veni Madhavan, Computing the shortest path tree in a weak visibility polygon, Proceedings of the Eleventh Symposium on Foundation of Software Technology and Theoretical Computer Science, New Delhi, Lecture Notes in Computer Science, No. 560, pp. 369-389, Springer Verlag, 1991.

    11. S. K. Ghosh and A. Maheshwari,  Optimal parallel algorithm for determining the intersection type of two star-shaped polygons, Proceedings of the Third Canadian  Conference  on  Computational  Geometry, Vancouver,  pp.   3-7,  1991.

    12. S. K. Ghosh, A. Maheshwari, S. P. Pal, S. Saluja and C. E. Veni Madhavan, Computing the shortest path tree in a weak visibility polygon, Proceedings of the First National Seminar on Theoretical Computer Science, pp. 44-56, 1991.

    13. S. K. Ghosh and A. Maheshwari,  Parallel algorithms for all minimum link paths and link center problems, Proceedings of the Third Scandinavian Workshop on Algorithm Theory, Helsinki, Lecture Notes in Computer Science, No. 621, pp. 106- 117, Springer Verlag, 1992.

    14. S. K. Ghosh and D. M. Mount, Studying approximations to polyhedral objects under various optimization criteria, Proceedings of the Indo-US Workshop on Cooperative Research in Computer Science,  pp. 48-51,  1992.

    15. S. K. Ghosh,  Computational geometry: An introduction,  (Survey Paper), Proceedings of the National Seminar on Theoretical Computer Science, pp. 145-187, 1992.

    16. T. Dey, M. B. Dillencourt and S. K. Ghosh,  Triangulating with high connectivity,  Proceedings of the Sixth Canadian Conference on Computational Geometry,  pp.  339-343,  1994.

    17. S. K. Ghosh,  Parallel computational geometry: An introduction,   (Survey Paper), Proceedings of the National Seminar on Theoretical Computer Science, pp. 284-314, 1994.

    18. S. K. Ghosh and J. W. Burdick, An on-line algorithm for exploring an unknown polygonal environment by a point robot, Proceedings of the Ninth Canadian Conference on Computational Geometry, pp. 100-105, 1997.

    19. S. K. Ghosh and J. W. Burdick,  Understanding discrete visibility and related approximation algorithms, Proceedings of the Ninth Canadian Conference on Computational Geometry,  pp.  106-111,  1997.

    1. B. Bhattacharya and S. K. Ghosh,  Characterizing LR-visibility polygons and related problems, Proceedings of the Tenth Canadian Conference on Computational Geometry,  pp.  1-6,  1998.

    2. S. K. Ghosh,  Parallel algorithms in computational geometry,  (Survey Paper), Proceedings of the International Workshop on High Performance Computing, pp. 87-116, 1998.

    3. A. Bhattacharya, S. K. Ghosh and S. Sarkar,   Exploring an unknown polygonal environment with bounded  visibility, Proceedings of the International Conference on Computational Science, San Francisco,  Lecture  Notes  in  Computer Science,  No.  2073,  pp. 640-648,  Springer Verlag, 2001.

    4. S. K. Ghosh, P. P. Goswami, A. Maheshwari, S. C. Nandy, S. P. Pal and Swami Sarvattomananda,   Algorithms for computing diffuse reflection paths in polygons, Proceedings of the Third International Workshop on Algorithms and Computations, Kolkata,  Lecture  Notes  in  Computer Science,  No.  5431,  pp. 47-58,  Springer, 2009.

    5. A. A. Diwan, S. K. Ghosh, P. P. Goswami and A. Lingas,  On joint triangulation of two sets of points in the plane, Proceedings of India-Taiwan Conference on Discrete Mathematics, Taipei,  pp.   34-43, 2009. (Full version of this paper is available at arxiv.org).

    6. S. K. Ghosh and P. P. Goswami,   Unsolved problems in visibility graph theory, (Survey Paper), Proceedings of India-Taiwan Conference on Discrete Mathematics, Taipei,  pp.   44-54, 2009. (Full version of this survey paper is available at arxiv.org).

    7. S. K. Ghosh,   Approximation algorithms for art gallery problems in polygons and terrains, (Survey Paper), Proceedings of the Forth International Workshop on Algorithms and Computations, Dhaka, Lecture Notes in Computer Science, No. 5942, pp. 21-34, Springer, 2010.

    8. Y. Disser, S. K. Ghosh, M. Mihalak, P. Widmayer,   Mapping a polygon with holes using a compass, Proceedings of the Eight International Symposium on Algorithms for Sensor Systems, Wireless Ad Hoc Networks and Autonomous Mobile Entities, Lecture Notes in Computer Science, vol. 7718, pp. 78-89, Springer, 2012.

    9. A. Bishnu, S. K. Ghosh, P. P. Goswami, S. P. Pal, S. Sarvattomananda,   An algorithm for computing constrained reflection paths in simple polygon, Manuscript, April 2013 (available at arxiv.org).

    10. S. K. Ghosh and B. Roy,   Problems on Plane Triangulations of Points, Proceedings of India-Taiwan Conference on Discrete Mathematics, Hsinchu, Taiwan, pp. 57-60, 2013.

    11. S. K. Ghosh and B. Roy,   Some results on point visibility graphs, Proceedings of the 8th International Workshop on Algorithms and Computations, Chennai, Lecture Notes in Computer Science, vol. 8344, pp. 163-175, Springer, 2014.

    12. A. Baertschi, T. Tschager, S. K. Ghosh, M. Mihalak and P. Widmayer,   Improved bounds for the conflict-free chromatic art gallery problem, Proceedings of the 30th ACM Annual Symposium on Computational Geometry, pp. 144-153, 2014.

    13. P. Bhattachary, S. K. Ghosh and B. Roy,   Vertex Guarding in Weak Visibility Polygons, Proceedings of the 1st International Conference on Algorithms and Discrete Applied Mathematics, Kanpur, Lecture Notes in Computer Science, vol. 8959, pp. 45-57, Springer, 2015. (Full version of the paper is available at arxiv.org).

    14. S. K. Ghosh and S. P. Pal,   A National Effort for Motivating Indian Students and Teachers towards Algorithmic Research, Manuscript (on Computer Education), July 2015 (available at arxiv.org).

    15. P. Bhattacharya, S. K. Ghosh, S. P. Pal,   Constant Approximation Algorithms for Guarding Simple Polygons using Vertex Guards, CoRR abs/1712.05492, 2017

    16. Onur Çagirici, S. K. Ghosh, Petr Hlinený, . Roy,   On Conflict-Free Chromatic Guarding of Simple Polygons, COCOA 2019: 601-612

    17. A. A. Diwan, B. Roy, S. K. Ghosh,   Drawing Bipartite Graphs in Two Layers with Specified Crossings, CALDAM 2019: 97-108

    18. D. Chakraborty, Florent Foucaud, H. Gahlawat, S. K. Ghosh, B. Roy,   Hardness and Approximation for the Geodetic Set Problem in Some Graph Classes, CALDAM 2020: 102-115

    19. D. Chakraborty, Antoine Dailly, S. Das, Florent Foucaud, H. Gahlawat, S. K. Ghosh,   Complexity and Algorithms for ISOMETRIC PATH COVER on Chordal Graphs and Beyond, ISAAC 2022: 12:1-12:17

    Back to Home Page