Key Publications
All Other Publications

Books and Surveys
Delaunay Mesh Generation.
Siu-Wing Cheng, Tamal K. Dey, Jonathan R. Shewchuk. To be Published by CRC Press (2012 December). Details and Sample Chapters including a new algorithm for meshing 3D polyhedra with arbitrary small angles (chapter 9).


Order link
   
Curve and Surface Reconstruction : Algorithms with Mathematical Analysis.
T. K. Dey. Published by Cambridge University Press (2007). Preface and contents.  Two chapters.

Erratum

Order link

 Delaunay mesh generation of three dimensional domains.
T. K. Dey. Technical Report OSU-CISRC-9/07-TR64, October, 2007. To appear in Tessellations in the sciences: Virtues, Techniques and Applications of Geometric Tilings, eds. R. van de Weygaert, G. Vegter, J. Ritzerveld & V. Icke, Springer-Verlag, 2009.


Delaunay meshes are used in various applications such as finite element analysis, computer graphics rendering, geometric modeling, and shape analysis. As the applications vary, so do the domains to be meshed. Although meshing of geometric domains with Delaunay simplices have been around for a while, provable techniques to meshing various types of three dimenisonal domains have been developed only recently. We devote this article to presenting these techniques. We survey various related results and detail a few core algorithms that have provable guarantees and are amenable to practical implementation. Delaunay refinement, a paradigm originally developed for guaranteeing shape quality of mesh elements, is a common thread in these algorithms. We finish the article by listing a set of open questions.
 
Sample based geometric modeling
T. K. Dey. Chapter in Geometric and Algorithmic Aspects of Computer-Aided Design and Manufacturing, eds Janardan, Smid, Dutta. DIMACS series in Discrete Mathematics and Theoretical Computer Science, Volume 67, 2005.

A new paradigm for digital modeling of physical objects from sample points is fast emerging due to recent advances in scanning technology. Researchers are investigating many of the traditional modeling problems in this new setting. We name this new area as sample based geometric modeling. The purpose of this article is to expose the readers to this new modeling paradigm through three basic problems, namely surface reconstruction, medial axis approximation, and shape segmentation. The algorithms for these three problems developed by the author and his co-authors are described.
Curve and surface reconstruction
T. K. Dey. Chapter in Handbook of Discrete and Computational Geometry, Goodman and O' Rourke eds., CRC press, 2nd edition (2004)

The problem of reconstructing a shape from its sample appears in many scientific and engineering applications. Because of the variety in shapes and applications, many algorithms have been proposed over the last two decades, some of which exploit application-specific information and some of which are more general. We will concentrate on techniques that apply to the general setting and have proved to provide some guarantees on the quality of reconstruction.


Papers
  Spectral concentration, robust k-center, and simple clustering
T. K. Dey,  A. Rossi., and A. Sidiropoulos
arXiv:1404.1008

It has been recently shown by Oveis Gharan, and Trevisan  that for any $k\geq 1$, any graph with sufficiently large gap between the $k$-th and $(k+1)$-th eigenvalue of its normalized Laplacian admits a partition into $k$ clusters, each having small external conductance, and large internal conductance.
Moreover, they gave an iterative algorithm for finding such a partition.

We present a simple spectral algorithm for finding a partition that is guaranteed to be close to the one obtained by \cite{DBLP:conf/soda/GharanT14}, for graphs of bounded degree, and with slightly larger spectral gap. More precisely, we show that approximating the robust $k$-center problem in the eigenspace results in a provably good partition. Combining our result with a greedy 3-approximation for robust $k$-center due to Charikar \etal~\cite{DBLP:conf/soda/CharikarKMN01} gives us the desired spectral partitioning algorithm. We also show how a simple greedy algorithm for $k$-center can be implemented in time $O(n k^2 \log n)$. Finally, we evaluate our algorithm on some real-world, and synthetic inputs.

          
  Computing topological persistence for simplicial maps
T. K. Dey,  F. Fan, and Y. Wang., (SoCG 2014), Proc. 30th Annu. Sympos. Comput. Geom. (2013).  Full version 
arXiv:1208.5018v4
[SimpPers software]

Algorithms for persistent homology and zigzag persistent homology are well-studied for homology modules where homomorphisms are induced by inclusion maps. In this paper, we propose a practical algorithm for computing persistence under Z_2 coefficients for a sequence of general simplicial maps.

First, we observe that it is not hard to simulate simplicial maps by inclusion maps but not necessarily in a monotone direction. This, combined with the known algorithms for zigzag persistence, provides an algorithm for computing the persistence induced by simplicial maps.

Our main result is that the above simple minded approach can be improved for a sequence of simplicial maps given in a monotone direction. The improvement results from the use of the so-called annotations that we show can determine the persistence of simplicial maps using a lighter data structure. A consistent annotation through atomic operations implies the maintenance of a consistent cohomology basis, hence a homology basis by duality. While the idea of maintaining a cohomology basis through an inclusion is not new, maintaining them through a vertex collapse is new, which constitutes an important atomic operation for simulating simplicial maps. Annotations support the vertex collapse in addition to the usual inclusion quite naturally.

Finally, we exhibit an application of this new tool in which we approximate the persistence diagram of a filtration of Rips complexes where vertex collapses are used to tame the blow-up in size.
          
  Edge contractions and simplicial homology
T. K. Dey,  A. N. Hir
ani, B. Krishnamoorthy, and G. Smith. April, 2013. arXiv:1304.0664

We study the effect of edge contractions on simplicial  homology because these contractions have turned to be useful in various  applications involving topology. It was observed previously that   contracting edges that  satisfy the so called  link condition preserves homeomorphism  in low dimensional complexes, and homotopy in general.   But, checking the link condition involves computation in all dimensions,  and hence can be costly, especially in high dimensional  complexes. We define a weaker and more local condition called the p-link condition for each dimension p, and study its  effect on edge contractions. We prove the following: (i) For homology  groups, edges satisfying the  p- and (p-1)-link conditions can be contracted without  disturbing the p-dimensional homology group. (ii) For  relative homology groups, the (p-1)-, and the (p-2)-link conditions  suffice to guarantee that the contraction does not introduce any new class in  any of the resulting relative  homology groups, though some of the existing classes can be  destroyed. Unfortunately, the surjection in relative homolgy groups  does not guarantee that no new relative  torsion is created. (iii) For torsions, edges satisfying the p-link condition alone can be contracted without creating any new relative torsion and the p-link condition cannot be avoided.  The  results on relative homology and relative torsion are motivated by  recent results on computing optimal homologous chains, which state  that such problems can be solved by linear programming if the  complex has no relative torsion.  Edge contractions that do not  introduce new relative torsions, can safely be availed in these contexts.

          
  Graph induced complex on point data (full version)
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 efficiency of extracting topological information from point data depends largely on the complex that is built on top of the data points. From a computational viewpoint, the most favored complexes for this purpose have so far been Vietoris-Rips and witness complexes. While the Vietoris-Rips complex is simple to compute and is a good vehicle for extracting topology of sampled spaces, its size is huge--particularly in high dimensions. The witness complex on the other hand enjoys a smaller size because of a subsampling, but fails to capture the topology in high dimensions unless imposed with extra structures. We investigate a complex called the graph induced complex that, to some extent, enjoys the advantages of both. It works on a subsample but still retains the power of capturing the topology as the Vietoris-Rips complex. It only needs a graph connecting the original sample points from which it builds a complex on the subsample thus taming the size considerably. We show that, using the graph induced complex one can (i) infer the one dimensional homology of a manifold from a very lean subsample, (ii) reconstruct a surface in three dimension from a sparse subsample without computing Delaunay triangulations, (iii) infer the persistent homology groups of compact sets from a sufficiently dense sample. We provide experimental evidences in support of our theory.

          
  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.


Persistent homology with coefficients in a field F coincides with the same for cohomology because of duality. We propose an implementation of a recently introduced algorithm for persistent cohomology that attaches annotation vectors with the simplices. We separate the representation of the simplicial complex from the representation of the cohomology groups, and introduce a new data structure for maintaining the annotation matrix, which is more compact and reduces substancially the amount of matrix operations. In addition, we propose a heuristic to simplify further the representation of the cohomology groups and improve both time and space complexities. The paper provides a theoretical analysis,  as well as a detailed experimental study of our implementation and comparison with state-of-the-art software for persistent homology and cohomology.

Note: Also see our ``computing topological persistence for simplicial maps" paper which motivated this implementation.
          
  An efficient computation of handle and tunnel loops via Reeb graphs.
T. K. Dey,  F. Fan, and Y. Wang. ACM Trans. Graphics (Siggraph 2013), Vol. 32 (4). Supplementary file for proofs.

[Web-page] [Software ReebHanTun] [Talk slides]

A special family of non-trivial loops on a surface called handle and tunnel loops associates closely to geometric features of ``handles" and ``tunnels" respectively in a 3D model. The identification of these handle and tunnel loops can benefit a broad range of applications from topology simplification / repair, and surface parameterization, to feature and shape recognition. Many of the existing efficient algorithms for computing non-trivial loops cannot be used to compute these special type of loops. The two algorithms known for computing handle and tunnel loops provably have a serious drawback that they both require a tessellation of the interior and exterior spaces bounded by the surface. Computing such a tessellation of three dimensional space around the surface is a non-trivial task and can be quite expensive. Furthermore, such a tessellation may need to refine the surface mesh, thus causing the undesirable side-effect of outputting the loops on an altered surface mesh.

In this paper, we present an efficient algorithm to compute a basis for handle and tunnel loops without requiring any 3D tessellation. This saves time considerably for large meshes making the algorithm scalable while computing the loops on the original input mesh and not on some refined version of it. We use the concept of the Reeb graph which together with several key theoretical insights on linking number provide an initial set of loops that provably constitute a handle and a tunnel basis. We further develop a novel strategy to tighten these handle and tunnel basis loops to make them geometrically relevant. We demonstrate the efficiency and effectiveness of our algorithm as well as show its robustness against noise, and other anomalies in the input.

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

The Delaunay refinement, a versatile method of mesh generation, is plagued by memory thrashing when required to generate large output meshes. To address this space issue, a localized version of Delaunay refinement was proposed for generating meshes for smooth surfaces and volumes bounded by them. The method embodies a divide-and-conquer paradigm in that it maintains the growing set of sample points with an octree and produces a local mesh within each individual node, and stitches these local meshes seamlessly. The proofs of termination and global consistency for localized methods exploit recently developed sampling theory for smooth surfaces. Unfortunately, these proofs break down for a larger class called piecewise smooth complexes (PSCs) that allow smooth surface patches that are joined along ridges and corners. In this work, we adapt a recently developed sampling and meshing algorithm for PSCs into the localization framework. This requires revisiting the original algorithm, and more importantly re-establishing the correctness proofs to accommodate the localization framework. Our implementation of the algorithm exhibits that it can indeed generate large meshes with significantly less time and memory than the original algorithm without localization. In fact, it beats a state-of-the-art meshing tool of CGAL for generating large meshes.

          
 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]

The detection and reconstruction of feature curves in surfaces from a point cloud data is a challenging problem because most of the known theories for smooth surfaces break down at these places. The features such as boundaries, sharp ridges and corners, and curves where multiple surface patches intersect creating non-manifold points are often considered important geometries for further processing. As a result, they need to be preserved in a reconstruction of the sampled surface from its point sample. The problem becomes harder in presence of noise. We propose a robust Voronoi-based pipeline that engages several sub steps consisting of approaches proposed originally for smooth case. We modify or enhance them to handle features in singular surfaces. The experimental results provide the evidence that the method is effective.

Note: This paper extracts features differently than our ``Feature-Preserving reconstruction of singular surfaces" paper which introduced the WeightCocone to reconstruct with feature curves
          
 Weighted graph Laplace operator under topological noise
T. K. Dey, P. Ranjan, and Y. Wang. (SODA 2013), ACM-SIAM Symposium on Discrete Algorithms (2013).


Recently, various applications have motivated the study of spectral structures (eigenvalues and eigenfunctions) of the so-called Laplace-Beltrami operator of a manifold and their discrete versions. A popular choice for the discrete version is the so-called Gaussian weighted graph Laplacian which can be applied to point cloud data that samples a manifold. Naturally, the question of stability of the spectrum of this discrete Laplacian under the perturbation of the sampled manifold becomes important for its practical usage. Previous results showed that the spectra of both the manifold Laplacian and discrete Laplacian are stable when the perturbation is ``nice'' in the sense that it is restricted to a diffeomorphism with minor area distortion. However, this forbids, for example, small topological changes.

We study the stability of the spectrum of the weighted graph Laplacian under more general perturbations. In particular, we allow arbitrary, including topological, changes to the hidden manifold as long as they are localized in the ambient space and the area distortion is small. Manifold Laplacians may change dramatically in this case. Nevertheless, we show that the weighted graph Laplacians computed from two sets of points, uniformly randomly sampled from a manifold and a perturbed version of it, have similar spectra. The distance between the two spectra can be bounded in terms of the size of the perturbation and some intrinsic properties of the original manifold.

          
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]

Bubbles and foams are important features of liquid surface phenomena, but they are difficult to animate due to their thin films and complex interactions in the real world. In particular, small bubbles (having diameter <1cm) in a dense foam are highly affected by surface tension, so their shapes are much less deformable compared with larger bubbles. Under this small bubble assumption, we propose a more accurate and efficient particle-based algorithm to simulate bubble dynamics and interactions. The key component of this algorithm is an approximation of foam geometry, by treating bubble particles as the sites of a weighted Voronoi diagram. The connectivity information provided by the Voronoi diagram allows us to accurately model various interaction effects among bubbles. Using Voronoi cells and weights, we can also explicitly address the volume loss issue in foam simulation, which is a common problem in previous approaches. Under this framework, we present a set of bubble interaction forces to handle miscellaneous foam behaviors, including foam structure under Plateau's laws, clusters formed by liquid surface bubbles, bubble-liquid and bubble-solid coupling, bursting and coalescing. Our experiment shows that this method can be straightforwardly incorporated into existing liquid simulators, and it can efficiently generate realistic foam animations, some of which have never been produced in graphics before.
         
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]

Reconstructing a surface mesh from a set of discrete point samples is a fundamental problem in geometric modeling. It becomes challenging in presence of `singularities' such as boundaries, sharp features, and non-manifolds. A few of the current research in reconstruction have addressed handling some of these singularities, but a unified approach to handle them all is missing. In this paper we allow the presence of various singularities by requiring that the sampled object is a collection of smooth surface patches with boundaries that can meet orintersect.

Our algorithm first identifies and reconstructs the features where singularities occur. Next, it reconstructs the surface patches containing these feature curves. The identification and reconstruction of feature curves are achieved by a novel combination of the Gaussian weighted graph Laplacian and the Reeb graphs. The global reconstruction is achieved by a method akin to the well known Cocone reconstruction, but with weighted Delaunay triangulation that allows protecting the feature samples with balls. We provide various experimental results to demonstrate the effectiveness of our feature-preserving singular surface reconstruction algorithm.
           
 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.

We study circle valued maps and consider the persistence  of the homology of their fibers. The outcome is a finite collection of computable invariants  which answer the basic questions on persistence and in addition encode the topology of the source space and its relevant subspaces. Unlike persistence of real valued maps, circle valued maps enjoy a different class of invariants celled Jordan cells in addition to bar codes. We establish a relation between the homology of the source space and of its relevant subspaces with these invariants and provide a new algorithm to compute these invariants from an input matrix that encodes a circle valued map on an input simplicial complex.


Also see how it all started: arXiv:1012.3763, 2010.
         
 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]

Recent advances in mesh deformation have been dominated by two techniques: one uses an interactive structure like a cage which transfers the user intended moves to the mesh, the other lest the user to impart the moves to the mesh directly. The former one lets the user deform the model in real-time and also preserves the shape with sophisticated techniques like Green Coordinates. The direct techniques on the other hand free the user from the burden of creating an appropriate cage though they take more computing time to solve larger non-linear optimizations. It would be ideal to develop a cage-free technique that provides real-time defoirmation while respecting the local geometry. Using a simple eigen-framework we devise such a technique. Our framework creates an implicit skeleton automatically. The user only specifies the motion in a simple and intuitive manner, and our algorithm computes a deformation whose quality is similar to that of the cage-based scheme with Green Coordinates.

           
 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

Let K be a simplicial complex and g the dimension of its p-th homology group H_p(K) defined with Z_2 coefficients. We show that we can compute a basis H of H_p(K) and annotate each p-simplex of K with a binary vector of length g with the following property: the annotations, summed over all p-simplices in any p-cycle z, provide the coordinate vector of the homology class [z] in the basis H. The basis and the annotations for all simplices can be computed in O(n^{\omega}) time, where n is the size of K and \omega<2.376 is a quantity so that two nxn  matrices can be multiplied in O(n^{\omega}) time. The pre-computation of annotations permits answering queries about the independence or the triviality of p-cycles efficiently. Using annotations of edges in 2-complexes, we derive better algorithms for computing optimal basis and optimal homologous cycles in 1-dimensional homology. Specifically, for computing an optimal basis of H_1(K),we improve the time complexity known for the problem from O(n^4) to O(n^{\omega}+n^2g^{\omega-1}). Here n denotes the size of the 2-skeleton of K and g the rank of H_1(K). Computing an optimal cycle homologous to a given 1-cycle is NP-hard even for surfaces and an algorithm taking 2^{O(g)}n\log n time is known for surfaces. We extend this algorithm to work with arbitrary 2-complexes in O(n^{\omega})+2^{O(g)}n^2\log n time using annotations.

Also see this technical report for a more practical algorithm.
         
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]

Delaunay refinement, recognized as a versatile tool for meshing a variety of geometries, has the deficiency that it does not scale well with increasing mesh size. The bottleneck can be traced down to the memory usage of 3D Delaunay triangulations. Recently an approach has been suggested to tackle this problem for the specific case of smooth surfaces by subdividing the sample set in an octree and then refining each subset individually while ensuring {\em termination} and {\em consistency}. We extend this to localized refinement of volumes, which brings about some new challenges. We show how these challenges can be met with simple steps while retaining provable guarantees, and that our algorithm scales many folds better than a state-of-the-art meshing tool provided by CGAL.


Also, see the paper below on localized Delaunay refinement for surfaces.
         
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]
Given a continuous function f: X-> R on a topological space X, its {\em level set} f^{-1}(a) changes continuously as the real value a changes. Consequently, the connected components in the level sets appear, disappear, split and merge.  The Reeb graph of f summarizes this information into a graph structure. Previous work on Reeb graph mainly focused on its efficient computation. In this paper, we initiate the study of two important aspects of the Reeb graph which can facilitate its  broader applications in shape and data analysis. The first one is the approximation of the Reeb graph of a function on a smooth compact manifold M without boundary. The approximation is computed from a set of points P sampled from M. By leveraging a relation between the Reeb graph and the so-called {\em vertical homology group}, as well as between cycles in M and in a Rips complex  constructed from P, we compute the H_1-homology of the Reeb graph from P. It takes O(n \log n) expected time, where n is the size of the 2-skeleton of the Rips complex. As a by-product, when M is an orientable 2-manifold, we also obtain an efficient near-linear time (expected) algorithm to compute the rank of H_1(M) from point data. The best known previous algorithm for this problem takes O(n^3) time for point data. The second aspect concerns the definition and computation of the \emph{persistent Reeb graph homology} for a sequence of Reeb graphs defined on a filtered space. For a piecewise-linear function defined on a filtration of a simplicial complex K, our algorithm computes all persistent H_1-homology for the Reeb graphs in O(n n_e^3) time, where n is the size of the 2-skeleton and n_e is the number of edges in K.

       
Localized Delaunay refinement for sampling and meshing.  [Talk slides][Web-page][Software]
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).
[Extended version]

The technique of Delaunay refinement has been recognized as a versatile tool to generate Delaunay meshes of a variety of geometries. Despite its usefulness, it suffers from one lacuna that limits its application. It does not scale well with the mesh size. As the sample point set grows, the Delaunay triangulation starts stressing the available memory space which ultimately stalls any effective progress. A natural solution to the problem is to maintain the point set in clusters and run the refinement on each individual cluster. However, this needs a careful point insertion strategy and a balanced coordination among the neighboring clusters to ensure consistency across individual meshes. We design an octtree based localized Delaunay refinement method for meshing surfaces in three dimensions which meets these goals. We prove that the algorithm terminates and provide guarantees about structural properties of the output mesh. Experimental results show that the method can avoid memory thrashing while computing large meshes and thus scales much better than the standard Delaunay refinement method.
     
 Persistent heat signature for pose-oblivious matching of incomplete models.  [Talk slides]
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).

Although understanding of shape features in the context of shape matching and retrieval has made considerable progress in recent years, the case for partial and incomplete models in presence of pose variations still begs a robust and efficient solution. A signature that encodes features at multi-scales in a pose invariant manner is more appropriate for this case. The Heat Kernel Signature function from spectral theory exhibits this multi-scale property. We show how this concept can be merged with the persistent homology to design a novel efficient pose-oblivious matching algorithm for all models, be they partial, incomplete, or complete. We make the algorithm scalable so that it can handle large data sets. Several test results show the robustness of our approach.
       
 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.

The persistent homology provides a mathematical tool to describe ``features" in a principle manner. The persistence algorithm proposed by Edelsbrunner et al. [5] can compute not only the persistent homology for a filtered simplicial complex, but also representative generating cycles for persistent homology groups. However, if there are dynamic changes either in the filtration or in the underlying simplicial complex, the representative generating cycle can change wildly.

In this paper, we consider the problem of tracking generating cycles with temporal coherence. Specifically, our goal is to track a chosen essential generating cycle so that the changes in it are ``local". This requires reordering simplices in the filtration, To handle reordering operations. we build upon the matrix framework proposed by Cohen-Steiner et al.[3] to swap two consecutive simplices, so that we can process a reordering directly. We present an application showing how our algorithm can track an essential cycle in a complex constructed out of a point cloud data.
   
 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]

Given a simplicial complex with weights on its simplices, and a nontrivial cycle on it, we are interested in finding the cycle with minimal weight which is homologous to the given one. Assuming that the homology is defined with integer (Z) coefficients, we show the following (Theorem 5.2):

For a finite simplicial complex K of dimension greater than p, the boundary matrix [d_(p+1)] is totally unimodular if and only if H_p(L,L_0) is torsion-free for all pure subcomplexes L_0, L in K of dimension p and p+1 respectively where L_0\subset L.

Because of the total unimodularity of the boundary matrix, we can solve the optimization problem, which is inherently an integer programming problem, as a linear program and obtain integer solution. Thus the problem of finding optimal cycles in a given homology class can be solved in polynomial time. This result is surprising in the backdrop of a recent result which says that the problem is NP-hard under Z_2 coefficients which, being a field, is in general easier to deal with. One consequence of our result, among others, is that one can compute in polynomial time an optimal 2-cycle in a given homology class for any finite simplicial complex embedded in R^3. Our optimization approach can also be used for various related problems, such as finding an optimal chain homologous to a given one when they are not cycles.
 
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]

Inference of topological and geometric attributes of a hidden manifold from its point data is a fundamental problem arising in many scientific studies and engineering applications. In this paper we present an algorithm to compute a set of cycles from a point data that presumably sample a smooth manifold M\subset R^d. These cycles approximate a shortest basis of the one dimensional homology group H_1(M) over coefficients in finite field Z_2.  Previous results addressed the issue of computing the rank of the homology groups from point data, but there is no result on approximating the shortest basis of a manifold from its point sample. In arriving our result, we also present a polynomial time algorithm for computing a shortest basis of H_1(K) for any finite simplicial complex K whose edges have non-negative weights.
 
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.

Spectral methods have been widely used in a broad range of applications fields. One important object involved in such methods is the Laplace-Beltrami operator of a manifold. Indeed, a variety of work in graphics and geometric optimization uses the eigen-structures (i.e., the eigenvalues and eigenfunctions) of the Laplace operator. Applications include mesh smoothing, compression, editing, shape segmentation, matching, parameterization, and so on. While the Laplace operator is defined (mathematically) for a smooth domain, these applications often approximate a smooth manifold by a discrete mesh. The spectral structure of the manifold Laplcian is estimated from some discrete Laplace operator constructed from this mesh.

In this paper, we study the important question of how well the specturm computed from the discrete mesh approximates the true spectrum of the manifold Lplacian. We exploit a recent result on mesh Laplacian and provide the first convergence result to relate the spectrum constructed from a general mesh (approximating an m-manifold embedded in R^d) with the true spectrum. We also study how stable these eigenvalues and their discrete approximations are when the underlying manifold is perturbed, and provide explicit bounds for the Laplacian spectra of two ``close" manifolds, as well as a convergence result for their discrete approximations. Finally, we present various experimental results to demonstrate that these discrete spectra are both accurate and robust in practice.
 
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.


As a direct consequence of software quirks, designer errors, and representation flaws, often three-dimensional shapes are stored in formats that introduce inconsistencies such as small gaps and overlaps between surface patches. We present a new algorithm that simultaneously repairs imperfect geometry and topology while generating Delaunay meshes of these shapes. At the core of this approach is a meshing algorithm for input shapes that are piecewise smooth complexes (PSCs), a collection of smooth surface patches meeting at curves non-smoothly or in  non-manifold configuarations. Guided by a user tolerance parameter, we automatically merge nearby components while building a Delaunay mesh that has many of these errors fixed. Experimental evidence is provided to show the results of our algorithm on common computer-aided design (CAD) formats. Our algorithm may  also be used to simplify shapes by removing small features which would require an excessive number of elements to preserve them in the output mesh.

Note: One of the main ingredients of this paper is our PSC meshing paper.
      
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]

We present an algorithm for the reconstruction of a surface with boundaries (including a non-orientable one) in three dimensions from a sufficiently dense sample. It is guaranteed that the output is isotopic to the unknown sampled surface. No previously known algorithm guarantees isotopic or homeomorphic reconstruction of surfaces with boundaries. Our algorihtm is surprisingly simple. It `peels' slivers greedily from an alpha-complex of a sample of the surface. No other post-processing is necessary. We provide several experimental results from an implementation of our basic algorithm and also a modified version of it.
     
Cut Locus and Topology from Surface Point Data.
T. K. Dey, K. Li. Proc. 25th Ann. Sympos. Comput. Geom.(SOCG09), 2009, 125--134.


A cut locus of a point in a compact Riemannian manifold M is defined as the set of points where minimizing geodesics issued from p stop being minimizing. It is known that a cut locus contains most of the topological information of M. Our goal is to utilize this property of cut loci to decipher the topology of M from a point sample. Recently it has been shown that Rips complexes can be built from  a point sample P of M systematically to compute the Betti numbers, the rank of the homology groups of M. Rips complexes can be computed easily and therefore are favored over others such as restricted Delaunay, alpha, Cech, and witness complex. However, the sizes of the Rips complexes tend to be large. Since the dimension of a cut locus is lower than that of the manifold M, a subsample of P approximating the cut locus is usually much smaller in size and hence admits a relatively smaller Rips complex.

In this paper we explore the above approach for point data sampled from surfaces embedded in any high dimensional Euclidean space. We present an algorithm that computes a subsample P' of a sample P of a 2-manifold where P' approximates a cut locus. Empirical results show that the first Betti number of M can be computed from Rips complexes built on these subsamples. The sizes of these Rips complexes are much smaller than the one built on the original sample of M.

Our first attempt on a related topic was the following paper:

Topology from Data via Geodesic Complexes. T. K. Dey and K. Li. Tech Report OSU-CISRC-3/09-TR05.
   
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]

Recently a Delaunay refinement algorithm has been proposed that can mesh piecewise smooth complexes which include polyhedra, smooth and piecewise smooth surfaces, and non-manifolds. However, this algorihtm employs domain dependent numerical predicates, some of which could be computationally expensive and hard to implement. In this paper we develop a refinement strategy that eliminates these complicated domain dependent predicates. As a result we obtain a meshing algorithm that is practical and implementation-friendly.
 
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]

Loops in surfaces associated with topological features such as handles and tunnels are important entities in many applications including surface parameterization, feature identification, and topological simplification. Recently, a persistent homology based algorithm has been proposed to compute them. The algorithm has several advantages including its simplicity, combinatorial nature and independence from computing other extra structures. In this paper, we propose changes to this loop computation algorithm based on some novel observations. These changes reduce the computation time of the algorithm dramatically. In particular, our experimental results show that the suggested changes achieve considerable speed up for large data sets without sacrificing loop qualities.

Note: This is a follow-up paper of our SIGGRAPH08 paper below.
 
Computing Geometry-aware Handle and Tunnel Loops in 3D Models.
T. K. Dey, K. Li, J. Sun, and D. Cohen-Steiner. SIGGRAPH 2008, 45:1--45:9.

[Video][Software][Talk-slide][Web-page]

Many applications such as topology repair, model editing, surface parameterization, and feature recognition benefit from computing loops on surfaces that wrap around their `handles' and `tunnels'. Computing such loops while optimizing their geometric lengths is difficult. On the other hand, computing such loops without considering geometry is easy but may not be very useful. In this paper we strike a balance by computing topologically correct loops that are also geometrically relevant. Our algorithm is a novel application of the concepts from topological persistence introduced recently in computational topology. The usability of the computed loops is demonstrated with some examples in feature identification and topology simplification.

Note: See the paper below  On computing handle and tunnel loops  for our first attempt on this problem.

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.


The flow complex is a geometric structure, similar to the Delaunay tessellation, to organize a set of (weighted) points in R^k. Flow shapes are topological spaces correspoding to substructures of the flow complex. The flow complex and flow shapes have found applications in surface reconstruction, shape matching, and molecular modeling. In this article we give an algorithm for computing the flow complex of weighted points in any dimension. The algorithm reflects the recursive structure of the flow complex. On the basis of the algorithm we establish a topological similarity between flow shapes and the nerve of a corresponding ball set, namely homotopy equivalence.

This paper grew out of:
Alpha-Shapes and Flow Shapes are Homotopy Equivalent. T. K. Dey, J. Giesen and M. John. Proceedings of the 35th Annual ACM Symposium on Theory of Computing (STOC 2003) 493-502
 
Normal variation with adaptive feature size (2007)

The proof of the normal variation lemma (Lemma 2) in  Amenta-Bern paper ``Surface reconstruction by Voronoi filtering", DCG, 1999, pg. 481-504, is not correct (which also appears in my book on reconstruction). In this short note we fix the problem and improve the bound on the normal variation. This should improve various bounds derived afterwards using the normal variation result.

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

We present a method to maintain a mesh approximating a deforming surface, which is specified by a dense set of sample points. We identify a reasonable motion model for which a provably good surface mesh can be maintained. Our algorithm determines the appropriate times at which the mesh is updated to maintain a good approximation. The updates use simple primitives, and no costly computation such as line-surface intersection is necessary. Point insertions and deletions are allowed at the updates. Each update takes time linear in the size of the current sample set plus the new sample points inserted. We also construct examples for which, under the same model, no other algorithm makes asymptotically fewer changes to the mesh than our algorithm.

This paper is based on the following flip paper available as a preprint from computational geoemtry arxiv.

 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. The abstract was:

Delaunay flip is an elegant, simple tool to convert a triangulation of a point set to its Delaunay triangulation. The technique has been researched extensively for full dimensional triangulations of point sets. However, an important case of triangulations which are not full dimensional is surface triangulations in three dimensions. In this paper we address the question of converting a surface triangulation to a subcomplex of the Delaunay triangulation with edge flips. We show that the surface triangulations which closely approximate a smooth surface with uniform density can be transformed to a Delaunay triangulation with a simple edge flip algorithm. The condition on uniformity becomes less stringent with increasing density of the triangulation. If the condition is dropped completely, the flip algorithm still terminates although the output surface triangulation becomes ``almost Delaunay" instead of exactly Delaunay.


 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]

Recently a Delaunay refinement algorithm has been proposed that can mesh domains as general as piecewise smooth complexes [CDR07]. In this paper we introduce a novel modification of the algorithm  to make it implementable in practice. In particular, we replace four tests of the original algorithm with only a single test that is easy to implement. The algorithm has the following guarantees. The output mesh restricted to each manifold element in the complex is a manifold with proper incidence relations. More importantly, with increasing level of refinement which can be controlled by an input parameter, the output mesh becomes homeomorphic to the input while preserving all input features. Implementation results on a disparate array of input domains are presented to corroborate our claims.

For the theory see the following paper:

Theory of a practical Delaunay meshing algorithm for a large class of domains. S.-W. Cheng, T. K. Dey and J. Levine. Algorithms, Architecture and Information Systems Security, B. Bhattacharya, S. Sur-Kolay, S. Nandy and A. Bagchi (eds.), World Scientific Review Volume 3, 2008, 17--41.

 
  
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

Many applications seek to identify features like `handles' and `tunnels' in a shape bordered by a surface embedded in three dimensions. To this end we define handle and tunnel loops on surfaces which can help identifying these features. We show that a closed surface of genus g always has g handle and g tunnel loops induced by the embedding. For a class of shapes that retract to graphs, we characterize these loops by a linking condition with these graphs. These characterizations lead to algorithms for detection and generation of these loops. We provide an impementation with applications to feature detection and topology simplification to show the effectiveness of the method.



 
 
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.

Scalar functions defined on a topological space T are at the core of many applications such as shape matching, visualization, and physical simulations. Topological persistence is an approach to characterizing these functions. It measures how long topological structures in the level sets {x in T : f(x) <= c} persist as c changes. Recently it was shown that the critical values defining a topological structure with relatively large persistence remain almost unaffected by small perturbations. This result suggests that topological persistence is a good measure for matching and comparing scalar functions. We extend these results to critical points in the domain by redefining persistence and critical points and replacing sub-level sets {x in T : f(x) <= c} with interval sets {x in T : a<=f(x)< b}. With these modifications we establish a stability result for critical points. This result is strengthened for maxima that can be used for matching two scalar functions. 
 

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

DelIso software

We present an isosurface meshing algorithm DelIso, based on the Delaunay refinement paradigm. This paradigm has been successfully applied to mesh a variety of domains with guarantees for topology, geometry, mesh gradedness, and triangle shape. A restricted Delaunay triangulation, dual of the intersection between the surface and the three dimensional Voronoi diagram, is often the main ingredient in Delaunay refinement. Computing and storing three dimensional Voronoi/Delaunay diagrams become bottlenecks for Delaunay refinement techniques since isosurface computations generally have large input datasets and output meshes. A highlight of our algorithm is that we find a simple way to recover the restricted Delaunay triangulation of the surface without computing the full 3D structure. We employ techniques for efficient ray tracing of isosurfaces to generate surface sample points, and demonstrate the effectiveness of our implementation on a variety of volume datasets.
 
 
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

We present a Delaunay refinement algorithm for meshing a piecewise smooth complex in three dimensions with correct topology. The small angles between the tangents of two meeting manifold patches pose difficulty. We protect these regions with weighted points. The weights are chosen to mimic the local feature size and to satisfy a Lipschitz-like property. A Delaunay refinement using the weighted Voronoi diagram is shown to terminate with the recovery of the topology of the input. To this end, we present new concepts and results including a new definition of local feature size and a proof for a generalized topological ball property.

 
 
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

Many applications in geometric modeling, computer graphics, visualization, and computer vision benefit from a reduced representation called curve-skeletons of a shape. These are curves possibly with branches which compactly represent the shape geometry and topology. The lack of a proper mathematical definition has been a bottleneck in developing and applying the curve-skeletons. A set of desirable properties of these skeletons has been identified and the existing algorithms try to satisfy these properties mainly through a procedural definition. We define a function called medial geodesic on the medial axis which leads to a mathematical definition and an approximation algorithm for curve-skeletons. Empirical study shows that the algorithm is robust against noise, operates well with a single user parameter, and produces curve-skeletons with the desirable properties. Moreover, the curve-skeletons can be associated with additional attributes that follow naturally from the definition. These attributes capture shape eccentricity, a local measure of how far a shape is away from a tubular one.
 

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.

We present an algorithm to identify the flat and tubular regions of a three dimensional shape from its point sample. We consider the distance function to the input point cloud and the Morse structure induced by it on R^3. Specifically we focus on the index 1 and index 2 saddle points and their unstable manifolds. The unstable manifolds of index 2 saddles are one dimensional whereas those of index 1 saddles are two dimensional. Mapping these unstable manifolds back onto the surface, we get the tubular and flat regions. The computations are carried out on the Voronoi diagram of the input points by approximating the unstable manifolds with Voronoi faces. We demonstrate the performance of our algorithm on several point sampled objects.
 

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

NormFet software


We consider the problem of approximating normal and feature sizes approximations of a surface from point cloud data that may be noisy. These problems are central to many applications dealing with point cloud data. In the noise-free case, the normals and feature sizes can be approximated by the centers of a set of unique large Delaunay balls called polar balls. In presence of noise, polar balls do not necessarily remain large and hence their centers may not be good for normal and feature approximations. Earlier works suggest that some large Delaunay balls can play the role of polar balls. However, these results were short in explaining how the big Delaunay balls should be chosen for reliable approximations and how the approximation error depends on various factors. We provide new analyses that fill these gaps. In particular, they lead to new algorithms for practical and reliable normal and feature approximations.
 

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

We study the problem of triangulating a smooth closed implicit surface S endowed with a 2D metric tensor that varies over S. This is commonly known as the anisotropic surface meshing problem. We extend the 2D metric tensor naturally to 3D and employ the 3D anisotropic Voronoi diagram of a set P of samples on S to triangulate S. We prove that a restricted dual, Mesh P,  is a valid triangulation homeomorphic to S under appropriate conditions. We also develop an algorithm for constructing P and Mesh P.  In addition to being homeomorphic to S, each triangle in Mesh P is well-shaped when measured using the 3D metric tensors of its vertices. Users can set upper bounds on the anisotropic edge lengths and the angles between the surface normals at vertices and the normals of incident triangles (measured both isotropically and anisotropically).
 


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.
Technical Report OSU-CISRC-4-05-TR26, April, 2005.


AMLS Software

Recent work have shown that moving least squares (MLS) surfaces can be used effectively to reconstruct surfaces from possibly noisy point cloud data. Several variants of MLS surfaces have been suggested, some of which have been analyzed theoretically for guarantees. These analyses, so far, have assumed uniform sampling density. We propose a new variant of the MLS surface that, for the first time, incorporates local feature sizes in its formulation, and we analyze it for reconstruction guarantees using a non-uniform sampling density. The proposed variant of the MLS surface has several computational advantages over existing MLS methods.

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


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.


Many applications that process a point cloud data benefit from a reliable normal estimation step. Given a point cloud presumably sampled from an unknown surface, the problem is to estimate the normals of the surface at the data points. Two approaches, one based on numerical optimizations and another based on Voronoi diagrams are known for the problem. Variations of numerical approaches work well even when point clouds are contaminated with noise. Recently a variation of the Voronoi based method is proposed for noisy point clouds. The centrality of the normal estimation step in point cloud processing begs a thorough study of the two approaches so that one knows which approach is appropriate for what circumstances. This paper presents such results.
  

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

Polygonal meshes are used to model smooth surfaces in many applications. Often these meshes need to be remeshed for improving the quality, density or gradedness. We apply the Delaunay refinement paradigm to design a provable algorithm for isotropic remeshing of a polygonal mesh that approximates a smooth surface. The proofs provide new insights and our experimental results corroborate the theory.
  
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.


Recently, a provable Delaunay meshing algorithm called QMesh has been proposed for polyhedra that may have acute input angles. The algorithm guarantees bounded circumradius to shortest edge length ratio for all tetrahedra except the ones near small input angles. This guarantee eliminates or limits the occurrences of all types of poorly shaped tetrahedra except slivers. A separate technique called weight pumping is known for sliver elimination. But, allowable input for the technique so far have been periodic point sets and piecewise linear complex with non-acute input angles. In this paper, we incorporate the weight pumping method into QMesh thereby ensuring that all tetrahedra except the ones near small input angles have bounded aspect ratio. Theoretically, the algorithm has an abysmally small angle guarantee inherited from the weight pumping method. Nevertheless, our experiments show that it produces better angles in practice.



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.

The distance function to surfaces in three dimensions plays a key role in many geometric modeling applications such as medial axis approximations, surface reconstructions, offset computations, feature extractions and others. In most of these cases, the distance function to the surface is approximated by a discrete distance function where the distances are measured from a discrete sample of the surface. The critical points of the distance function determines the topology of the geometric structures in question. Howvere, no theoretical result exists linking the sampling and the critical point structures of the distance functions. We provide this link by showing that the critical points of the discrete distance function either lie very close to the surface or near the medial axis both quantified with the sampling density. One implication of this result is that known Morse theory based surface reconstruction algorithms do indeed approximate the surface geometrically.


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 AbstractSee also [Talk slides]

We present an algorithm to "reconstruct" a smooth k-dimensional manifold M embedded in an Euclidean space R^d from a "sufficiently dense" point sample from the manifold. The algorithm outputs a simplicial manifold that is homeomorphic and geometrically close to M. The running time is O(nlogn) where n is the number of points in the sample (the multiplicative constant depends exponentially on the dimension though).
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).

Recent results establish that a subset of the Voronoi diagram of a point set that is sampled from a smooth boundary of a shape approximates the medial axis. The corresponding question for the dual Delaunay triangulation is not addressed in the literature. We show that, for two dimensional shapes, the Delaunay triangulation approximates a specific structure which we call anchor hulls. As an application we demonstrate that our approximating result is useful for the problem of shape matching.
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

We present an algorithm to compute a Delaunay mesh conforming to a polyhedron possibly with small input angles. The radius-edge ratio of most output tetrahedra are bounded by a constant, except possibly those that are provably close to small angles. Further, the mesh is graded, that is, edge lengths are at least a constant fraction of the local feature sizes at the edge endpoints. Unlike a previous algorithm, this algorithm is simple to implement as it avoids computing local feature sizes and protective zones explicitly. Our experimental results confirm our claims and show that few skinny tetrahedra remain.
Sampling and meshing a surface with guaranteed topology and geometry
S.-W. Cheng, T. K. Dey, E. Ramos and T. Ray.Proc. 20th Sympos. Comput. Geom. (SOCG 2004), 280--289 .

Extended version,  in SIAM Journal Computing, Vol. 37 (2007), 1199--1227.

This paper presents an algorithm for sampling and triangulating a smooth surface in R3 where the triangulation is homeomorphic to the surface. The only assumption we make is that the input surface representation is amenable to certain types of computations, namely computations of the intersection points of a line with the surface, computations of the critical points of some height functions defined on the surface and its restriction to a plane, and computations of some silhouette points. The algorithm ensures bounded aspect ratio, size optimality, and smoothness of the output triangulation. Unlike previous algorithms, this algorithm does not need to compute the local feature size for generating the sample points which was a major bottleneck. Experiments show the usefulness of the algorithm in remeshing and meshing CAD surfaces that are piecewise smooth.
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

We present an algorithm for surface reconstruction in presence of noise. We show that, under a reasonable noise model, the algorithm has theoretical guarantees. Actual performance of the algorithm is illustrated by our experimental results.

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

The medial axis of a surface in 3D is the closure of all points that have two or more closest points on the surface. It is an essential geometric structure in a number of applications involving 3D geometric shapes. Since exact computation of the medial axis is difficult in general, efforts continue to improve their approximations. Voronoi diagrams turn out to be useful for this approximation. Although it is known that Voronoi vertices for a sample of points from a curve in 2D approximate its medial axis, similar result does not hold in 3D. Recently, it has been discovered that only a subset of Voronoi vertices converge to the medial axis as sample density approaches infinity. However, most applications need a non-discrete approximation as opposed to a discrete one. To date no known algorithm can compute this approximation straight from the Voronoi diagram with a guarantee of convergence.We present such an algorithm and its convergence analysis in this paper. One salient feature of the algorithm is that it is scale and density independent. Experimental results corroborate our theoretical claims.

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

Given a triangulated closed surface, the problem of constructing a hierarchy of surface models of decreasing level of detail has attracted much attention in computer graphics. A hierarchy provides a view-dependent refinement and facilitates the computation of parameterization. For a triangulated closed surface of n vertices and genus g, we prove that there is a constant c>0 such that if n > c g, a greedy strategy can identify \Theta(n) topology-preserving edge contractions that do not interfere with each other. Further, each of them affects only a constant number of triangles. Repeatedly identifying and contracting such edges produces a topology-preserving hierarchy of O(n+g^2) size and O(logn +g) depth. Although several implementations exist for constructing hierarchies, our work is the first to show that a greedy algorithm can efficiently compute a hierarchy of provably small size and low depth. When no contractible edge exists, the triangulation is irreducible. Nakamoto and Ota showed that any irreducible triangulation of an orientable 2-manifold has at most max{342g-72, 4} vertices. Uisng our proof techniques we obtain a new bound of mx{240g,4}.
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

Geometric shapes are identified with their features. For computational purposes a concrete mathematical definition of features is required. In this paper we use a topological approach, namely dynamical systems, to define features of shapes. To exploit this definition algorithmically we assume that a point sample of the shape is given as input from which features of the shape have to be approximated. We translate our definition of features to the discrete domain while mimicking the set-up developed for the continuous shapes. The outcome of this approach is a clean mathematical definition of features that are efficiently computable with combinatorial algorithms. Experimental results show that our algorithms segment shapes in two and three dimensions into so-called features quite effectively. Further, we develop a shape matching algorithm that takes advantage of our robust feature segmentation step. Performance of this algorithm is exhibited with experimental results.

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

Delaunay meshes with bounded circumradius to shorten edge length ratio have been propsed in the past for quality meshing. The only poor quality tetrahedra called slivers that can occur in such a mesh can be eliminated by the sliver exudation method. This method has been shown to work for periodic point sets, but not with boundaries. Recently a randomized point-placement strategy has been proposed to remove slivers while conforming to a given boundary. In this paper we present a deterministic algorithm for generating a weighted Delaunay mesh which respects the input boundary and has no poor quality tetrahedron including slivers. As in previous work, we assume that no input angle is acute. This success is achieved by combining the weight pumping method for sliver exudation and the Delaunay refinement method for boundary conformation.
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).

There are many scientific and engineering applications where an automatic detection of shape dimension from sample data is necessary. Topological dimensions of shapes constitute an important global feature of them. We present a Voronoi based dimension detection algorithm that assigns a dimension to a sample point which is the topological dimension of the manifold it belongs to. Based on this dimension detection, we also present an algorithm to approximate shapes of arbitrary dimension from their samples. Our empirical results with data sets in three dimensions support our theory.
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).

The problem of computing a piecewise linear approximation to a surface from a set of sample points is improtant in solid modeling, computer graphics and computer vision. A recent algorithm using the Voronoi diagram of the sample points gave a guarantee on the distance of the output surface from the original sampled surface assuming that the sample was sufficiently dense. We give a similar algorithm, simplifying the computation and the proof of the geometric guarantee. In addition, we guarantee that our output surface is homeomorphic to the original surface; to our knowledge this is the first such topological guarantee for this problem.

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

This paper describes an algorithm for maintaining an approximating triangulation of a deforming surface in R 3 . The surface is the envelope of an infinite family of spheres defined and controlled by a finite collection of weighted points. The triangulation adapts dynamically to changing shape, curvature, and topology of the surface.
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).

A sliver is a tetrahedron whose four vertices lie close to a plane and whose orthogonal projection to that plane is a convex quadrilateral with no short edge. Slivers are notoriously common in 3-dimensional Delaunay triangulations even for well-spaced point sets. We show that if the Delaunay triangulation has the ratio property then there is an assignment of weights so the weighted Delaunay triangulation contains no slivers. We also give an algorithm to compute such a weight assignment.
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

We present an algorithm that provably reconstructs a curve in the framework introduced by Amenta, Bern and Eppstein. The highlights of the algorithm are: (i) it is simple, (ii) it requires a sampling density better than previously known, (iii) it can be adapted for curve reconstruction in higher dimensions straightforwardly.
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

We study edge contractions in simplicial complexes and local conditions under which they preserve the topological type. The conditions are based on a generalized notion of boundary, which lends itself to defining a nested hierarchy of triangulable spaces measuring the distance to being a manifold.
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

We describe an optimal algorithm to decide if one closed curve on a triangulated 2-manifold can be continuously transformed to another, i.e., if they are homotopic. Suppose C_1 and C_2 are two closed curves on a surface M of genus g. Further, suppose T is a triangulation of M of size n such that C_1 and C_2 are represented as edge-vertex sequences of lengths k_1 and k_2 in T, respectively. Then, our algorithm decides if C_1 and C_2 are homotopic in O(n+k_1+k_2) time and space, provided g \not = 2 if M is orientable, and g \not 3, 4 if M is non-orientable. This as well implies an optimal algorithm to decide if a closed curve on a surface can be continuously contracted to a point. Except for the three low genus cases, our algorithm completes an investigation into the computational complexity of two classical problems for surfaces posed by the mathematician Max Dehn at the beginning of this century. The novelty of our approach is in the application of methods from modern combinatorial group theory.

Reprint available upon request
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).

We prove an O(nk1/3) upper bound for planar k-sets. This is the first considerable improvement on this bound after its early solutions approximately twenty seven years ago. Our proof technique also applies to improve the current bounds on the combinatorial complexities of k-levels in arrangements of line segments, k convex polygons in the union of n lines, parametric minimum spanning trees and parametric matroids in general.
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

A geometric hypergraph H is a collection of i-dimensional simplices, called hyperedges or, simply, edges, induced by some (i + 1)-tuples of a vertex set V in general position in d-space. The topological structure of geometric graphs, i.e., the case d = 2; i = 1, has been studied extensively, and it proved to be instrumental for the solution of a wide range of problems in combinatorial and computational geometry. They include the k-set problem, proximity questions, bounding the number of incidences between points and lines, designing various efficient graph drawing algorithms, etc. In this paper, we make an attempt to generalize some of these tools to higher dimensions. We will mainly consider extremal problems of the following type. What is the largest number of edges (i-simplices) that a geometric hypergraph of n vertices can have without containing certain forbidden configurations? In particular, we discuss the special cases when the forbidden configura­ tions are k intersecting edges, k pairwise intersecting edges, k crossing edges, k pairwise crossing edges, k edges that can be stabbed by an i-flat, etc. Some of our estimates will be tight.
 
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 .

The authors of this article believe there is or should be a research area appropriately referred to as computational topology. Its agenda includes the identification and formalization of topological questions in computer applications and the study of algorithms for topological problems. It is hoped this article can contribute to the creation of a computational branch of topology with a unifying influence on computing and computer applications.
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

We show that the region lit by a point light source inside a simple n-gon after at most k reflections off the boundary has combinatorial complexity O(n2k ), for any k – 1. A lower bound of Ω((n/k θ(1))2k ) is also established which matches the upper bound for any fixed k. A simple near-optimal algorithm for computing the illuminated region is presented, which runs in O(n2k log n) time and O(n2k ) space for k > 1, and in O(n2 log2 n) time and O(n2 ) space for k = 1.
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.

Every collection of t > 2n^2 triangles with a total of n vertices in R^3 has \Omega(t^4/n^6) crossing pairs. This implies that one of their edges meets \Omega(t^3/n^6) of the triangles. From this it follows that n points in R^3 have only O(n^{8/3}) halving planes.

Reprint available upon request

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

Given a set of n labeled points on S^d, how many combinatorially different geometric triangulations for this point set are there? We show that the logarithm of this number is at most some positive constant times n^{\floor d/2}+1. Evidence is provided that for even dimensions d the bound can be improved to some constant times n^{d/2}.



Tamal K. Dey's Webpage