Edited Proceedings

Journal/Conference publications and Technical Reports

Computational Geometry

• Visibility

• Binay K. Bhattacharya, Gautam Das, Asish Mukhopadhyay and Giri Narasimhan. Optimally computing a shortest weakly visible line segment inside a simple polygon. Computational Geometry: Theory and Applications, 23(1), pages 1-29, July 2002.
• G.Srinivasaraghavan and Asish Mukhopadhyay. Edge visibility graphs of orthogonal polygons with holes. International Journal of Computational Geometry and Applications, 10(1), pages 79-102, 2000
• Binay K. Bhattacharya and Asish Mukhopadhyay and Godfried T.Toussaint. Computing a shortest weakly externally visible line segment for a simple polygon. International Journal of Computational Geometry and Applications, 9(1), pages 81-96, 1999.
• G. Srinivasaraghavan and A. Mukhopadhyay. A new necesssary condition for the vertex visibility graphs of simple polygons. Discrete and Computational Geometry, 12(1), pages 65-82, 1994 .
• Binay K. Bhattacharya and Asish Mukhopadhyay. Computing in linear time an internal line segment from which a simple polygon is weakly internally visible. In Proceedings of ISAAC, LNCS 1004, pages 22-31, Cairns, Australia, 1995 .
• Binay K. Bhattacharya, Asish Mukhopadhyay and Giri Narasimhan. Two guard walkability of simple polygons. In Proceedings of the 7th International Conference on Algorithms and Data Structures (WADS), LNCS 2125, Rhode Island, USA, 2001 .

• Proximity Graphs

• S. V. Rao and Asish Mukhopadhyay. Fast Algorithms for computing beta-skeletons and their relatives. Pattern Recognition, 34, pages 2163-2172, 2001 .
• Asish Mukhopadhyay and S. V. Rao. Output-sensitive algorithm for computing beta-skeletons. Computing, 65, pages 285-289, 2000 .
• S. V. Rao and Asish Mukhopadhyay. Efficient algorithms for computing the beta-spectrum. In Proceedings of the Canadian Conference on Computational Geometry, New Brunswick, pages 91-97, August 2000 .
• S. V. Rao and Asish Mukhopadhyay. Beta-skeletons in higher dimensions. In Proceedings of the First Indian Conference on Computer Vision, Graphics and Image Processing, New Delhi, pp 402-407, December 1998 .
• Andrzej Lingas and Asish Mukhopadhyay. A linear-time construction of the relative neighbourhood graph within a histogram. The 4th International Workshop on Algorithms and Data Structures (WADS), LNCS 955, pages. 228-238, Springer, 16-18 August 1995 .

• Optimization problems

• Tom Switzer, Animesh Sarker and Asish Mukhopadhyay. Approximate bounding boxes in the streaming model. Technical Report, School of Computer Science, University of Windsor, September 2009 .
• Animesh Sarker, Asish Mukhopadhyay and Tom Switzer. Approximate minimum spanning ellipsoids in the streaming model. Technical Report, School of Computer Science, University of Windsor, August 2009 .
• Asish Mukhopadhayay, Eugene Greene, Animesh Sarker and Tom Switzer. Approximate minimum spanning ellipse in the streaming model. In Proceedings of the 7th Japan Conference on Computational Geometry and Graphs, pages 9-10, Kanazawa, Japan, 11-13 Nov., 2009. pdf

  This paper is a merger of two earlier papers.

• Xin Wu, Xijie Zeng, Bryan St. Amour and Asish Mukhopadhyay. Robust implementation of an algorithm to compute a convex polygon stabber of a set of isothetic line segments. Technical Report, School of Computer Science, University of Windsor, July 2009. pdf
• Hamid Zarrabi-Zadeh and Asish Mukhopadhyay. Streaming 1-center with ouliers in high dimensions. In Proceedings of the 21st Canadian Conference on Computational Geometry, pages 83-86, UBC, Vancouver, 17-19 August 2009. pdf
• Asish Mukhopadhyay and Animesh Sarker. A note on the approximation ratio for computing an approximate spanning ellipse in the streaming model. Technical Report, School of Computer Science, University of Windsor, May 2009. pdf
• Eugene Greene and Asish Mukhopadhyay. Closest-point queries for complex objects. Accepted to the Computational Geometry and Applications Track of ICCSA 2009, held at Yongjin, Korea, June 2009 (this is a revised version of a Technical Report Number 07-018, 01 October 2007, School of Computer Science, University of Windsor, Canada). pdf
• Asish Mukhopadhyay and Eugene Greene. A short note on monotone matrices and the segment sum selection problem. Tech Report Number 08-026, 11 Sept. 2008, School of Computer Science, University of Windsor, Canada. pdf
• Asish Mukhopadhyay and Eugene Greene. A streaming algorithm for computing an approximate spanning ellipse. In Abstracts of the Fall Workshop on Computational Geometry, RPI, Troy, New York, 2008. (full version) pdf
• Asish Mukhopadhyay, Chanchal Kumar, Eugene Greene and Binay K. Bhattacharya. On intersecting a set of parallel line segments with a convex polygon of minimum area. In Information Processing Letters (impact factor: 0.660), 105, pages 58-64, 2008.
• R.L. Scot Drysdale and Asish Mukhopadhyay. An O(n log n) algorithm for the all-farthest-segments problem for a planar set of points. In Information Processing Letters (impact factor 0.660), Vol. 105, pp 47-51, 2008
• Asish Mukhopadhyay and Eugene Greene. On the k-th maximum density segment of a sequence (working paper), June 2007
• Asish Mukhopadhyay, Eugene Greene and Dulon Roy Chowdhury. On the all-farthest triangles problem for a set of points in 3d. In abstracts of the 17th Fall Workshop on Computational and Combinatorial Geometry, IBM T.J. Watson, Research Center, New York, 9-10 Nov., 2007
• Asish Mukhopadhyay and Eugene Greene. On a geometric approach to the segment sum problem and its generalization. In Proceedings of the 19th Canadian Conference on Computational Geometry, pages 265-268, Carleton University, Ottawa, 20-22 August 2007 .
• Asish Mukhopadhyay, Eugene Greene and S. V. Rao. On intersecting a set of isothetic line segments with a convex polygon of minimum area. In Proceedings of the International Workshop on Computational Geometry and Applications, LNCS 4705, pages 41-54, Kuala Lampur, Malaysia, 2007. (accepted for publication to the International Journal of Computational Geometry and Applications)
• R.L. Scot Drysdale and Asish Mukhopadhyay. An O(n log n) algorithm for the all-farthest-segments problem for a planar set of points. In Proceedings of the 18th Canadian Conference on Computational Geometry, pages 185-188, Queen's University, Kingston, 14-16 August, 2006.
• Asish Mukhopadhyay, Samidh Chatterjee and Benjamin Lafreniere. On the all-farthest-segments problem for a planar set of points. In Information Processing Letters (impact factor 0.660), 100, pages 120-123, 2006 (preliminary version in Abstracts of the 22nd European Workshop on Computational Geometry, Greece, 2006)
• Asish Mukhopadhyay and Samidh Chatterjee. Farthest and Closest Segments. Technical Report 05-015, School of Computer Science, University of Windsor, July, 2005.
• Asish Mukhopadhyay. Using simplicial partitions to compute a point closest to a query line. In Pattern Recognition Letters , 24(12), pages 1915-1920, 2003.
• Pinaki Mitra, Asish Mukhopadhyay. Computing the closest point to a query hyperplane in higher dimensions. In Proceedings of the International Workshop on Computational Geometry and its Applications, LNCS 2669, pages 787-796, Montreal, 2003.
• Pinaki Mitra, Asish Mukhopadhyay and S. V. Rao. Computing the closest point to a circle. In Proceedings of the 15th Canadian Conference on Computational Geometry, pages 132-135, Halifax, Nova Scotia, 11-13 August, 2003.
• Asish Mukhopadhyay and S.V. Rao. Efficient algorithm for computing a largest empty arbitrary oriented rectangle. In International Journal of Computational Geometry and Applications, 13(3), pages 257-272, 2003 .
• Binay Bhattacharya and Asish Mukhopadhyay. A linear time algorithm for computing a minimum perimeter triangle enclosing a convex polygon. In the Proceedings of the Japan Conference on Discrete and Computational Geometry, LNCS 2866, pages 84-96, 2002. (a preliminary version appeared in the European Conference on Computational Geometry, Berlin, 26-28 March, 2001 )
• Shreesh Jadhav, Asish Mukhopadhyay and Binay K. Bhattacharya. An optimal algorithm for the intersection radius of a set of convex polygons. Journal of Algorithms, 20(2), pages 244-267, 1996. .
• Binay K. Bhattacharya, Shreesh Jadhav, Asish Mukhopadhyay and J. M. Robert. Optimal algorithms for some smallest intersection radius problems. Computing, 52, pages 269-279, 1994. .
• Asish Mukhopadhyay, Chanchal Kumar and Binay K. Bhattacharya. Area-optimal convex polygonal stabber of a set of parallel line segments. In Proceedings of the 5th Canadian Conference on Computational Geometry, Waterloo, pages 169-174, 1993.
• Shreesh Jadhav, Asish Mukhopadhyay, Binay K. Bhattacharya. An optimal algorithm for the intersection radius of convex polygons. In Proceedings of the Foundations of Software Technology and Theoretical Computer Science, pages 92-103, New Delhi, 1992.

Combinatorial Geometry

• Asish Mukhopadhyay and Eugene Greene. The ordinary line problem revisited. In Proceedings of the 19th Canadian Conference on Computational Geometry, pages 61-64, Carleton University, Ottawa, 20-22 August, 2007 (invited to a special issue of Computational Geometry: Theory amd Applications). pdf
• Asish Mukhopadhyay, Alok Agrawal and Ravi Mohan Hosabettu. On the ordinary line problem in computational geometry. Nordic Journal of Computing, 4, pages 330-341, 1997.
• Olivier Devillers and Asish Mukhopadhyay. Finding an ordinary conic and an ordinary hyperplane. Nordic Journal of Computing, 6(4), pages 462-468, 1999.
• Shreesh Jadhav and Asish Mukhopadhyay. Computing a centerpoint of a finite planar set of points in linear time. Discrete and Comp. Geometry, 12(3), pp 291-312, 1994.
• Asish Mukhopadhyay. Computing the incidences of m points and n conics in the plane. Technical Report, School of Computer Science, University of Windsor, Canada.

Applications of Computational Geometry in Computational Biology

• Md. Shafiul Alam, Asish Mukhopadhyay and Animesh Sarker. Generalized jewels and the point placement problem. In Proceedings of the 21st Canadian Conference on Computational Geometry, pages 45-48, UBC, Vancouver, August 17-19, 2009. pdf
• Md. Shafiul Alam, Asish Mukhopadhyay and Animesh Sarker. More on generalized jewels and the point placement problem. Technical Report, School of Computer Science, University of Windsor, September 2009.
• Md. Shafiul Alam and Asish Mukhopadhyay. Improved upper and lower bounds for the point placement problem. Technical Report, School of Computer Science, University of Windsor, No. 10-004, March 2010.

Applications of Computational Geometry in Computer Graphics

• Curve and Surface Reconstruction

• Asish Mukhopadhyay, Harshit Rathod, Chong Wang and Bryan St. Amour, Certifying curve reconstruction algorithms, accepted for presentation to EuroCG 2010, Dortmund, Germany.
• Asish Mukhopadhyay and Augustus Das, Curve reconstruction in the presence of noise, in Proceedings of Computer Graphics, Imaging and Visualization, pp 177-182, held at Bangkok, Thailand 15 - 17 August, 2007
• Asish Mukhopadhyay and Augustus Das, An RNG-based heuristic for curve reconstruction, in Proceedings of the International Symposium on Voronoi Diagram 2006, Banff, Canada, 2-5 July, 2006, pages 246-251, (revised version) pdf
• Gunjan Jha, Sanjay Agarwal and Asish Mukhopadhyay, Surface Reconstruction from Contours: Improvements to the Barequet-Sharir heuristic, in Proceedings of CSI-97, Ahmedabad, India, 1997.
• Vishal Goenka, Deepak Kumar, Nabanjan Das and Asish Mukhopadhyay, Surface Reconstruction from Parallel Planar Contours, in Proceedings of CSI-96, Bangalore, pp 441 - 444, 1996.

• Geometric Compression

• Encoding Quadrilateral Meshes in 2.40 bits per vertex, Pawel Kosicki, Asish Mukhopadhyay, in Proceedings of ICVGIP 2004 (acceptance rate 30%), Kolkata, India, Dec 16-18, 2004 .
• Quanbin Jing, Asish Mukhopadhyay, Linear time compression and decompression of 3d quad mesh on vertex and opposite-edge table, Manuscript, June 2002.
• Asish Mukhopadhyay, Quanbin Jing, Encoding quadrilateral meshes, accepted to the Fifteenth Canadian Conference on Computational Geometry, halifax, Nova Scotia, 2003. May 2003. Compressed PDF File

Computer Graphics

• B. S. S. Pradhan and A. Mukhopadhyay, Adaptive cell division for ray-tracing, Computers and Graphics, Vol. 15, No. 4, pp 549-552, 1991 .

Discrete Mathematics

• Asish Mukhopadhyay, 2x2 matrix-multiplication revisited, in Journal of the Indian Institute of Science, Bangalore 64(B)(1983),105-107.
• Asish Mukhopadhyay, A solution to the polynomial Hensel-code problem, IEEE Transactions on Computers, VC-36, pp 634-637, 1987 .
• Asish Mukhopadhyay and V.S.Alagar, Exact computation of the characteristic polynomial of an integer matrix, Annual Conference on Computer Algebra, Algebraic Algorithms, Symbolic Computation and Error-Correcting Codes, Grenoble, France, 1985, pp 316-324, LNCS V229.