Publications

2020

Persistence of the Conley Index in Combinatorial Dynamical Systems. T. K. Dey, M. Mrozek, and R. Slechta, February 2020, Proc. Internat. Sympos. Comput. Geom. (2020) (SoCG 2020).

An efficient algorithm for 1-dimensional (persistent) path homology. T. K. Dey, T. Li, and Y. Wang, January 2020, arxiv:https://arxiv.org/abs/2001.09549, Proc. Internat. Sympos. Comput. Geom. (2020) (SoCG 2020).

2019

Road Network reconstruction from Satellite Images with Machine Learning Supported by Topological Methods. T. K. Dey, J. Wang, and Y. Wang, September 2019, arxiv:https://arxiv.org/pdf/1909.06728.pdf. A shoter version appears in SIGSPATIAL 2019.

Computing Minimal Persistent Cycles: Polynomial and Hard Cases. T. K. Dey, T. Hou, and S. Mandal. Proceedings ACM-SIAM Sympos. Discrete Algorithms (SODA 20). arxiv: https://arxiv.org/abs/1907.04889

Computing height persistence and homology generators in R^3 efficiently. T. K. Dey , Proc. 30th ACM-SIAM Sympos. Discrete Algorithms, 2019 (SODA 19), pages 2649--2662. arxiv version: https://arxiv.org/abs/1807.03655. Talk Slides

2018

Edge contraction in persistence-generated discrete Morse vector fields. T. K. Dey and R. Slechta. Proc. SMI 2018, Computers & Graphics, .Vol. 74, 33-43. Journal version: https://doi.org/10.1016/j.cag.2018.05.002

Persistent homology of Morse decompositions in combinatorial dynamics. T. K. Dey, M. Juda, T. Kapela, J. Kubica, M. Lipinski, M. Mrozek. https://arxiv.org/abs/1801.06590. 2018. SIAM J. on Applied Dynamical System, Vol. 18, Issue 1, 510--530, 2019.

Computing Bottleneck Distance for 2-D Interval Decomposable Modules. T. K. Dey, C. Xin. Proc. 34th Internat. Sympos. Comput. Geoem., 32:1--32:15 (SoCG 2018).
The n-D version: Computing Bottelneck Distance for Multi-parameter Interval Decomposable Persistence Modules. Preprint, September, 2019.

Graph Reconstruction by Discrete Morse Theory. T. K. Dey, J. Wang and Y. Wang. Proc. Internat. Sympos. Comput. Geom., 31:1--31:15 (SoCG 2018).

Protein Classification with Improved Topological Data Analysis. T. K. Dey and S. Mandal. Proc. Workshop on Algorithms in Bioinformatics (WABI 2018), 6:1--6:13. DOI 10.4230/LIPIcs.WABI.2018.6 Web-page: http://web.cse.ohio-state.edu/~dey.8/proteinTDA/

2017

Improved Image Classification using Topological Persistence. T. K. Dey, S. Mandal, W. Varcho. Proc. Vision Modeling and Visualization., (VMV 2017). http://dx.doi.org/10.2312/vmv.20171272 Web-page: http://web.cse.ohio-state.edu/~dey.8/imagePers/

Efficient Algorithms for Computing a Minimal Homology Basis. T. K. Dey, T. Li, and Y. Wang. Proc. LATIN 2018: Theoretical Informatics, LNCS, Vol. 10807, 376--398 (LATIN 2018).

Temporal Hierarchical Clustering. T. K. Dey, A. Rossi, and A. Sidiropoulos. Proc. 28th Internat. Symposium on Algorithms and Computation (ISAAC 2017). https://arxiv.org/abs/1707.09904

Topological analysis of nerves, Reeb spaces, mappers, and multiscale mappers. T. K. Dey, F. Memoli, and Y. Wang. Proc. Internat. Sympos. Comput. Geom. (2017) (SoCG 2017). [full version]. [talk slides].

Declutter and resample: Towards parameter free denoising. M. Buchet, T. K. Dey, J. Wang, and Y. Wang. Proc. Internat. Sympos. Comput. Geom. (2017), (SoCG 2017). Full Version

Parameter-free topology inference and sparsification for data on manifolds. T. K. Dey, Z. Dong, and Y. Wang. (2015), older version at arXiv:1505.06462. Proc. ACM-SIAM Sympos. Discrete Algorithms (SODA 2017). [talk slides]

2016

Multiscale Mapper: Topological summarization via codomain covers. T. K. Dey, F. Memoli, and Y. Wang. ACM-SIAM Sympos. Discrete Algorithms (SODA 2016) Older version arXiv: 1504.03763v1 [talk slides]. SODA version.

2015

Comparing graphs via persistence distortion. T. K. Dey, D. Shi and Y. Wang. 31st Annu. Sympos. Comput. Geom. (SoCG 15). [GraphComp software]

Topological analysis of scalar fields with outliers. M. Buchet, F. Chazal, T. K. Dey, F. Fan, S. Oudot and Y. Wang. 31st Annu. Sympos. Comput. Geom. (SoCG 15). arXiv:1412.1680.

Spectral concentration and greedy k-clustering. T. K. Dey, A. Rossi., and A. Sidiropoulos, arXiv:1404.1008v2. Comput. Geom. Theory & Applications (2018).

2014

Dimenison detection with local homology. T. K. Dey, F. Fan, and Y. Wang, Canadian Conf. Comput. Geom. (CCCG 2014), Full version arXiv: 1405.3534. [Talk Slide]

Computing topological persistence for simplicial maps. T. K. Dey, F. Fan, and Y. Wang., (SoCG 2014), Proc. 30th Annu. Sympos. Comput. Geom. (2013). (our algorithm works for any finite field--see the conclusion of updated Full version). [SimpPers software] [Talk slide]

Automatic posing of meshed human model using point clouds. T. K. Dey, B. Fu, H. Wang, and L. Wang., (SMI 2014), Computers & Graphics, Vol. 46, pages 14--24. [Talk slide] [Video link]

2013

Edge contractions and simplicial homology. T. K. Dey, A. N. Hir ani, B. Krishnamoorthy, and G. Smith. April, 2013. arXiv:1304.0664

Graph induced complex on point data. T. K. Dey, F. Fan, and Y. Wang., (SoCG 2013) Proc. 29th Annu. Sympos. Comput. Geom. (2013), pages 107--116. [Talk slides] [Web-page] [GICsoftware]

The compressed annotation matrix: an efficient data structure for computing persistent cohomology. J.-D. Boissonnat, T. K. Dey, C. Maria, (ESA 2013), LNCS 8125, 2013.

Localized Delaunay Refinement for Piecewise-Smooth Complexes. T. K. Dey and A. Slatton (SoCG 2013) Proc. 29th Annu. Sympos. Comput. Geom. (2013), pages 47--56. [software LocPSC] [Talk Slides]

Voronoi-based Feature Curves Extraction for Sampled Singular Surfaces. T. K. Dey and L. Wang (SMI 2013), Computers & Graphics, special issue of Shape Modeling International (2013), Vol. 37 (6), 659--668. [Web-page] [software SingularCocone]

Weighted graph Laplace operator under topological noise. T. K. Dey, P. Ranjan, and Y. Wang. (SODA 2013), ACM-SIAM Symposium on Discrete Algorithms (2013).

2012

Animating bubble interactions in a liquid foam. O. Busaryev, T. K. Dey, H. Wang, and R. Zhong. (SIGGRAPH 2012), ACM Trans. Graphics, Vol. 31 (4), 2012. [Video link]

Feature-Preserving reconstruction of singular surfaces. T. K. Dey, X. Ge, Q. Que, I. Safa, L. Wang, Y. Wang. Computer Graphics Forum, Vol. 31 (5), 1787--1796, special issue of Eurographics Sympos. Geometry Processing (SGP 2012). [Talk slides]

Topological Persistence for circle valued maps. D. Burghelea and T. K. Dey. Discrete & Computational Geometry, Volume 50, No. 1 (2013), 69--98. Also in arXiv:1104.5646. April, 2011.

Eigen deformation of 3D models. T. K. Dey, P. Ranjan and Y. Wang. Proc. Computer Graphics International (CGI 2012). The Visual Computer Volume 28, Numbers 6-8 (2012), 585-595, DOI: 10.1007/s00371-012-0705-0 [Talk slides] [Video]

Annotating simplices with a homology basis and its applications. O. Busaryev, S. Cabello, C. Chen, T. K. Dey, and Y. Wang. 13th Scandinavian Sympos. Workshops Algorithm Theory (SWAT 2012). Lecture Notes in Computer Science Volume 7357, 2012, pp 189-200. [Talk slides] Earlier arxiv version arXiv:1107.3793v2

2011

Localized Delaunay refinement for volumes. T. K. Dey and A. G. Slatton. Computer Graphics Forum, Vol 30 (5), 1417--1426. Special issue Proc. of Eurographics Sympos. Geometry Processing (SGP 2011). [Web-page] [Talk slides] [Software]

Reeb graphs: approximation and persistence. T. K. Dey and Y. Wang. Proc. 27th Annu. Sympos. Comput. Geom. (SOCG 2011), 226--235. Extended version in Discrete & Computational Geometry, Vol. 49 (2013), 46--73. [Extended version]

2010

Localized Delaunay refinement for sampling and meshing. T. K. Dey, J. A. Levine, and A. Slatton. Computer Graphics Forum. Vol. 29 (5)(2010), 1723--1732. Specail issue of Proc. Eurographics Sympos. Geometry Processing. (SGP 2010). [Talk slides] [Web-page] [Software] [Extended version]

Persistent heat signature for pose-oblivious matching of incomplete models. T. K. Dey, K. Li, C. Luo, P. Ranjan, I. Safa, and Y. Wang. Computer Graphics Forum. Vol. 29 (5) (2010), 1545--1554. Special isue of Proc. Sympos. Geometry Processing. (SGP 2010). [Talk slides]

Tracking a generator by persistence. O. Busaryev, T. K. Dey, and Y. Wang. 16th Annu. Internat. Computating and Combinatorics Conf. (COCOON 2010), 278--287. Journal version in Discrete Mathematics, Algorithms and Applications, Vol 2, Issue 4, 2010, 539--552. DOI:10.1142/S1793830910000875.

Optimal homologous cycles, total unimodularity, and linear programming. T. K. Dey, A. Hirani, and B. Krishnamoorthy. SIAM J. Computing, Vol. 40, pp 1026--1044. Prelim. version in 42nd ACM Sympos. Comput. Theory (STOC 2010), 221--230. arXiv:1001.0338v1[math.AT], 2nd January, 2010. [web-page] [combined talk-slides]

Approximating cycles in a shortest basis of the first homology group from point data. T. K. Dey, J. Sun, and Y. Wang. Inverse Problems, Vol. 27 (2011), 124004. doi:10.1088/0266-5611/27/12/124004

An earlier version appeared with title ``Approximating loops in a shortest homology basis from point data" in Proc. 26th Annu. Sympos. Comput. Geom. (SOCG 2010), 166--175. arXiv:0909.5654v1[cs.CG], 30th September 2009. [web-page] [software] [talk-slides]

Convergence, Stability, and Discrete Approximation of Laplace Spectra. T. K. Dey, P. Ranjan, and Y. Wang. Proc. ACM/SIAM Sympos. Discrete Algorithms (SODA 2010), 650--663. Paper with a minor correction.

2009

Repairing and meshing imperfect shapes with Delaunay refinement. O. Busaryev, T. K. Dey, J. A. Levine. Proc. SIAM/ACM Joint Conf. Geometric and Physical Modeling (SPM 2009), 25--33.

Isotopic Reconstruction of Surfaces with Boundaries. T. K. Dey, K. Li., E. A. Ramos, and R. Wenger. Proc. Sympos. Geom. Processing.(SGP09), special issue of Computer Graphics Forum, Vol. 28, No. 5 (2009), 1371--1382. [Web-page] [Software] [talk-slide] [Video]

Cut Locus and Topology from Surface Point Data. T. K. Dey, K. Li. Proc. 25th Ann. Sympos. Comput. Geom.(SOCG09), 2009, 125--134.

Delaunay meshing of piecewise smooth complexes without expensive predicates. T. K. Dey, J. A. Levine. Algorithms, vol. 2, issue 4 (2009), 1327--1349. doi:10.3390/a2041327 Tech Report, OSU-CISRC-7/08-TR40, July 2008. [Video] [Software] [Talk-slide] [Web-page]

Persistence-based Handle and Tunnel Loops Computation Revisited for Speed Up. T. K. Dey and K. Li. Shape Modeling International (SMI09), 2009. Special issue of Computer & Graphics, Article in press, doi:10.1016/j.cag.2009.03.008. [Software]

2008

Recursive geometry of the flow complex and topology of the flow complex filtration. K. Buchin, T. K. Dey, J. Giesen, and M. John. Comput. Geom. Theory Application. (2008), vol. 40, 115--157.

2007

Normal variation with adaptive feature size (2007)

Maintaining Deforming Surface Meshes. S.-W. Cheng and T. K. Dey. Proc. 19th ACM-SIAM Sympos. Discrete Algorithms (SODA 2008) (2008), 112--121.

Delaunay Edge Flips in Dense Surface Triangulations. S.-W. Cheng and T. K. Dey. Pre-print arXiv:cs.CG/0712.1959, 2007. short version in EuroCG 2008.

Note: We are retracting this result due to a bug in a Lemma (Lemma 3.1). We are trying to salvage the other results without using Lemma 3.1.

A practical Delaunay meshing algorithm for a large class of domains. S.-W. Cheng, T. K. Dey, and J. A. Levine. Proc. 16th Internat. Meshing Roundtable (IMR 2007), 477--494. [Talk slides]

On computing handle and tunnel loops. T. K. Dey, K. Li, and J. Sun. IEEE Proc. Internat. Conf. Cyberworlds (NASAGEM workshop) (2007), 357--366. Journal version is in Computer-Aided Design, in press, doi:10.1016/j.cad.2009.01.001. [Talk slides] HandleTunnel software

Stability of critical points with interval persistence. T. K. Dey and R. Wenger. Discrete & Computational Geometry, vol 38 (2007), 479--512. Tech Report OSU-CISRC-4/06-TR47, April 2006.

Delaunay meshing of isosurfaces. T. K. Dey and J. A. Levine. Proc. Shape Modeling International (SMI 2007), 241--250. DelIso software

Delaunay refinement for piecewise smooth complexes. S.-W. Cheng, T. K. Dey, and E. A. Ramos. Proc. 18th Annu. ACM-SIAM Sympos. Discrete Algorithms (SODA 2007), 1096--1105. Journal Version in Discrete & Comput. Geom., 2008, article in press. doi.10.1007/s00454-008-9109-3. Extended Full Version

2006

Defining and computing curve-skeletons with medial geodesic function. T. K. Dey and J. Sun. Proc. Sympos. Geometry Processing (SGP 2006), 143--152. CurveSkel Software

Identifying flat and tubular regions of a shape by unstable manifolds. S. Goswami, T. K. Dey, and C. Bajaj. Proc. 11th ACM Sympos. Solid Modeling Applications (SPM 2006), 27--37.

Normal and feature approximations from noisy point clouds. T. K. Dey and J. Sun. Proc. FST&TCS 2006, LNCS 4337, 21--32. NormFet software

Anisotropic surface meshing. S.-W. Cheng, T. K. Dey and E. A. Ramos. Proc. ACM-SIAM Sympos. Discrete Algorithms (SODA 2006), 202--211.

2005

An Adaptive MLS Surface for Reconstruction with Guarantees. T. K. Dey and J. Sun. Symposium on Geometry Processing (SGP 2005), 43--52. Conference version. Extended version. AMLS Software.

Also see: Extremal Surface Based Projections Converge and Reconstruct with Isotopy. T. K. Dey, S. Goswami and J. Sun. Technical Report OSU-CISRC-05-TR25, April, 2005.

An early attempt: T. K. Dey, S. Goswami and J. Sun. Smoothing noisy point clouds with Delaunay preprocessing and MLS. Tech-report OSU-CISRC-3/04-TR17, 2004.

Normal Estimation for Point Clouds : A Comparison Study for a Voronoi Based Method. T. K. Dey, G. Li and J. Sun. Eurographics Sympos. on Point-Based Graphics (2005), 39--46.

Polygonal Surface Remeshing with Delaunay Refinement. T. K. Dey, G. Li and T. Ray. Proc.14th Internat. Meshing Roundtable, (IMR 2005), 343--361. Journal version in Engineering with Computers, vol. 26, page 289--301, 2010. Conference version Extended version SurfRemesh software

Weighted Delaunay Refinement for Polyhedra with Small Angles. S.-W. Cheng, T. K. Dey and T. Ray. Proc.14th Internat. Meshing Roundtable (IMR 2005), 325--342.

Critical points of distance to an epsilon-sampling of a surface and flow-complex- based surface reconstruction. T. K. Dey, J. Giesen, E. A. Ramos and B. Sadri. Proc. 21st Annu. Sympos. Comput. Geom., (SOCG 2005), 218--227. ( Invited Journal version in Internat. J. Comput. Geom. Applications, Vol 18, 2008, 29--61.) Extended version.

Manifold Reconstruction from Point Samples. Siu-Wing Cheng, T. K. Dey and E. A. Ramos. Proc. ACM-SIAM Sympos. Discrete Algorithms, (SODA 2005), 1018--1027. Extended Abstract [Talk slides]

Delaunay Triangulations Approximate Anchor Hulls. T. K. Dey, Joachim Giesen and Samrat Goswami. Comput. Geom. Theory Applications, vol. 36 (2006), 131--143. (prelim. version in (SODA 2005), 1028-1037).

Quality meshing for polyhedra with small angles. S.-W. Cheng, T. K. Dey, E. Ramos and T. Ray. International J. Comput. Geom. & Applications, Vol. 15, No. 4 (2005), 421--461. Prelim. version in (SOCG 2004). Extended version QualMesh Software

2004

Provable surface reconstruction from noisy samples. T. K. Dey and S. Goswami. Computationa Geometry Theory & Applications, vol. 35, 2006, 124--141. Prelim. version in (SOCG 2004). RobustCocone software

2003

Approximating the Medial Axis from the Voronoi Diagram with a Convergence Guarantee. T. K. Dey and W. Zhao. Algorithmica, vol. 38, 2003, 179--200. Medial Software

Hierarchy of surface models and irreducible triangulation. S.-W. Cheng, T. K. Dey and S.-H. Poon. Computational Geometry : Theory & Applications, Vol. 27, No. 2 (2004), 135--150

Shape segmentation and matching with flow discretization. T. K. Dey, J. Giesen and S. Goswami. Proc. Workshop Algorithms Data Strucutres (WADS 03), LNCS 2748, F. Dehne, J.-R. Sack, M. Smid Eds., 25--36 Extended version Segmatch Software

Also see the following paper: Shape segmentation and matching from noisy point clouds. T. K. Dey, J. Giesen and S. Goswami. Proc. Eurographics Sympos. Point-Based Graphics (2004), Marc Alexa and S. Rusinkiewicz (eds) (2004), 193--199.

Quality meshing with weighted Delaunay refinement. S.-W. Cheng and T. K. Dey.SIAM J. Computing, Vol. 33 (2003), 69--93 Preliminary version in (SODA 2002).

Shape dimension and approximation from samples. T. K. Dey, J. Giesen, S. Goswami and W. Zhao. Discrete & Comput. Geom., vol 29, 419--434 (2003) Prelim. version in (SODA 2002).

2002

A simple algorithm for homeomorphic surface reconstruction. N. Amenta, S. Choi, T. K. Dey and N. Leekha. Intl. Journal on Computational Geometry & Applications, vol. 12, (2002), 125--141. Prelim. version in (SOCG 2000).

Also see the following paper: Tight Cocone : A water-tight surface reconstructor. T. K. Dey and S. Goswami. J. Computing Inform. Sci. Engin., vol. 30, (2003), 302--307. Cocone Software

2001

Dynamic skin triangulation. H-L. Cheng, T. K. Dey, H. Edelsbrunner and J. Sullivan. Discrete Comput. Geom., vol. 25, (2001), 525--568 Prelim. version in (SODA 2001).

2000

Sliver exudation. S.-W. Cheng, T. K. Dey, H. Edelsbrunner, M. A. Facello and S.-H. Teng.J. ACM, Vol. 47, (2000), 883--904 Prelim. version in (SOCG 1999).

1999

A simple provable algorithm for curve reconstruction. T. K. Dey and P. Kumar.Proc. 10th. ACM-SIAM Symposium on Discrete Algorithms (SODA '99) , 1999, 893--894

Topology preserving edge contraction. T. K. Dey, H. Edelsbrunner, S. Guha and D. Nekhayev. Publications de l' Institut Mathematique (Beograd), Vol. 60 (80), 23--45, 1999

Transforming curves on surfaces. T. K. Dey and S. Guha. Journal of Computer and System Sciences, vol. 58, 1999, 297--325. Preliminary version in IEEE (FOCS 1995), 266-274

1998

Improved bounds for planar k-sets and related problems. T. K. Dey. Invited paper in a special issue of Discrete & Computational Geometry, Vol. 19, No. 3, (1998), 373-382 Prelim. version in IEEE (FOCS 1997).

Extremal problems for geometric hypergraphs. T. K. Dey and J. Pach.Discrete & Computational Geometry, Vol. 19, No. 4, (1998), 473--484. Preliminary version in ISAAC 96, LNCS 1178, 105-114

Computational Topology. T. K. Dey, H. Edelsbrunner and S. Guha. Advances in Discrere and Computational Geometry, eds. B. Chazelle, J. E. Goodman and R. Pollack. Contemporary Mathematics, AMS, Providence, 1998 .

Visibility with multiple reflections. B. Aronov, A. Davis, T. K. Dey, S. P. Pal and D. C. Prasad. Discrete & Computational Geometry, Vol. 20, No. 61, (1998), 61--78. Preliminary version in 5th SWAT, 1996, LNCS 1097, 284-295

1994

Counting triangle crossings and halving planes. T. K. Dey and H. Edelsbrunner.Invited paper in a special issue, Discrete & Computational Geometry, Vol. 12 (1994), 281--289 Prelim. version in SoCG 1995.

1993

On counting triangulations in d dimensions. T. K. Dey. Computational Geometry: Theory and Applications, Vol. 3 (1993), 315--325.