Books and Surveys

Delaunay Mesh Generation.
SiuWing
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




Delaunay
mesh generation of three dimensional
domains.
T. K. Dey. Technical Report
OSUCISRC9/07TR64, 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, SpringerVerlag, 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 ComputerAided 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
coauthors 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)
New version for 3rd edition to be published (2016).
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
applicationspecific 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

Computing height persistence and homology generators in R^3 efficiently
T.
K. Dey , July, 2018 arxiv version: https://arxiv.org/abs/1807.03655
Recently
it has been shown that computing the dimension of the first
homology group $H_1(K)$ of a simplicial $2$complex $K$ embedded
linearly in $R^4$ is as hard as computing the rank of a sparse
$01$ matrix. This puts a major roadblock to computing
persistence and a homology basis (generators) for complexes
embedded in $R^4$ and beyond in less than quadratic or even
nearquadratic time. But, what about dimension three? It is known
that persistence for piecewise linear functions on a complex $K$ with
$n$ simplices can be computed in $O(n\log n)$ time and a set of
generators of total size $k$ can be computed in $O(n+k)$ time when $K$
is a graph or a surface linearly embedded in $R^3$. But, the
question for general simplicial complexes $K$ linearly embedded
in $R^3$ is not completely settled. No algorithm with a complexity
better than that of the matrix multiplication is known for
this important case. We show that the persistence for {\em height
functions} on such complexes, hence called {\em height
persistence}, can be computed in $O(n\log n)$ time. This
allows us to compute a basis (generators) of $H_i(K)$, $i=1,2$, in
$O(n\log n+k)$ time where $k$ is the size of the output. This improves
significantly the current best bound of $O(n^{\omega})$, $\omega$ being
the matrix multiplication exponent. We achieve these improved
bounds by leveraging recent results on zigzag persistence in
computational topology, new observations about Reeb graphs, and some
efficient geometric data structures.



Edge contraction in persistencegenerated discrete Morse vector fields
T.
K. Dey and R. Slechta. Proc. SMI 2018, Computers & Graphics, to appear. Journal version: https://doi.org/10.1016/j.cag.2018.05.002
Recently,
discrete Morse vector fields have been shown to be useful in various
applications. Analogous to the simplification of large meshes using
edge contractions, one may want to simplify the cell complex $K$ on
which a discrete Morse vector field $V(K)$ is defined. To this end, we
define a gradient aware edge contraction operator for triangulated
$2$manifolds with the following guarantee. If $V(K)$ was generated by
a specific persistencebased method, then the vector field that results
from our contraction operator is exactly the same as the vector field
produced by applying the same persistencebased method to the
contracted complex. An implication of this result is that local
operations on $V(K)$ are sufficient to produce the persistencebased
vector field on the contracted complex. Furthermore, our experiments
show that the structure of the vector field is largely preserved by our
operator. For example, $1$unstable manifolds remain largely unaffected
by the contraction. This suggests that for some applications of
discrete Morse theory, it is sufficient to use a contracted complex.
Also, see our recent work on Discrete Morse based reconstruction here and here



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.
We investigate combinatorial dynamical systems on simplicial complexes considered as finite topological spaces.
Such systems arise in a natural way from sampling dynamics and may be
used to reconstruct some features of the dynamics directly from
the sample. We study the homological persistence of Morse decompositions
of such systems, an important descriptor of the dynamics, as a
tool for validating the reconstruction. Our framework can be viewed as
a step toward extending the classical persistence theory to ``vector
cloud" data. We present experimental results on two numerical
examples.



Computing Bottleneck Distance for 2D Interval Decomposable Modules
T.
K. Dey, C. Xin. Proc. (SoCG 2018), to appear.
Computation
of the interleaving distance between persistence modules is a central
task in topological data analysis. For $1$D persistence modules,
thanks to the isometry theorem, this can be done by computing the
bottleneck distance with known efficient algorithms. The question is
open for most $n$D persistence modules, $n>1$, because of the well
recognized complications of the indecomposables. Here, we consider a
reasonably complicated class called {\em $2$D interval decomposable}
modules whose indecomposables may have a description of nonconstant
complexity. We present a polynomial time algorithm to compute the
bottleneck distance for these modules from indecomposables, which
bounds the interleaving distance from above, and give another algorithm
to compute a new distance called {\em dimension distance} that bounds
it from below.



Graph Reconstruction by Discrete Morse Theory
T.
K. Dey, J. Wang and Y. Wang. Proc. (SoCG 2018), to appear.
Recovering hidden graphlike structures from potentially noisy data is a
fundamental task in modern data analysis. Recently, a persistenceguided
discrete Morsebased framework to extract a geometric graph from
lowdimensional data has become popular. However, to date, there is very
limited theoretical understanding of this framework in terms of graph
reconstruction. This paper makes a first step towards closing this gap.
Specifically, first, leveraging existing theoretical understanding of
persistenceguided discrete Morse cancellation, we provide a simplified version
of the existing discrete Morsebased graph reconstruction algorithm. We then
introduce a simple and natural noise model and show that the aforementioned
framework can correctly reconstruct a graph under this noise model, in the
sense that it has the same loop structure as the hidden groundtruth graph, and
is also geometrically close. We also provide some experimental results for our
simplified graphreconstruction algorithm.
Also see this paper in SIGSPATIAL (2017). Improved Road Network Reconstruction Using Discrete Morse Theory. T. K. Dey, J. Wang, and Y. Wang. Proc. SIGSPATIAL 2017.



Efficient Algorithms for Computing a Minimal Homology Basis
T.
K. Dey, T. Li, and Y. Wang. Proc. (LATIN 2018), to appear.
Efficient
computation of shortest cycles which form a homology basis
under Z2additions in a given simplicial complex K has been
researched actively in recent years. When the complex K is a weighted
graph with n vertices and m edges, the problem of computing a
shortest (homology) cycle basis is known to be solvable in $O(m^2n/\log
n+ n^2m)$time. Several works [1,2] have addressed the case when the
complex K is a 2manifold. The complexity of these algorithms
depends on the rank g of the onedimensional homology group of K.
This rank g has a lower bound of $\Theta(n)$, where n denotes the
number of simplices in K giving an $O(n^4)$ worstcase time complexity
for the algorithms in [1,2]. This worstcase complexity is improved in
[3] to $O(n^\omega+n^2g^{\omega1})$ for general simplicial complexes
where $\omega< 2.3728639$ [4] is the matrix multiplication exponent.
Taking $g=\Theta(n)$, this provides an $O(n^{\omega+1})$ worstcase
algorithm. In this paper, we improve this time complexity.
Combining the divide and conquer technique from [5] with the use
of annotations from [3], we present an algorithm that runs in
$O(n^\omega+n^2g)$ time giving the first $O(n^3)$ worstcase algorithm
for general complexes. If instead of minimal basis, we settle for
approximate basis, we can improve the running time even further. We
show that a 2approximate minimal homology basis can be computed
in $O(n^{\omega}\sqrt{n \log n})$ expected time. We also study more
general measures for defining the minimal basis and identify reasonable
conditions on these measures that allow computing a minimal basis
efficiently.



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
We study hierarchical clusterings of metric spaces that change over time.
This is a natural geometric primitive for the analysis of dynamic data sets.
Specifically, we introduce and study the problem of finding a temporally
coherent sequence of hierarchical clusterings from a sequence of unlabeled
point sets. We encode the clustering objective by embedding each point set into
an ultrametric space, which naturally induces a hierarchical clustering of the
set of points. We enforce temporal coherence among the embeddings by finding
correspondences between successive pairs of ultrametric spaces which exhibit
small distortion in the GromovHausdorff sense. We present both upper and lower
bounds on the approximability of the resulting optimization problems.



Temporal Clustering
T.
K. Dey, A. Rossi, and A. Sidiropoulos. Proc. European Symposium on Algorithms (ESA 2017).
Full Version
https://arxiv.org/abs/1704.05964
We study the problem of clustering sequences of unlabeled point
sets taken from a common metric space. Such scenarios arise naturally
in applications where a system or process is observed in distinct time
intervals, such as biological surveys and contagious disease
surveillance. In this more general setting existing algorithms for
classical (i.e.~static) clustering problems are not applicable anymore.
We propose a set of optimization problems which we collectively refer
to as \emph{temporal clustering}. The quality of a solution to a
temporal clustering instance can be quantified using three parameters:
the number of clusters $k$, the spatial clustering cost $r$, and the
maximum cluster displacement $\delta$ between consecutive time steps.
We consider spatial clustering costs which
generalize the wellstudied $k$center, discrete $k$median, and
discrete $k$means objectives of classical clustering problems. We
develop new algorithms that achieve tradeoffs between the three
objectives $k$, $r$, and $\delta$. Our upper bounds are complemented by
inapproximability results.



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]
Data analysis
often concerns not only the space where data come from, but also
various types of maps attached to data. In recent years, several
related structures have been used to study maps on data, including Reeb
spaces, mappers and multiscale mappers. The construction of these
structures also relies on the socalled \emph{nerve} of a cover of the
domain.
In this paper, we aim to analyze the topological information
encoded in these structures in order to provide better understanding of
these structures and facilitate their practical usage.
More specifically, we show that the onedimensional homology of
the nerve complex $N(\mathcal{U})$ of a pathconnected cover
$\mathcal{U}$ of a domain $X$ cannot be richer than that of the domain
$X$ itself. Intuitively, this result means that no new $H_1$homology
class can be ``created'' under a natural map from $X$ to the nerve
complex $N(\mathcal{U})$. Equipping $X$ with a pseudometric $d$, we
further refine this result and characterize the classes of $H_1(X)$
that may survive in the nerve complex using the notion of \emph{size}
of the covering elements in $\mathcal{U}$. These fundamental results
about nerve complexes then lead to an analysis of the $H_1$homology of
Reeb spaces, mappers and multiscale mappers.
The analysis of $H_1$homology groups unfortunately does not
extend to higher dimensions. Nevertheless, by using a mapinduced
metric, establishing a GromovHausdorff convergence result between
mappers and the domain, and interleaving relevant modules, we can still
analyze the persistent homology groups of (multiscale) mappers to
establish a connection to Reeb spaces.



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
[talk slides]
In many data analysis applications the following scenario is commonplace: we
are given a point set that is supposed to sample a hidden ground truth
$K$ in a metric space, but it got corrupted with noise so that some of
the data points lie far away from $K$ creating outliers also
termed as {\em ambient noise}. One of the main goals of denoising
algorithms is to eliminate such noise so that the curated data lie
within a bounded Hausdorff distance of $K$. Popular denoising
approaches such as deconvolution and thresholding often require the
user to set several parameters and/or to choose an appropriate noise
model while guaranteeing only asymptotic convergence. Our goal is to
lighten this burden as much as possible while ensuring theoretical
guarantees in all cases.
Specifically, first, we propose a simple denoising algorithm that
requires only a single parameter but provides a theoretical guarantee
on the quality of the output on general input points. We argue that
this single parameter cannot be avoided. We next present a simple
algorithm that avoids even this parameter by paying for it with a
slight strengthening of the sampling condition on the input points
which is not unrealistic. We also provide some preliminary empirical
evidence that our algorithms are effective in practice.



Parameterfree topology inference and sparsification for data on manifolds
T.
K. Dey, Z. Dong, and Y. Wang. (2015), older version at arXiv:1505.06462. Proc. ACMSIAM Sympos. Discrete Algorithms (SODA 2017).
[talk slides]
In topology inference from data, current approaches face two major problems.
One concerns the selection of a correct parameter to build an appropriate
complex on top of the data points; the other involves with the typical `large'
size of this complex. We address these two issues in the context of inferring
homology from sample points of a smooth manifold of known dimension sitting in
an Euclidean space Rk. We show that, for a sample size of n n
points, we can identify a set of O(n2)O(n^2) points (as opposed to O(n⌈k2⌉)O(n^\ceil{k/2}) Voronoi vertices) approximating a subset of the medial
axis that suffices to compute a distance sandwiched between the well known
local feature size and the local weak feature size (in fact, the approximating
set can be further reduced in size to O(n) O(n)). This distance, called the lean
feature size, helps pruning the input set at least to the level of local
feature size while making the data locally uniform. The local uniformity in
turn helps in building a complex for homology inference on top of the
sparsified data without requiring any usersupplied distance threshold. Unlike
most topology inference results, ours does not require that the input is dense
relative to a {\em global} feature such as {\em reach} or {\em weak feature
size}; instead it can be adaptive with respect to the local feature size. We
present some empirical evidence in support of our theoretical claims.



SimBa: An efficient tool for approximating Ripsfiltration persistence via Simplicial Batchcollapse
T.
K. Dey, D. Shi, and Y. Wang. European Symposium on Algorithms (ESA 2016).
An Extended Version.
[talk slides]
SimBa Software
SimPers Software
In
topological data analysis, a point cloud data P extracted from a metric
space is often analyzed by computing the persistence diagram or
barcodes of a sequence of Rips complexes built on P indexed by a scale
parameter. Unfortunately, even for input of moderate size, the size of
the Rips complex may become prohibitively large as the scale parameter
increases. Starting with the \emph{Sparse Rips filtration} introduced
by Sheehy, some existing methods aim to reduce the size of the complex
so as to improve the time efficiency as well. However, as we
demonstrate, existing approaches still fall short of scaling well,
especially for high dimensional data. In this paper, we investigate the
advantages and limitations of existing approaches. Based on insights
gained from the experiments, we propose an efficient new algorithm,
called SimBa, for
approximating the persistent homology of Rips filtrations with quality
guarantees. Our new algorithm leverages a batch collapse strategy as
well as a new sparse Ripslike filtration. We experiment on a variety
of low and high dimensional data sets. We show that our strategy
presents a significant size reduction, and our algorithm for
approximating Rips filtration persistence is order of magnitude faster
than existing methods in practice.



Multiscale Mapper: Topological summarization via codomain covers
T.
K. Dey, F. Memoli, and Y. Wang. ACMSIAM Sympos. Discrete Algorithms (SODA 2016) Older version arXiv: 1504.03763v1
[talk slides]
SODA version
Summarizing topological information from datasets and maps defined on them is a central theme in topological data analysis. Mapper,
a tool for such summarization, takes as input both a possibly high
dimensional dataset and a map defined on the data, and produces a
summary of the data by using a cover of the codomain of the map. This
cover, via a pullback operation to the domain, produces a simplicial
complex connecting the data points. The resulting view of the data
through a cover of the codomain offers flexibility in analyzing the
data. However, it offers only a view at a fixed scale at which the
cover is constructed. Inspired by the concept, we explore a notion of
hierarchical family of coverings which induces a hierarchical family of
simplicial complexes connected by simplicial maps, which we call multiscale mapper.
We study the resulting structure, its associated persistence module,
and its stability under perturbations of the maps and the coverings.
The information encoded in multiscale mapper complements that of
individual mappers at fixed scales. An upshot of this development is a
practical algorithm for computing the persistence diagram of multiscale
mapper when the domain is a simplicial complex and the map is a
realvalued piecewiselinear function.



Segmenting a surface mesh into pants using Morse theory
M. Hajij, T. K. Dey, and X. Li. Graphical Models, Vol 88 (2016), 1221.
http://www.sciencedirect.com/science/article/pii/S1524070316300376
A
pair of pants is a genus zero orientable surface with three boundary
components. A pants decomposition of a surface is a finite collection
of unordered pairwise disjoint simple closed curves embedded in the
surface that decompose the surface into pants. In this paper, we
present two Morse theory based algorithms for pants decomposition of a
surface mesh. Both algorithms operate on achoice of an appropriate
Morse function on the surface. The first algorithm uses this Morse
function to identify handles that are glued systematically to obtain a
pants decomposition. The second algorithm uses the Reeb graph of the
Morse function to obtain a pants decomposition. Both algorithms work
for surfaces with or without boundaries. Our perliminary implementation
of the two algorithms shows that both algorithms run in much less time
than an existing stateoftheart method, and the Reeb graph based
algorithm achieves the best time efficiency. Finally, we demonstrate
the robustness of our algorothms agaisnt noise.
 

Comparing graphs via persistence distortion
T.
K. Dey, D. Shi and Y. Wang. 31st Annu. Sympos. Comput. Geom. (SoCG 15).
[GraphComp software]
Metric graphs are ubiquitous in
science and engineering. For example, many data are drawn from hidden
spaces that are graphlike, such as the cosmic web. A metric graph
offers one of the simplest yet still meaningful ways to represent the
nonlinear structure hidden behind the data. In this paper, we propose
a new distance between two finite metric graphs, called the persistence
distortiondistance, which draws upon a topological idea. This
topological perspective along with the metric space viewpoint provide a
new angle to the graph matching problem. Our persistencedistortion
distance has two properties not shared by previous methods: First, it
is stable against the perturbations of the input graph metrics. Second,
it is a \emph{continuous} distance measure, in the sense that it is
defined on an alignment of the underlying spaces of input graphs,
instead of merely their nodes. This makes our persistencedistortion
distance robust against, for example, different discretizations of the
same underlying graph. Despite considering the input graphs as
continuous spaces, that is, taking all points into account, we show
that we can compute the persistencedistortion distance in polynomial
time. The time complexity for the discrete case where only graph nodes
are considered is much faster. We also provide some preliminary
experimental results to demonstrate the use of the new distance measure.



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.
Given a realvalued function ff defined over a manifold MM embedded in
R^dRd, we are interested in recovering structural information about
f f from the sole information of its values on a finite sample PP. Existing
methods provide approximation to the persistence diagram of ff when the noise
is bounded in both the functional and geometric domains. However, they fail in
the presence of aberrant values, also called outliers, both in theory and
practice.
We propose a new algorithm that deals with outliers. We handle aberrant
functional values with a method inspired from the knearest neighbors
regression and the local median filtering, while the geometric outliers are
handled using the distance to a measure. Combined with topological results on
nested filtrations, our algorithm performs robust topological analysis of
scalar fields in a wider range of noise models than handled by current methods.
We provide theoretical guarantees on the quality of our approximation and some
experimental results illustrating its behavior.



Spectral concentration and greedy kclustering
T. K. Dey, A. Rossi., and A. Sidiropoulos, arXiv:1404.1008v2
A popular graph clustering method is to consider the embedding of an input
graph into R^k induced by the first k eigenvectors of its Laplacian, and to
partition the graph via geometric manipulations on the resulting metric space.
Despite the practical success of this methodology, there is limited
understanding of several heuristics that follow this framework. We provide
theoretical justification for one such natural and computationally efficient
variant.
Our result can be summarized as follows. A partition of a graph is called
strong if each cluster has small external conductance, and large internal
conductance. We present a simple greedy spectral clustering algorithm which
returns a partition that is provably close to a suitably strong partition,
provided that such a partition exists. A recent result shows that strong
partitions exist for graphs with a sufficiently large spectral gap between the
kth and (k+1)th eigenvalues. Taking this together with our main theorem gives
a spectral algorithm which finds a partition close to a strong one for graphs
with large enough spectral gap. We also show how this simple greedy algorithm
can be implemented in nearlinear time for any fixed k and error guarantee.
Finally, we evaluate our algorithm on some realworld and synthetic inputs.



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]
Detecting the dimension of a hidden manifold from a point sample has
become an important problem in the current datadriven era. Indeed,
estimating the shape dimension is often the first step in studying the
processes or phenomena associated to the data. Among the many
dimension detection algorithms proposed in various fields, a few can
provide theoretical guarantee on the correctness of the estimated
dimension. However, the correctness usually requires certain regularity
of the input:
the input points are either uniformly randomly sampled in a statistical
setting, or they form the socalled $(\eps,\delta)$sample which can be
neither too dense nor too sparse.
Here, we propose a purely topological technique to detect dimensions.
Our algorithm is provably correct and works under a more relaxed
sampling condition: we do not require uniformity, and we also allow
Hausdorff noise. Our approach detects dimension by determining local
homology. The computation of this topological structure is much less
sensitive to the local distribution of points, which leads to the
relaxation of the sampling conditions. Furthermore, by leveraging
various developments in computational topology, we show that this local
homology at a point $z$ can be computed \emph{exactly} for manifolds
using VietorisRips complexes whose vertices are confined within a
local neighborhood of $z$. We implement our algorithm and demonstrate
the accuracy and robustness of our method using both synthetic and real
data sets.



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 fieldsee the conclusion of updated Full version)
[SimpPers software] [Talk slide]
Algorithms
for persistent homology and zigzag persistent homology are wellstudied
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 socalled
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 blowup in size.



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 1424.
[Talk slide] [Video link]
We introduce a markerless approach to deform a quality human body
template mesh from its original pose to a different pose specified by a
point cloud. The point cloud may be noisy, incomplete, or even captured
from a different person. In this approach, we first build coarse
correspondences between the template mesh and the point cloud through a
squeezed spectral embedding technique that exploits human body
extremities. Based on these correspondences, we define the goal of
nonrigid registration using an elastic energy functional and apply a
discrete gradient flow to reduce the difference between a coarse control
mesh and the point cloud. The deformed template mesh can then be
obtained from the deformation of the control mesh using mean value
coordinates afterwards. Our experiments show (see the supplementary
video) that the approach is capable of equipping a mesh with the pose of
a scanned point cloud data even if it is incomplete and noisy.



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 plink 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 (p1)link conditions can be contracted without disturbing
the pdimensional homology group. (ii) For relative homology groups, the (p1), and the (p2)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 plink condition
alone can be contracted without creating any new relative torsion and
the plink 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 107116.
[Talk slides] [Webpage] [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 VietorisRips and witness complexes. While the
VietorisRips complex is simple to compute and is a good vehicle for
extracting topology of sampled spaces, its size is hugeparticularly
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 VietorisRips
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
stateoftheart 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.
[Webpage] [Software ReebHanTun] [Talk slides]
A special family of nontrivial 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 nontrivial 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 nontrivial task and can be
quite expensive. Furthermore, such a tessellation may need to refine
the surface mesh, thus causing the undesirable sideeffect 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 PiecewiseSmooth Complexes (full version)
T. K. Dey and A. Slatton (SoCG 2013) Proc. 29th Annu. Sympos. Comput. Geom. (2013), pages 4756.
[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 divideandconquer 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 reestablishing 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 stateoftheart meshing tool of CGAL for generating large
meshes.



Voronoibased 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), 659668.
[Webpage] [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 nonmanifold 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 Voronoibased 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 ``FeaturePreserving 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), ACMSIAM Symposium on Discrete Algorithms (2013).
Recently,
various applications have motivated the study of spectral structures
(eigenvalues and eigenfunctions) of the socalled LaplaceBeltrami
operator of a manifold and their discrete versions. A popular choice for the discrete version is the socalled 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 particlebased
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, bubbleliquid and bubblesolid 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.



FeaturePreserving
reconstruction of singular surfaces
T. K. Dey, X. Ge, Q. Que, I.
Safa, L. Wang, Y. Wang. Computer Graphics Forum, Vol. 31 (5), 17871796,
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 nonmanifolds.
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 featurepreserving
singular surface reconstruction algorithm.



Topological
Persistence for circle valued maps
D. Burghelea and T. K. Dey. Discrete & Computational Geometry, Volume 50, No. 1 (2013), 6998. 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 68 (2012), 585595, DOI: 10.1007/s0037101207050 [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 realtime 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 nonlinear optimizations.
It would be ideal to develop a cagefree technique that provides realtime
defoirmation while respecting the local geometry. Using a simple eigenframework
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 cagebased 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 189200.
[Talk
slides] Earlier arxiv version arXiv:1107.3793v2
Let K be a simplicial complex and g the dimension of its pth 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 psimplex of K with a binary vector
of length g with the following property: the annotations, summed over
all psimplices in any pcycle 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 precomputation of annotations
permits answering queries about the independence or the triviality of pcycles
efficiently. Using annotations of edges in 2complexes, we derive better
algorithms for computing optimal basis and optimal homologous cycles in
1dimensional 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^{\omega1}). Here n denotes the size of the 2skeleton
of K and g the rank of H_1(K). Computing an optimal cycle homologous to
a given 1cycle is NPhard 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
2complexes 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), 14171426. Special issue Proc.
of Eurographics Sympos. Geometry Processing (SGP
2011). [Webpage]
[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 stateoftheart
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),
226235. Extended version in Discrete & Computational Geometry, Vol. 49 (2013), 4673.
[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 socalled {\em vertical homology
group}, as well as between cycles in M and in a Rips complex constructed
from P, we compute the H_1homology of the Reeb graph from P. It takes O(n
\log n) expected time, where n is the size of the 2skeleton of the Rips
complex. As a byproduct, when M is an orientable 2manifold, we also
obtain an efficient nearlinear 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 piecewiselinear
function defined on a filtration of a simplicial complex K, our algorithm
computes all persistent H_1homology for the Reeb graphs in O(n n_e^3) time,
where n is the size of the 2skeleton and n_e is the number of edges in K.



Localized Delaunay
refinement for sampling and meshing. [Talk
slides][Webpage][Software]
T. K. Dey, J. A. Levine, and
A. Slatton. Computer Graphics Forum. Vol. 29 (5)(2010), 17231732.
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 poseoblivious 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), 15451554. 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 multiscales
in a pose invariant manner is more appropriate for this case. The
Heat Kernel Signature function from spectral theory exhibits this multiscale
property. We show how this concept can be merged with the persistent
homology to design a novel efficient poseoblivious 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), 278287. Journal
version in Discrete Mathematics, Algorithms and Applications, Vol
2, Issue 4, 2010, 539552.
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 CohenSteiner 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 10261044.
Prelim. version in 42nd ACM Sympos. Comput. Theory (STOC 2010), 221230. arXiv:1001.0338v1[math.AT],
2nd January, 2010. [webpage]
[combined
talkslides]
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 torsionfree
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 NPhard 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 2cycle 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/02665611/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), 166175.
arXiv:0909.5654v1[cs.CG], 30th September 2009. [webpage]
[software]
[talkslides]
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 nonnegative 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), 650663.
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 LaplaceBeltrami operator of a manifold. Indeed, a variety
of work in graphics and geometric optimization uses the eigenstructures
(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 mmanifold 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), 2533.
As
a direct consequence of software quirks, designer errors,
and representation flaws, often threedimensional 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 nonsmoothly or in nonmanifold
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 computeraided 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),
13711382. [Webpage]
[Software]
[talkslide]
[Video]
We
present an algorithm for the reconstruction of a
surface with boundaries (including a nonorientable 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 alphacomplex
of a sample of the surface. No other postprocessing 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, 125134.
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 2manifold 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 OSUCISRC3/09TR05.



Delaunay
meshing of piecewise smooth complexes without
expensive predicates.
T. K. Dey, J.
A. Levine. Algorithms, vol. 2, issue 4 (2009), 13271349.
doi:10.3390/a2041327
Tech Report,
OSUCISRC7/08TR40, July 2008.
[Video][Software][Talkslide][Webpage]
Recently a
Delaunay
refinement algorithm has been proposed that
can mesh piecewise smooth complexes which include
polyhedra, smooth and piecewise smooth surfaces, and
nonmanifolds. 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 implementationfriendly.



Persistencebased
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 followup
paper of our
SIGGRAPH08 paper below.



Computing
Geometryaware Handle and Tunnel Loops in 3D
Models.
T. K. Dey, K.
Li, J. Sun, and D. CohenSteiner. SIGGRAPH 2008, 45:145:9.
[Video][Software][Talkslide][Webpage]
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, 115157.
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:
AlphaShapes 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) 493502



Normal
variation with adaptive feature size
(2007)
The proof of
the normal variation lemma (Lemma 2) in AmentaBern
paper ``Surface reconstruction by Voronoi filtering",
DCG, 1999, pg. 481504, 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 ACMSIAM Sympos. Discrete Algorithms (SODA 2008) (2008), 112121.
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 linesurface 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. Preprint
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), 477494.
[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. SurKolay, S. Nandy and A. Bagchi
(eds.), World Scientific Review Volume 3, 2008, 1741.



On
computing handle and tunnel loops
T. K. Dey, K. Li, and J. Sun.
IEEE Proc. Internat. Conf. Cyberworlds (NASAGEM workshop) (2007), 357366.
Journal version is in ComputerAided 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),
479512. Tech Report OSUCISRC4/06TR47, 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
sublevel 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), 241250.
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. ACMSIAM Sympos.
Discrete Algorithms (SODA 2007),
10961105. Journal Version in Discrete &
Comput. Geom., 2008, article in press. doi.10.1007/s0045400891093.
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 Lipschitzlike 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 curveskeletons
with medial geodesic function
T. K. Dey and J. Sun. Proc.
Sympos. Geometry Processing (SGP 2006), 143152.
CurveSkel Software
Many applications in geometric modeling,
computer graphics, visualization, and computer
vision benefit from a reduced representation
called curveskeletons 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 curveskeletons. 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
curveskeletons. Empirical study shows that the algorithm
is robust against noise, operates well with a single user parameter,
and produces curveskeletons with the desirable properties. Moreover,
the curveskeletons 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),
2737.
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, 2132.
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 noisefree 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. ACMSIAM Sympos. Discrete
Algorithms (SODA 2006), 202211.
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 wellshaped 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),
4352.
Conference
version.
Extended
version.
Technical
Report OSUCISRC405TR26, 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 nonuniform 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
OSUCISRC05TR25, April, 2005.
An early attempt
T. K. Dey, S. Goswami and
J. Sun. Smoothing
noisy point clouds
with Delaunay preprocessing and MLS.
Techreport OSUCISRC3/04TR17, 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 PointBased Graphics (2005), 3946.
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), 343361.
Journal version in Engineering with Computers, vol. 26,
page 289301, 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), 325342.
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 nonacute 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 epsilonsampling of a surface and flowcomplex based surface reconstruction.
T. K. Dey, J. Giesen,
E. A. Ramos and B. Sadri.
Proc. 21st Annu. Sympos. Comput.
Geom., (SOCG 2005), 218227.
( Invited Journal version in Internat.
J. Comput. Geom. Applications, Vol 18, 2008, 2961.)
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
SiuWing Cheng,
T. K. Dey and E. A. Ramos. Proc.
ACMSIAM Sympos. Discrete Algorithms, (SODA 2005), 10181027.
Extended
AbstractSee
also [Talk
slides]
We present an algorithm
to "reconstruct" a smooth kdimensional
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), 131143. (prelim.
version in (SODA 2005), 10281037).
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), 421461. 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 radiusedge 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),
280289 .
Extended
version,
in SIAM Journal Computing, Vol. 37 (2007), 11991227.
This paper presents
an algorithm for sampling and triangulating
a smooth surface in R^{3} 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, 124141. 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, 179200.
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 nondiscrete 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), 135150
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 viewdependent 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) topologypreserving 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 topologypreserving 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 2manifold has at most max{342g72,
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.,
2536
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 setup 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 socalled 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.
PointBased Graphics (2004), Marc Alexa
and S. Rusinkiewicz (eds) (2004), 193199.



Quality
meshing with weighted
Delaunay refinement
S.W. Cheng and
T. K. Dey.SIAM J. Computing, Vol. 33 (2003),
6993 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
pointplacement 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, 419434
(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), 125141.
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 watertight
surface reconstructor
T. K. Dey and S. Goswami. J. Computing
Inform. Sci. Engin., vol. 30, (2003),
302307.
Cocone Software



Dynamic
skin triangulation
HL. Cheng, T. K.
Dey, H. Edelsbrunner and J. Sullivan.
Discrete Comput. Geom., vol.
25, (2001), 525568 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), 883904
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 3dimensional Delaunay triangulations even
for wellspaced 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. ACMSIAM Symposium
on Discrete Algorithms (SODA '99)
, 1999, 893894
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), 2345, 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, 297325. Preliminary
version in IEEE (FOCS 1995),
266274
We describe an optimal
algorithm to decide if one closed curve
on a triangulated 2manifold 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 edgevertex 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 nonorientable. 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
ksets and related problems
T. K. Dey.Invited
paper in a special issue of Discrete
& Computational Geometry, Vol. 19,
No. 3, (1998), 373382
Prelim. version in IEEE (FOCS 1997).
We prove an O(nk^{1/3})
upper bound for planar ksets.
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 klevels
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), 473484. Preliminary
version in ISAAC 96, LNCS
1178, 105114
A geometric hypergraph
H is a collection of idimensional simplices,
called hyperedges or, simply, edges,
induced by some (i + 1)tuples of a vertex set
V in general position in dspace. 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 kset 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 (isimplices) 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 iflat, 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), 6178. Preliminary
version in 5th SWAT, 1996,
LNCS 1097, 284295
We show that the
region lit by a point light source inside
a simple ngon after at most k reflections
off the boundary has combinatorial complexity
O(n^{2k} ), 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 nearoptimal algorithm for computing
the illuminated region is presented, which runs
in O(n^{2k} log n) time and O(n^{2k}
) space for k > 1, and in O(n^{2} log^{2}
n) time and O(n^{2} ) 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), 281289 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), 315325.
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}.


