I primarily work in the fields of Computational geometry, Computational and applied topology. My work lies at the intersection of computer science (especially algorithms) and applied mathematics (especially applied topology, discrete and combinatorial geometry). I am particularly interested in developing effective and theoretically justified algorithms for data / shape analysis using geometric and topological ideas and methods. I aim to both provide theoretical understanding of various computational methods developed, and to apply them to practical domains, including computational biology, computational neuroanatomy, geometric modeling, computer graphics and visualization.

My research has been supported by NSF, NIH and DOE.

I am looking for motivated graduate students with interests in geometric/topological algorithms and data analysis, as well as strong background in algorithms, theory, and/or mathematics. I am happy to work with exceptional undergraduate students on data analysis projects. Students should have strong interests in algorithms design and data analysis applications.

Journal / Conference Publications -- Chronological order


  • Visualizing attributed graphs via terrain metaphor.
    Y. Zhang, Y. Wang and S. Parthasarathy. 23rd SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) 2017, pages 1325-1334.
  • Composing Tree Graphical Models with Persistent Homology Features for Clustering Mixed-Type Data.
    X. Ni, N. Quadrianto, Y. Wang and C. Chen. 34th Intl. Conf. Machine Learning (ICML) 2017, pages 2622-2631.
  • A quest to unravel the metric structure behind perturbed networks.
    S. Parthasarathy, D. Sivakoff, M. Tian and Y. Wang. Sympos. Comput. Geom. (SoCG) 2017, 53:1-53:16.
  • Declutter and Resample: Towards parameter free denoising.
  • M. Buchet, T. Dey, J. Wang and Y. Wang. Sympos. Comput. Geom. (SoCG) 2017, 23:1-23:16
  • Topological Analysis of Nerves, Reeb Spaces, Mappers, and Multiscale Mappers.
    T. Dey, F. Memoli and Y. Wang. Sympos. Comput. Geom. (SoCG) 2017, 36:1-36:16.
  • Metric embeddings with outliers
    A. Sidiropoulos, D. Wang and Y. Wang. ACM-SIAM Sympos. Discrete Alg. (SoDA) , pages 670--689, 2017.
  • Parameter-free topology inference and sparsification for data on manifolds
    T. K. Dey, Z. Dong and Yusu Wang. ACM-SIAM Sympos. Discrete Alg. (SoDA) , pages 2733--2747, 2017.
  • Optimal topological cycles and their application in cardiac trabeculae restoration
    P. Wu, C. Chen, Y. Wang, S. Zhang, C. Yuan, Z. Qian, D. Metaxas, L. Axel. 25th Biennial Intl. Conf. Information Processing in Medical Imaging (IPMI), 2017, pages 80-92 (Selected for Oral presentation.)
  • Graphons, mergeons, and so on!
    J. Eldridge, M. Belkin and Y. Wang. NIPS 2016, pages 2307-2315. (Selected for Oral presentation.)
  • SimBa: An Efficient Tool for Approximating Rips-Filtration Persistence via Simplicial Batch-Collapse
    T. K. Dey, D. Shi and Y. Wang. Euro. Symp. Algorithms (ESA) 2016, 35:1--35:16. The software package (developed by Dayu Shi) can be downloaded [here]
  • Multiscale Mapper: Topological summarization via codomain covers
    T. K. Dey, F. Memoli and Y. Wang. ACM-SIAM Sympos. Discrete Alg. (SoDA) 2016, pages 997-1013. Also available on arXiv:1504.03763v1
  • Efficient map reconstruction and augmentation via topological methods
    S. Wang, Y. Wang, and Y. Li. ACM SIGSPATIAL 2015. [project page] ( Won Best Paper Award!)
  • Beyond Hartigan consistency: Merge distortion metric for hierarchical clustering
    J. Eldridge, M. Belkin and Y. Wang. Conf. Learning Theory (COLT) 2015, pages 588-606. ( Won Best Student Paper Award! ).
  • Comparing graphs via persistence distortion
    T. Dey, D. Shi and Y. Wang. Sympos. Comput. Geom. (SoCG) 2015 , pages 491-506. Code by Dayu Shi can be downloaded here: [source-zip] and [exe-zip]
  • Strong equivalence of the interleaving and functional distortion metrics for Reeb graphs
    U. Bauer, E. Munch and Y. Wang. Sympos. Comput. Geom. (SoCG) 2015 , pages 461-475.
  • Maintaining contour trees of dynamic terrains
    P.K. Agarwal, T. Molhave, M. Revsbak, I. Safa, Y. Wang and J. Yang. Sympos. Comput. Geom. (SoCG) 2015 , pages 796-811.
  • Topological analysis of scalar fields with outliers
    M. Buchet, F. Chazal, T. Dey, F. Fan, S. Oudot and Y. Wang. Sympos. Comput. Geom. (SoCG) 2015 , pages 827-841.
  • Computing the Gromov-Hausdorff distance for metric trees
    P. Agarwal, K. Fox, A. Nath, A. Sidiroupolos and Y. Wang. ISAAC 2015 .
  • Graph induced complex on point data
    T. K. Dey, F. Fan and Y. Wang. Comput. Geom. 48(8): 575-588, 2015.
  • Learning with Fredholm Kernels
    Q. Que, M. Belkin and Y. Wang. NIPS 2014 , pages 2951-2959.
  • A collaborative visual analytics suite for protein folding research
    W. Harvey, I. Park, O. Rubel, V. Pascucci, P-T. Bremer, C. Li and Y. Wang. Journal of Molecular Graphics and Modelling (JMG) , 53, 59--71, 2014. The link is [here].
  • Measuring Distance Between Reeb Graphs
    U. Bauer, X. Ge, and Y. Wang. ACM Sympos. Comput. Geom. (SoCG) 2014, pages 464-473.
  • JS-Graph of Join and Split Trees
    S. Wang, Y. Wang and R. Wenger. ACM Sympos. Comput. Geom. (SoCG) 2014, pages 539-548.
  • Computing Topological Persistence for Simplicial Maps
    T. K. Dey, F. Fan, and Y. Wang. ACM Sympos. Comput. Geom. (SoCG) 2014, pages 345-354. The paper is [here]. The full version is also on arXiv at [here]. The software package (developed by Dayu Shi) is [here].
  • An efficient computation of handle and tunnel loops via Reeb graphs
    T. K. Dey, F. Fan, and Y. Wang. ACM Trans. Graphics (Special issue from SIGGRAPH), 2013, 32(4): 32:1-32:10. The paper is [here], and the supplementary file for proofs is [here]. The software can be downloaded [here].
  • Bilateral Blue Noise Sampling
    J. Chen, X. Ge, L-Y. Wei, B. Wang, Y. Wang, H. Wang, Y. Fei, K. Qian, J. Yong, W. Wang. ACM Trans. Graphics (Special issue from SIGGRAPH Asia), 2013, 32(4): 216:1-216:11. [Project page]
  • Measuring similarity between curves on 2-manifolds via homotopy area
    with E. W. Chambers. ACM Sympos. Comput. Geom. (SoCG) , 2013. The archive version is [here].
  • Graph induced complex on point data
    with T. K. Dey and F. Fan. ACM Sympos. Comput. Geom. (SoCG) , 2013. Full version is [here.] The accompanying software is [here.]
  • Weighted graph Laplace operator under Topological noise
    with T. K. Dey and P. Ranjan. ACM-SIAM Sympos. Discrete Alg. (SODA) , 2013. [pdf]
  • Reeb Graphs: Approximation and Persistence
    with T. K. Dey. Discrete and Computational Geometry 2012. [pdf]
  • Feature-preserving reconstruction of singular surfaces
    with T. K. Dey, X. Ge, Q. Que, I. Safa, and L. Wang. Computer Graphics Forum (special issue from SGP 2012), 31 (5), 1787--1796. 2012. [pdf]
  • Eigen-deformation of 3D models.
    with T. K. Dey and P. Ranjan. The Visual Computer 28 (6--8): 585--595, 2012. [video] (Conference version appeared in Computer Graphics International (CGI) 2012. )
  • Feature-aware streamline generation of planar vector fields via topological methods.
    with C. Luo and I. Safa. Computers and Graphics 36(6): 754--766, 2012.
  • Approximating Cycles in a Shortest Basis of the First Homology Group from Point Data
    with T. K. Dey and J. Sun. Inverse Problems 2012. [full-version][software by O. Busaryev]
  • Towards understading complex spaces: graph Laplacians on manifolds with singularities and boundaries
    with M. Belkin, Q. Que, and X. Zhou. COLT 2012. , 2012. [pdf]
  • Annotating simplices with a homology basis and its applications
    with O. Busaryev, S. Cabello, C. Chen and T. Dey. SWAT , 189--200, 2012.
  • Smolign: A Spatial Motifs Based Protein Multiple Structural Alignment Method
    with H. Sun, A. Sacan and H. Ferhatosmanoglu. IEEE//ACM Transactions on Computational Biology and Bioinformatics. 2011. [pdf]
  • Data Skeletonization via Reeb Graphs
    with X. Ge, I. Safa and M. Belkin. NIPS 2011. [pdf (full version)][software (in matlab)]
  • Reeb Graphs: Approximation and Persistence
    with T. K. Dey. ACM Symposium on Computational Geometry (SOCG) 2011. [pdf]
  • Enhanced Topology-sensitive Clustering by Reeb Graph Shattering
    with W. Harvey, O. Rubel, V. Pascucci, and P. -T. Bremer. TopoInVis 2011. [pdf]
  • Tracking a generator by persistence
    with O. Busaryev and T. K. Dey. Discrete Mathematics, Algorithms and Applications, 2 (4): 539--552, 2010. [DOI:10.1142/S1793830910000875]
  • Hausdorff distance under translation for points and balls
    with P. K. Agarwal, S. Har-Peled, and M. Sharir. ACM Trans. Alg. 6 (4), 2010. [ pdf ]
  • Persistent Heat Signature for Pose-oblivious Matching of Incomplete Models
    with T. K. Dey, K. Li, C. Luo, P. Ranjan, and I. Safa. Comput. Graph. Forum 2010 (SGP) . [pdf]
  • Generating and Exploring a Collection of Topological Landscapes for Visualization of Scalar-Valued Functions
    with W. Harvey. Comput. Graph. Forum 2010 (EuroVis) . (Won 3rd Best Paper Award at EuroVis 2010! ) [pdf]
  • A Randomized O(m log m) Time Algorithm for Computing Reeb Graph of Arbitrary Simplicial Complexes
    with W. Harvey and R. Wenger. ACM Symposium on Computational Geometry (SOCG) 2010. [pdf] and [code by W. Harvey]
  • Approximating Loops in a Shortest Homology Basis from Point Data
    with T. K. Dey and J. Sun. ACM Symposium on Computational Geometry (SOCG) 2010. [full-version][software by O. Busaryev]
    Note: the title for the journal version is Approximating Cycles in a Shortest Basis of the First Homology Group from Point Data.
  • Convergence, Stability, and Discrete Approximation of Laplace Spectra
    with T. K. Dey and P. Rajan. ACM-SIAM Symposium on Discrete Algorithms (SODA), 2010. [original pdf][modified pdf]
    (The modified pdf has a minor correction in the paper after Lemma 3.3.)
  • Integral Estimation from Point Cloud in d-Dimensional Space: A Geometric View
    with C. Luo and J. Sun. ACM Symposium on Computational Geometry (SOCG) , 2009. [pdf]
  • Constructing Laplace Operator from Point Clouds in R^d
    with M. Belkin and J. Sun. ACM-SIAM Symposium on Discrete Algorithms (SODA), 2009, 1031--1040. [pdf] [code (by J. Sun) ]
  • Exact Partial Curve Matching under the Frechet Distance
    ACM-SIAM Symposium on Discrete Algorithms (SODA), 2009, 645--654. [Original-version]
    with K. Buchin and M. Buchin, [ !! Improved-version !!]
  • Approximating Gradients for Meshes and Point Clouds via Diffusion Metric
    with C. Luo and I. Safa. Comput. Graph. Forum 2009, 28(5): 1497--1508. [pdf]
  • An enhanced partial order curve comparison algorithm and its application to analyzing protein folding trajectories
    with H. Sun and H. Ferhatosmanoglu. BMC BioInformatics 2008, 9 : 344. [web-server] [pdf ]
  • Distributed Roadmap Aided Routing in Sensor Networks
    with Z. Zheng, K. Fan, and P. Sinha. IEEE MASS 2008, 347--352. [pdf]
  • Discrete Laplace Operator for Meshed Surfaces
    with M. Belkin and J. Sun. ACM SOCG 2008. [pdf ] [code (by J. Sun) ]
  • Approximating Nearest Neighbor Among Triangles in Convex Position
    Information Processing Letters. 2008. [ pdf ]
  • Towards Unsupervised Segmentation of Semi-rigid Low-resolution Molecular Surfaces
    with L. J. Guibas. Algorithmica. 48 (4): 433--448 (Aug. 2007). [ pdf ]
  • Placement-Proximity-Based Voltage Island Grouping under Performance Requirement
    with H. Wu, M. Wong, and I. Liu. IEEE Trans. Computer-Aided Design. 26 (7): 1256--1269 (July 2007). [ pdf ]
  • LFM-Pro: A Tool for Detecting Significant Local Structural Sites in Proteins
    with A. Sacan, O. Ozturk and H. Ferhatosmanoglu. BioInformatics. 23 (6): 709--716 (Mar. 2007). [ pdf ]
  • Efficient Algorithms for Contact-map Overlap Problem
    with P. K. Agarwal and N. Mustafa. J. Comput. Biology (JCB) . 14 (2): 131--143 (Mar. 2007). [ pdf ]
  • An Enhanced Partial Order Curve Comparison over Multiple Protein Folding Trajectories
    with H. Sun, H. Ferhatosmanoglu, and M. Ota, Proc. Intl. Conf. Computational Systems Bioinformatics, 2007, 299--310.
  • Relations Between Two Common Types of Rectangular Tiling
    Proc. Intl. Symp. Algorithms and Computation, LNCS 4288, Springer-Verlag, 2006, 193--202.
  • Frechet Distances for Curves, Revisited
    with B. Aronov, S. Har-Peled, C. Kauner and C. Wenk, ESA 2006, 52--63.
  • Distance-sensitive routing and information brokerage in sensor networks
    with S. Funke, L. J. Guibas and A. Nguyen. DOCSS 2006, 234--251.
  • A Two-Dimensional Kinetic Triangulation with Near-Quadratic Topological Changes
    with P. K. Agarwal and H. Yu. Discrete and Computational Geometry (DCG) 36 (4): 573--592 (Dec. 2006). [ pdf ]
  • Extreme Elevation on a 2-Manifold
    with P. K. Agarwal, H. Edelsbrunner, and J. Harer. Discrete and Computational Geometry (DCG). 36 (4): 553--572 (Dec. 2006).
  • Segmenting molecular surfaces
    with V. Natarajan, P. Bremer, V. Pascucci and B. Hamann. Computer Aided Geometric Design (CAGD). 23: 495--509 (June 2006). [ pdf ]
  • Near-linear time approximation algorithms for curve simplification in two and three-dimensions
    with P. K. Agarwal, S. Har-Peled, and N. Mustafa. Algorithmica. 42(3/4): 203--221 (2005). [ pdf ]
  • Post-placement voltage island generation under performance requirement
    with H. Wu, I. Liu, and M. D. F. Wong, ICCAD 2005, 309--316
  • Low bounds for sparse geometric spanners
    with P. K. Agarwal and P. Yin, SODA 2005, 670--671
  • Coarse and reliable geometric alignment for protein docking
    with P. K. Agarwal, P. Brown, H. Edelsbrunner and J. Rudolph, PSB 2005, 66--77
  • Shape fitting with outliers
    with S. Har-Peled. SIAM J. Comput. 33(2): 269--285 (2004). [ pdf ]
  • Computing the writhing number of a polygonal knot
    with P. K. Agarwal and H. Edelsbrunner. Discrete and Computational Geometry (DCG) 32(1): 37--53 (2004). [ pdf ]
  • A 2D kinetic triangulation with near-quadratic topological changes
    with P. K. Agarwal and H. Yu, SOCG 2004, 180--189
  • Extreme elevation on a 2-manifold
    with P. K. Agarwal, H. Edelsbrunner and J. Harer, SOCG 2004, 357--365
  • Hausdorff distance under translation for points and balls
    with P. K. Agarwal, S. Har-Peled and M. Sharir, SOCG 2003, 282--291
  • Shape fitting with outliers
    with S. Har-Peled, SOCG 2003, 29--38
  • Near-linear time approximation algorithms for curve simplification
    with P. K. Agarwal, S. Har-Peled, and N. Mustafa, ESA 2002, 29--41
  • Computing the writhing number of a polygonal knot
    with P. K. Agarwal and H. Edelsbrunner, SODA 2002, 791--799
  • Occlusion culling for fast walkthrough in urban areas
    with P. K. Agarwal and S. Har-Peled, EuroGraphics (short paper) 2001.