Broadly, I am interested in the areas of scientific visualization, computational topology, computational geometry, and computer graphics. I have had the pleasure of collaborating with several distinguished researchers, brilliant postdocs and students.

Below is a summary of some of the research projects that I have worked (am working) on.

Please look at Visualization and Graphics Lab page for descriptions of recent research projects.


Reeb Graphs
Given a smooth real-valued function f over a manifold with or without boundary, the Reeb graph is obtained by contracting the connected components of the level sets to points. It serves as a useful interface to explore large and feature-rich scientific data sets. For 2D domains, we prove tight upper and lower bounds on the number of loops in the Reeb graph that depend only on the surface and describe an efficient algorithm to compute the Reeb graph for piecewise-linear functions. We have also developed generic algorithms to compute the Reeb graph of scalar functions defined over manifold and non-manifold domains. These algorithms are efficient either in terms of worst case running time or exhibit efficiency in practice -- are scalable to large data sets, require a low memor footprint, and are easy implement. We extend the computation to piecewise quadratic functions by constructing a generic tessellation of each element into monotonic patches.
  • Kree Cole-MacLaughlin, Herbert Edelsbrunner, John Harer, Vijay Natarajan and Valerio Pascucci. Loops in Reeb graphs of 2-manifolds. Invited paper in Discrete and Computational Geometry, 32(2), 2004, 231-244.
    Proc. ACM Symposium on Computational Geometry, 2003, 344-350. [Paper]
  • Scott E. Dillard, Vijay Natarajan, Gunther H. Weber, Valerio Pascucci, and Bernd Hamann. Tessellation of quadratic elements. Proc. Intl. Symp. Algorithms and Computation, LNCS 4288, Springer-Verlag, 2006, 722-731. [Paper]
  • Scott E. Dillard, Vijay Natarajan, Gunther H. Weber, Valerio Pascucci, and Bernd Hamann. Topology-guided tessellation of quadratic elements. Invited paper in Intl. J. Computational Geometry and Applications, 19(2), 2009, 195-211. [Paper]
  • Harish Doraiswamy and Vijay Natarajan. Efficient output-sensitive construction of Reeb graphs. Proc. Intl. Symp. Algorithms and Computation, LNCS 5369, Springer-Verlag, 2008, 557-568. [Paper]
  • Harish Doraiswamy and Vijay Natarajan. Efficient algorithms for computing Reeb graphs. Computational Geometry: Theory and Applications, 42, 2009, 606-616. [Paper]
  • Harish Doraiswamy and Vijay Natarajan. Output-sensitive construction of Reeb graphs. IEEE Transactions on Visualization and Computer Graphics, 18(1), 2012, 146-159. [Paper]
  • Harish Doraiswamy and Vijay Natarajan. Computing Reeb graphs as a union of contour trees. IEEE Transactions on Visualization and Computer Graphics, 19 (2), 2013, 249-262. [Paper]

Parallel computation of Morse-Smale Complexes
Data sizes grow faster than processor speeds resulting in an ever-present demand for better algorithms to process the data. With this motivation, we developed parallel algorithms to compute the Morse-Smale complex, a topological structure that has been widely studied and used to represent features in scalar fields. The algorithm utilizes the multiple cores available in the CPU and GPU of a typical desktop computer to compute the MS complex of large two- and three-dimensional data. The definition and computation of the MS complex for sampled functions requires gradient / steepest path computation and path tracing, which is inherently serial in nature. We proved two lemmas on gradient flow paths and symbolic perturbation that lead to an algorithm for computing the cells of the MS complex in a few massively parallel steps.
  • Nithin Shivashankar, Senthilnathan M. and Vijay Natarajan. Parallel computation of 2D Morse-Smale complexes. IEEE Transactions on Visualization and Computer Graphics, 18(10), 2012, 1757-1770. [Paper]
  • Nithin Shivashankar and Vijay Natarajan. Parallel computation of 3D Morse-Smale complexes. Computer Graphics Forum (EuroVis 2012), 31 (3), 2012, 965-974. [Paper]

Hierarchical Morse-Smale Complexes
Geometric methods for scalar field simplification do not provide the necessary level of control and hence may result in unnecessary removal of features. We have been working on a topological approach for simplifying continuous functions defined on volumetric domains. The Morse-Smale complex provides an efficient representation of topological features and enables controlled simplification of features. We have developed a combinatorial algorithm for simplifying the Morse-Smale complex that is robust and stable. The simplification procedure leaves important critical points untouched, and is therefore useful for extracting features and storing them in a hierarchy.
  • Attila Gyulassy, Vijay Natarajan, Valerio Pascucci, Peer-Timo Bremer and Bernd Hamann. Topology-based simplification for feature extraction from 3D scalar fields. Proc. IEEE Conference on Visualization, 2005, 535-542. [Paper]
  • Attila Gyulassy, Vijay Natarajan, Valerio Pascucci, Peer-Timo Bremer and Bernd Hamann. A topological approach to simplification of three-dimensional scalar fields. Invited paper in IEEE Transactions on Visualization and Computer Graphics, 12(4), 2006, 474-484. [Paper]
  • Attila Gyulassy, Mark Duchaineau, Vijay Natarajan, Valerio Pascucci, Eduardo Bringa, Andrew Higginbotham, and Bernd Hamann. Topologically clean distance fields. IEEE Transactions on Visualization and Computer Graphics (IEEE Visualization 2007), 13(6), 2007, 1432--1439. [Paper]

teaser teaser
Bio-molecular Surface Segmentation

We have developed a new method for segmentation of molecular surfaces. The segmentation is obtained by associating segments with local minima/maxima of an appropriate scalar function defined on the surface. Controlled simplification of the function merges segments resulting in a hierarchical segmentation of the molecular surface. This segmentation is used to identify rigid components of proteins molecules and to study the role of cavities and protrusions in protein-protein interactions.
  • Vijay Natarajan, Yusu Wang, Peer-Timo Bremer, Valerio Pascucci, and Bernd Hamann. Segmenting Molecular Surfaces. Computer Aided Geometric Design (special issue on Applications of Geometric Modeling in the Life Sciences), 23(6), 2006, 495-509. [Paper]
  • Oliver G. Staadt, Vijay Natarajan, Gunther H. Weber, David F. Wiley, and Bernd Hamann. Interactive processing and visualization of image data for biomedical and life science applications. M. Auer, H. Peng and A. Singh (editors), BMC Cell Biology (special issue), 8:S10, 2007. [Paper]
  • Vijay Natarajan, Patrice Koehl, Yusu Wang, and Bernd Hamann. Visual analysis of biomolecular surfaces. In Mathematical Methods for Visualization in Medicine and Life Sciences. L. Linsen, H. Hagen, and B. Hamann (editors), Springer Verlag, Mathematics and Visualization Series, 2007, 237-255. [Paper]


Comparative and Multi-field Visualization
We introduce local and global comparison measures for a collection of k real-valued smooth functions on a common d-dimensional surface. For the special case of k = d = 2 we relate the measures to the Jacobi set, the set of critical points of one function restricted to the level sets of the other. We also extended the topology-based multi-scale analysis methods to this challenging case of multi-field data. We developed a variation density function that profiles the relationship between multiple scalar fields over isosurfaces of a given scalar field. This profile serves as a valuable tool for multi-field data exploration because it provides the user with cues to identify interesting isovalues of scalar fields. We also employed the local comparison measure for robust computation of a multiresolution representation of the Jacobi setcp.
  • Herbert Edelsbrunner, John Harer, Vijay Natarajan, and Valerio Pascucci. Local and global comparison of continuous functions. Proc. IEEE Conference on Visualization, 2004, 275-280. [Paper][Video]
  • Suthambhara N. and Vijay Natarajan. Simplification of Jacobi sets. TopoInVis 2009, Springer-Verlag, Mathematics and Visualization Series, 2011, 91-102. [Paper]
  • Suthambhara N. and Vijay Natarajan. Relation-aware isosurface extraction in multi-field data. IEEE Transactions on Visualization and Computer Graphics, 17(2), 2011, 182-191. [Paper]
  • Suthambhara Nagaraj, Vijay Natarajan, and Ravi S. Nanjundiah. A gradient-based comparison measure for visual analysis of multifield data. Computer Graphics Forum, (EuroVis 2011), 30(3), 2011, 1101-1110. [Paper]

Point-based Representations
Extracting features from point sets is becoming increasingly important for purposes like model classification, matching, and exploration. We introduce a technique for segmenting a point-sampled surface into distinct features without explicit construction of a mesh or other surface representation. Our approach achieves computational efficiency through a three-phase segmentation process: a topological phase followed by a graph cut and finally a refinement phase. We apply our segmentation algorithm on laser-scanned models to evaluate its ability to capture geometric features in complex data sets.
  • Ichitaro Yamazaki, Vijay Natarajan, Zhaojun Bai, and Bernd Hamann. Segmenting point sets. Proc. IEEE Intl. Conf. Shape Modeling and Applications (SMI), 2006, 4-13. [Paper]

Morse-Smale complexes
Morse functions are used in differential topology to study the topology of manifolds. We use the results from Morse theory to study the topological features of natural phenomena. A Morse-Smale Complex partitions the 3D domain into cells with similar gradient flow characteristics. We design and implement an algorithm for constructing 3-dimensional Morse-Smale complexes with a guarantee on structural correctness. The challenge is to ensure that the discrete approximation of the data does not lead to intersections between the paths. We take advantage of the fact that cells of different dimension in the Morse-Smale complex characterize different types of features present in the data. For example, critical points pinpoint changes in level set topology. Edges of the Morse-Smale complex segment filament-like features that are not explicitly modeled in the original data. Interactive selection and rendering of portions of the Morse-Smale complex introduces fundamental data management challenges due to the unstructured nature of the complex even for structured inputs. We describe a data structure that stores the Morse-Smale complex and allows efficient selective traversal of regions of interest. We illustrate the practical use of this approach by applying it to study cryo-electron microscopy images of protein molecules.
  • Herbert Edelsbrunner, John Harer, Vijay Natarajan, and Valerio Pascucci. Morse-Smale complexes for piecewise linear 3-manifolds. Proc. ACM Symposium on Computational Geometry, 2003, 361-370. [Paper]
  • Vijay Natarajan and Valerio Pascucci. Volumetric analysis using Morse-Smale complexes. Intl. Conference on Shape Modeling and Applications (SMI), 2005, 320-330. [Paper][Video]
  • Vijay Natarajan and Valerio Pascucci. A topological method for analysis of 3D scalar functions. Invited paper in Computer Graphics and Geometry, 8(1), 2006, 66-76.
  • Attila Gyulassy, Vijay Natarajan, Valerio Pascucci, and Bernd Hamann. Efficient computation of Morse-Smale complexes for three-dimensional scalar functions. IEEE Transactions on Visualization and Computer Graphics (IEEE Visualization 2007), 13(6), 2007, 1440--1447. [Paper]

Attribute-preserving tetrahedral mesh simplification
We present an algorithm for the simplification of density maps in 3D. We assume that an input function specified at vertices of a triangulation and linearly interpolated within the tetrahedra. The fundamental operation in the simplification procedure is a topology preserving edge contraction. We describe simple and local conditions that can be used to check if an edge contraction preserves topology. These conditions are derived from the generic link conditions for 3-complexes described by Dey et. al. Besides providing a good approximation of the density map, the algorithm also aims to generate a mesh with good quality elements. We achieve this additional goal using a novel extension of the quadric error metric.
  • Vijay Natarajan and Herbert Edelsbrunner. Simplification of three-dimensional density maps. IEEE Transactions on Visualization and Computer Graphics, 10(5), 2004, 587-597. [Paper]

Topological analysis of scalar functions for scientific data visualization
Vijay Natarajan.
Ph.D. thesis. Department of Computer Science, Duke Univ., Durham, NC, 2004.
[PDF one-sided][Hyperlinked]
[PDF two-sided][Hyperlinked]
[Video 1][Video 2][Video 3]
Scientists attempt to understand physical phenomena by studying various quantities measured over the region of interest. A majority of these quantities are scalar (real-valued) functions. These functions are typically studied using traditional visualization techniques like isosurface extraction, volume rendering etc. As the data grows in size and becomes increasingly complex, these techniques are no longer effective. State of the art visualization methods attempt to automatically extract features and annotate a display of the data with a visualization of its features. In this thesis, we study and extract the topological features of the data and use them for visualization. We have three results:
  • An algorithm that simplifies a scalar function defined over a tetrahedral mesh. In addition to minimizing the error introduced by the approximation of the function, the algorithm improves the mesh quality and preserves the topology of the domain. We perform an extensive set of experiments to study the effect of requiring better mesh quality on the approximation error and the level of simplification possible. We also study the effect of simplification on the topological features of the data.
  • An extension of three-dimensional Morse-Smale complexes to piecewise linear 3-manifolds and an efficient algorithm to compute its combinatorial analog. Morse-Smale complexes partition the domain into regions with similar gradient flows. Letting n be the number of vertices in the input mesh, the running time of the algorithm is proportional to n log (n) plus the total size of the input mesh plus the total size of the output. We develop a visualization tool that displays different substructures of the Morse-Smale complex.
  • A new comparison measure between k functions defined on a common d-manifold. For the case d=k=2, we give alternative formulations of the definition based on a Morse theoretic point of view. We also develop visualization software that performs local comparison between pairs of functions in datasets containing multiple and sometimes time-varying functions.
We apply our methods to data from medical imaging, electron microscopy, and x-ray crystallography. The results of these experiments provide evidence of the usability of our methods.

Visibility Graphs
We consider the problem of reconstruction of a polygon given it's visibility graph. In general, such a polygon is not unique. We consider a special class of visibility graphs, namely Hamiltonian 2-separator chordal graphs, whose polygons are monotone. We describe parallel algorithms to verify if a given graph is a Hamiltonian 2-separator chordal graph and to reconstruct a polygon from this graph.
  • B.S. Panda, Vijay Natarajan and Sajal K. Das. Parallel algorithms for Hamiltonian 2-separator chordal graphs. Parallel Processing Letters, 12(1), 2002, 51-64.
    Proc. International Parallel and Distributed Processing Symposium, 2001. [Paper]