ASISH MUKHOPADHYAY'S RESEARCH PAGE

Edited Proceedings

Co-edited with Dr. Prosenjit Bose a special issue of a selection of papers from the 17th Canadian Conference on Computational Geometry that will appear in Computational Geometry: Theory and Applications , Vol. 42, No. 5, July 2009.

Journal/Conference publications and Technical Reports

Computational Geometry

Visibility

Journals

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 .

Conferences

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 .

Asish Mukhopadhyay, Chris Drouillard and Godfried Toussaint. Guarding simple polygons with semi-open edge guards. In Proceedings of The Third International Conference on Digital Information Processing and Communications (ICDIPC2013), Dubai, UAE, 30 Jan. 2013 - 1 Feb. 2013, pages 417-422:w .

Proximity Graphs

Journals

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 .

Conferences

Gautam K. Das, Asish Mukhopadhyay, Subhas C. Nandy, Sangameswar Patil and S. V. Rao. Computing the straight skeleton of a monotone polygon in O(n log n) time. Accepted for presentation to Canadian Conference on Computational Geometry, 9-11 August, 2010 .

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

Journals

Asish Mukhopadhayay, Eugene Greene, Animesh Sarker and Tom Switzer. From approximate balls to approximate ellipses. Available online in Journal of Global Optimization, DOI 10.1007/s10898-012-9932-1, 2012; published in Vol. 56, pages 27-42.

Asish Mukhopadhyay and Satish Panigrahi. All-maximum and all-minimum problems under some measures. In abstracts of the 12th European Conference on Computational Geometry , 19 March - 21 March, 2012, University of Perrugia, Assisi, Italy. talk ; to appear in Journal of Discrete Algorithms, DOI information: 10.1016/j.jda.2013.03.008, online version available here .

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, 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)

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. Using simplicial partitions to compute a point closest to a query line. In Pattern Recognition Letters , 24(12), pages 1915-1920, 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 .

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. .

Conferences and Reports

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 .

Asish Mukhopadhyay, Animesh Sarker and Tom Switzer. Approximate minimum spanning ellipsoids in the streaming model. Technical Report, School of Computer Science, University of Windsor, August 2009, accepted to The 4th Annual International Conference on combinatorial Optimization and Applications (COCOA 2010).

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 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.

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.

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 )

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

Journals

Asish Mukhopadhyay and Eugene Greene. The ordinary line problem revisited. In Computational Geometry: Theory and Applications, Vol. 45, pages 127-130, 2012.

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.

Reports

Asish Mukhopadhyay. Computing the incidences of m points and n conics in the plane. Technical Report, School of Computer Science, University of Windsor, Canada.

Biogeometry

Satish Panigrahi, Md. Shafiul Alam, and Asish Mukhopadhyay. A new profiling tool for gene expression data. Poster presentation at Conference on Informatics and Integrative Biology , 14 December - 16 December 2011 (CIIB-2011) Kolkata, India. poster; an extended version accepted for presentation at ICCSA, 2013 in Vietnam.

Puspal Bhabak and Asish Mukhopadhyay. Improved Approximation algorithms for agreement forests on k phylogenetic trees. Oral presentation at Conference on Informatics and Integrative Biology , 14 December - 16 December 2011 (CIIB-2011) Kolkata, India. talk

Md. Shafiul Alam, Satish Panigrahi, Puspal Bhabak and Asish Mukhopadhyay. Multi-gene linear separabiliy of gene expression data in linear time . In Short Abstracts Collection, pages 51-54, 6th International Symposium on Bioinformatics Research and Applications (ISBRA 10) , University of Connecticut, USA, May 23-26, 2010. pdf .

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. A new algorithm and improved lower bound for point placement on a line in 2 rounds. In Proceedings of the 22nd Canadian Conference on Computational Geometry , Winnipeg, Manitoba, 9-11 August, 2010. pdf

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. Accepted as a poster paper to Workshop on Algorithms in Bioinformatics (WABI 2010) , 8-10 September, University of Liverpool, England. Also archived as arXiv.org:1210.3833

Md. Shafiul Alam and Asish Mukhopadhyay. A linear time geometric algorithm for the segment density problem. In Abstracts of the Fall Workshop on Computational Geometry, Stony Brook University, Stony Brook, USA, 29-30 October, 2010.

Md. Shafiul Alam and Asish Mukhopadhyay. Algorithms for the problems of length-constrained heaviest segments, August 2011, arXiv.org:1108.4972

Md. Shafiul Alam and Asish Mukhopadhyay. Optimal Algorithms for Some Sum and Density Problems of a Sequence, Accepted for presentation to the 21st Fall Workshop on Computational Geometry, 4-5 November 2011, CCNY, New York City, New York.

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, In Proceedings of the 26th EuroCG Workshop on Computational Geometry, pages 225-228 , Dortmund, Germany, March 22-24, 2010.

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 .

Miscellaneous

M. S. Alam and Asish Mukhopadhyay. Constraint Representation for Autonomous Camera. Accepted to the 2010 International Conference on Computer Graphics and Virtual Reality (CGVR'10) , Las Vegas, Nevada, USA, 12 July - 15 July, 2010.

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.