Books and Surveys
|
|
|
Delaunay
mesh generation of three dimensional domains.
T. K. Dey. Technical Report OSU-CISRC-9/07-TR64,
October, 2007. To appear
in Tessellations in the sciences: Virtues, Techniques and
Applications of Geometric Tilings, eds. R. van de Weygaert,
G. Vegter, J. Ritzerveld & V. Icke, Springer-Verlag, 2009.
Delaunay
meshes are used in various applications such as finite
element analysis, computer graphics rendering, geometric
modeling, and shape analysis. As the applications vary,
so do the domains to be meshed. Although meshing of geometric
domains with Delaunay simplices have been around for
a while, provable techniques to meshing various types of three
dimenisonal domains have been developed only recently. We
devote this article to presenting these techniques. We survey
various related results and detail a few core algorithms that
have provable guarantees and are amenable to practical implementation.
Delaunay refinement, a paradigm originally developed for guaranteeing
shape quality of mesh elements, is a common thread in these
algorithms. We finish the article by listing a set of open questions.
|
|
|
Sample
based geometric modeling
T. K. Dey. Chapter
in Geometric and Algorithmic Aspects
of Computer-Aided Design and Manufacturing, eds
Janardan, Smid, Dutta. DIMACS series in Discrete Mathematics
and Theoretical Computer Science, Volume 67,
2005.
A new paradigm for digital
modeling of physical objects from sample
points is fast emerging due to recent advances
in scanning technology. Researchers are
investigating many of the traditional modeling problems
in this new setting. We name this new area as
sample based geometric modeling.
The purpose of this article
is to expose the readers to this new modeling paradigm
through three basic problems, namely surface
reconstruction, medial axis approximation, and shape
segmentation. The algorithms for these three problems
developed by the author and his co-authors are described.
|
|
|
Curve
and surface reconstruction
T. K. Dey. Chapter
in Handbook of Discrete and Computational
Geometry, Goodman and O' Rourke eds., CRC
press, 2nd edition (2004)
The problem of reconstructing
a shape from its sample appears in many
scientific and engineering applications.
Because of the variety in shapes and applications,
many algorithms have been proposed over
the last two decades, some of which exploit
application-specific information and some
of which are more general. We will concentrate
on techniques that apply to the general setting and have
proved to provide some guarantees on the quality
of reconstruction. |
|
|
Papers
|
Animating
bubble interactions in a liquid foam
O. Busaryev, T. K. Dey, H. Wang,
and R. Zhong. (SIGGRAPH 2012), to appear.
Bubbles and foams are important features of liquid surface phenomena, but
they are difficult to animate due to their thin films and complex interactions
in the real world. In particular, small bubbles (having diameter <1cm)
in a dense foam are highly affected by surface tension, so their shapes are
much less deformable compared with larger bubbles. Under this small bubble
assumption, we propose a more accurate and efficient particle-based algorithm
to simulate bubble dynamics and interactions. The key component of this algorithm
is an approximation of foam geometry, by treating bubble particles as the
sites of a weighted Voronoi diagram. The connectivity information provided
by the Voronoi diagram allows us to accurately model various interaction effects
among bubbles. Using Voronoi cells and weights, we can also explicitly address
the volume loss issue in foam simulation, which is a common problem in previous
approaches. Under this framework, we present a set of bubble interaction
forces to handle miscellaneous foam behaviors, including foam structure under
Plateau's laws, clusters formed by liquid surface bubbles, bubble-liquid
and bubble-solid coupling, bursting and coalescing. Our experiment shows
that this method can be straightforwardly incorporated into existing liquid
simulators, and it can efficiently generate realistic foam animations, some
of which have never been produced in graphics before.
|
|
|
Topological
Persistence for circle valued maps
D. Burghelea and T. K. Dey. November,
2011. An earlier version 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.
|
|
|
Annotating
simplices with a homology basis and its applications
O. Busaryev, S. Cabello, C. Chen,
T. K. Dey, and Y. Wang. To appear in 13th Scandinavian Sympos.
Workshops Algorithm Theory (SWAT 2012). Earlier
arxiv version arXiv:1107.3793v2
Let K be a simplicial complex and g the dimension of its p-th homology
group H_p(K) defined with Z_2 coefficients. We show that we can compute a
basis H of H_p(K) and annotate each p-simplex of K with a binary vector of
length g with the following property: the annotations, summed over all p-simplices
in any p-cycle z, provide the coordinate vector of the homology class [z]
in the basis H. The basis and the annotations for all simplices can be computed
in O(n^{\omega}) time, where n is the size of K and \omega<2.376 is a
quantity so that two nxn matrices can be multiplied in O(n^{\omega})
time. The pre-computation of annotations permits answering queries about the
independence or the triviality of p-cycles efficiently. Using annotations
of edges in 2-complexes, we derive better algorithms for computing optimal
basis and optimal homologous cycles in 1-dimensional homology. Specifically,
for computing an optimal basis of H_1(K),we improve the time complexity known
for the problem from O(n^4) to O(n^{\omega}+n^2g^{\omega-1}). Here n denotes
the size of the 2-skeleton of K and g the rank of H_1(K). Computing an optimal
cycle homologous to a given 1-cycle is NP-hard even for surfaces and an algorithm
taking 2^{O(g)}n\log n time is known for surfaces. We extend this algorithm
to work with arbitrary 2-complexes in O(n^{\omega})+2^{O(g)}n^2\log n time
using annotations.
Also see this technical
report for a more practical algorithm.
|
|
|
Localized
Delaunay refinement for volumes
T. K. Dey and A. G. Slatton.
Computer Graphics Forum, Vol 30 (5), 1417--1426. Special issue Proc. of
Eurographics Sympos. Geometry Processing (SGP 2011).
[Web-page]
[Talk
slides] [Software]
Delaunay refinement, recognized as a versatile
tool for meshing a variety of geometries, has the deficiency that it does
not scale well with increasing mesh size. The bottleneck can be traced
down to the memory usage of 3D Delaunay triangulations. Recently an approach
has been suggested to tackle this problem for the specific case of smooth
surfaces by subdividing the sample set in an octree and then refining each
subset individually while ensuring {\em termination} and {\em consistency}.
We extend this to localized refinement of volumes, which brings about some
new challenges. We show how these challenges can be met with simple steps
while retaining provable guarantees, and that our algorithm scales many
folds better than a state-of-the-art meshing tool provided by CGAL.
Also, see the paper
below on localized Delaunay refinement for surfaces.
|
|
|
Reeb graphs: approximation
and persistence
T. K. Dey and Y. Wang. Proc.
27th Annu. Sympos. Comput. Geom. (SOCG 2011),
226--235.
[Extended
version]
Given a continuous function
f: X-> R on a topological space X, its {\em level set} f^{-1}(a)
changes continuously as the real value a changes. Consequently, the
connected components in the level sets appear, disappear, split and merge.
The Reeb graph of f summarizes this information into a graph structure.
Previous work on Reeb graph mainly focused on its efficient computation.
In this paper, we initiate the study of two important aspects of the Reeb
graph which can facilitate its broader applications in shape and
data analysis. The first one is the approximation of the Reeb graph of
a function on a smooth compact manifold M without boundary. The approximation
is computed from a set of points P sampled from M. By leveraging a relation
between the Reeb graph and the so-called {\em vertical homology group},
as well as between cycles in M and in a Rips complex constructed from
P, we compute the H_1-homology of the Reeb graph from P. It takes O(n \log
n) expected time, where n is the size of the 2-skeleton of the Rips complex.
As a by-product, when M is an orientable 2-manifold, we also obtain an efficient
near-linear time (expected) algorithm to compute the rank of H_1(M) from
point data. The best known previous algorithm for this problem takes O(n^3)
time for point data. The second aspect concerns the definition and computation
of the \emph{persistent Reeb graph homology} for a sequence of Reeb graphs
defined on a filtered space. For a piecewise-linear function defined on a
filtration of a simplicial complex K, our algorithm computes all persistent
H_1-homology for the Reeb graphs in O(n n_e^3) time, where n is the size of
the 2-skeleton and n_e is the number of edges in K.
|
|
|
Localized Delaunay
refinement for sampling and meshing. [Talk
slides][Web-page][Software]
T. K. Dey, J. A. Levine, and A. Slatton.
Computer Graphics Forum. Vol. 29 (5)(2010), 1723--1732. Specail
issue of Proc. Eurographics Sympos. Geometry Processing. (SGP 2010).
[Extended
version]
The technique of Delaunay
refinement has been recognized as a versatile tool to generate
Delaunay meshes of a variety of geometries. Despite its usefulness,
it suffers from one lacuna that limits its application. It does not
scale well with the mesh size. As the sample point set grows, the
Delaunay triangulation starts stressing the available memory space
which ultimately stalls any effective progress. A natural solution
to the problem is to maintain the point set in clusters and run the
refinement on each individual cluster. However, this needs a careful
point insertion strategy and a balanced coordination among the neighboring
clusters to ensure consistency across individual meshes. We design an
octtree based localized Delaunay refinement method for meshing surfaces
in three dimensions which meets these goals. We prove that the algorithm
terminates and provide guarantees about structural properties of the
output mesh. Experimental results show that the method can avoid memory
thrashing while computing large meshes and thus scales much better than
the standard Delaunay refinement method.
|
|
|
Persistent
heat signature for pose-oblivious matching of incomplete models.
[Talk
slides]
T. K. Dey, K. Li, C. Luo, P. Ranjan,
I. Safa, and Y. Wang. Computer Graphics Forum. Vol. 29 (5)
(2010), 1545--1554. Special isue of Proc. Sympos. Geometry Processing.
(SGP 2010).
Although understanding of
shape features in the context of shape matching and retrieval has
made considerable progress in recent years, the case for partial
and incomplete models in presence of pose variations still begs a robust
and efficient solution. A signature that encodes features at multi-scales
in a pose invariant manner is more appropriate for this case. The Heat
Kernel Signature function from spectral theory exhibits this multi-scale
property. We show how this concept can be merged with the persistent homology
to design a novel efficient pose-oblivious matching algorithm for all
models, be they partial, incomplete, or complete. We make the algorithm
scalable so that it can handle large data sets. Several test results
show the robustness of our approach.
|
|
|
Tracking
a generator by persistence.
O. Busaryev, T. K. Dey, and Y. Wang.
16th Annu. Internat. Computating and Combinatorics Conf.
(COCOON 2010), 278--287. Journal version
in Discrete Mathematics, Algorithms and Applications, Vol 2, Issue
4, 2010, 539--552.
DOI:10.1142/S1793830910000875.
The persistent homology provides
a mathematical tool to describe ``features" in a principle manner.
The persistence algorithm proposed by Edelsbrunner et al. [5] can
compute not only the persistent homology for a filtered simplicial
complex, but also representative generating cycles for persistent
homology groups. However, if there are dynamic changes either in the
filtration or in the underlying simplicial complex, the representative
generating cycle can change wildly.
In this paper, we consider the problem of tracking
generating cycles with temporal coherence. Specifically, our
goal is to track a chosen essential generating cycle so that the
changes in it are ``local". This requires reordering simplices in
the filtration, To handle reordering operations. we build upon the
matrix framework proposed by Cohen-Steiner et al.[3] to swap two consecutive
simplices, so that we can process a reordering directly. We present
an application showing how our algorithm can track an essential cycle
in a complex constructed out of a point cloud data.
|
|
|
Optimal
homologous cycles, total unimodularity, and linear programming.
T. K. Dey, A. Hirani, and B. Krishnamoorthy.
SIAM J. Computing, Vol. 40, pp 1026--1044. Prelim. version
in 42nd ACM Sympos. Comput. Theory (STOC
2010), 221--230. arXiv:1001.0338v1[math.AT], 2nd January,
2010. [web-page]
[combined
talk-slides]
Given a simplicial complex
with weights on its simplices, and a nontrivial cycle on it,
we are interested in finding the cycle with minimal weight which
is homologous to the given one. Assuming that the homology is defined
with integer (Z) coefficients, we show the following (Theorem
5.2):
For a finite simplicial complex K of dimension
greater than p, the boundary matrix [d_(p+1)] is totally
unimodular if and only if H_p(L,L_0) is torsion-free for all
pure subcomplexes L_0, L in K of dimension p and p+1 respectively
where L_0\subset L.
Because of the total unimodularity of the
boundary matrix, we can solve the optimization problem, which
is inherently an integer programming problem, as a linear program
and obtain integer solution. Thus the problem of finding optimal
cycles in a given homology class can be solved in polynomial time.
This result is surprising in the backdrop of a recent result which
says that the problem is NP-hard under Z_2 coefficients which, being
a field, is in general easier to deal with. One consequence of our
result, among others, is that one can compute in polynomial time an
optimal 2-cycle in a given homology class for any finite simplicial complex
embedded in R^3. Our optimization approach can also be used for various
related problems, such as finding an optimal chain homologous to a given
one when they are not cycles.
|
|
|
Approximating
cycles in a shortest basis of the first homology group from point
data
T. K. Dey, J. Sun, and Y. Wang.
Inverse Problems, Vol. 27 (2011), 124004. doi:10.1088/0266-5611/27/12/124004
An earlier version appeared with title ``Approximating loops in a shortest
homology basis from point data" in Proc. 26th Annu. Sympos. Comput.
Geom. (SOCG 2010), 166--175. arXiv:0909.5654v1[cs.CG],
30th September 2009. [web-page]
[software]
[talk-slides]
Inference
of topological and geometric attributes of a hidden manifold
from its point data is a fundamental problem arising in
many scientific studies and engineering applications. In this
paper we present an algorithm to compute a set of cycles from a
point data that presumably sample a smooth manifold M\subset R^d.
These cycles approximate a shortest basis of the one dimensional
homology group H_1(M) over coefficients in finite field Z_2.
Previous results addressed the issue of computing the rank of the
homology groups from point data, but there is no result on approximating
the shortest basis of a manifold from its point sample. In arriving
our result, we also present a polynomial time algorithm for computing
a shortest basis of H_1(K) for any finite simplicial complex K whose edges
have non-negative weights.
|
|
|
Convergence,
Stability, and Discrete Approximation of Laplace Spectra
T. K. Dey, P. Ranjan, and Y. Wang.
Proc. ACM/SIAM Sympos. Discrete Algorithms (SODA 2010), 650--663.
Paper
with a minor correction.
Spectral
methods have been widely used in a broad range of applications
fields. One important object involved in such methods is the
Laplace-Beltrami operator of a manifold. Indeed, a variety of
work in graphics and geometric optimization uses the eigen-structures
(i.e., the eigenvalues and eigenfunctions) of the Laplace operator.
Applications include mesh smoothing, compression, editing, shape
segmentation, matching, parameterization, and so on. While the Laplace
operator is defined (mathematically) for a smooth domain, these applications
often approximate a smooth manifold by a discrete mesh. The spectral
structure of the manifold Laplcian is estimated from some discrete Laplace
operator constructed from this mesh.
In this paper, we study the important
question of how well the specturm computed from the discrete
mesh approximates the true spectrum of the manifold Lplacian.
We exploit a recent result on mesh Laplacian and provide the first
convergence result to relate the spectrum constructed from a general
mesh (approximating an m-manifold embedded in R^d) with the true
spectrum. We also study how stable these eigenvalues and their
discrete approximations are when the underlying manifold is perturbed,
and provide explicit bounds for the Laplacian spectra of two ``close"
manifolds, as well as a convergence result for their discrete approximations.
Finally, we present various experimental results to demonstrate
that these discrete spectra are both accurate and robust in practice.
|
|
|
Repairing
and meshing imperfect shapes with Delaunay refinement
O. Busaryev, T. K. Dey, J. A. Levine.
Proc. SIAM/ACM Joint Conf. Geometric and Physical
Modeling (SPM 2009), 25--33.
As
a direct consequence of software quirks, designer errors,
and representation flaws, often three-dimensional shapes
are stored in formats that introduce inconsistencies such as small
gaps and overlaps between surface patches. We present a new algorithm
that simultaneously repairs imperfect geometry and topology
while generating Delaunay meshes of these shapes. At the core
of this approach is a meshing algorithm for input shapes that are piecewise
smooth complexes (PSCs), a collection of smooth surface patches meeting
at curves non-smoothly or in non-manifold configuarations.
Guided by a user tolerance parameter, we automatically merge nearby
components while building a Delaunay mesh that has many of these errors
fixed. Experimental evidence is provided to show the results of our
algorithm on common computer-aided design (CAD) formats. Our algorithm
may also be used to simplify shapes by removing small features
which would require an excessive number of elements to preserve them
in the output mesh.
Note: One of the main ingredients
of this paper is our PSC
meshing paper.
|
|
|
Isotopic
Reconstruction of Surfaces with Boundaries
T. K. Dey, K. Li.,
E. A. Ramos, and R. Wenger. Proc. Sympos.
Geom. Processing.(SGP09), special issue of
Computer Graphics Forum, Vol. 28, No. 5 (2009), 1371--1382.
[Web-page]
[Software]
[talk-slide]
[Video]
We
present an algorithm for the reconstruction of a surface
with boundaries (including a non-orientable one) in three
dimensions from a sufficiently dense sample. It is guaranteed
that the output is isotopic to the unknown sampled surface. No previously
known algorithm guarantees isotopic or homeomorphic reconstruction
of surfaces with boundaries. Our algorihtm is surprisingly simple.
It `peels' slivers greedily from an alpha-complex of a sample of
the surface. No other post-processing is necessary. We provide
several experimental results from an implementation of our basic
algorithm and also a modified version of it.
|
|
|
Cut
Locus and Topology from Surface Point Data.
T. K. Dey, K. Li.
Proc. 25th Ann. Sympos. Comput. Geom.(SOCG09), 2009, 125--134.
A
cut locus of a point in a compact Riemannian manifold
M is defined as the set of points where minimizing geodesics
issued from p stop being minimizing. It is known that a cut
locus contains most of the topological information of M. Our
goal is to utilize this property of cut loci to decipher the
topology of M from a point sample. Recently it has been shown
that Rips complexes can be built from a point sample P of
M systematically to compute the Betti numbers, the rank of the homology
groups of M. Rips complexes can be computed easily and therefore are
favored over others such as restricted Delaunay, alpha, Cech, and
witness complex. However, the sizes of the Rips complexes tend to
be large. Since the dimension of a cut locus is lower than that of
the manifold M, a subsample of P approximating the cut locus is usually
much smaller in size and hence admits a relatively smaller Rips
complex.
In this paper we explore
the above approach for point data sampled from surfaces
embedded in any high dimensional Euclidean space. We present
an algorithm that computes a subsample P' of a sample P of
a 2-manifold where P' approximates a cut locus. Empirical results
show that the first Betti number of M can be computed from Rips
complexes built on these subsamples. The sizes of these Rips
complexes are much smaller than the one built on the original sample
of M.
Our first attempt on a related
topic was the following paper:
Topology
from Data via Geodesic Complexes. T. K. Dey
and K. Li. Tech Report OSU-CISRC-3/09-TR05.
|
|
|
Delaunay
meshing of piecewise smooth complexes without expensive
predicates.
T. K. Dey, J. A.
Levine. Algorithms, vol. 2, issue 4 (2009), 1327--1349.
doi:10.3390/a2041327
Tech Report, OSU-CISRC-7/08-TR40,
July 2008.
[Video][Software][Talk-slide][Web-page]
Recently a
Delaunay
refinement algorithm has been proposed that
can mesh piecewise smooth complexes which include polyhedra,
smooth and piecewise smooth surfaces, and non-manifolds.
However, this algorihtm employs domain dependent numerical
predicates, some of which could be computationally expensive
and hard to implement. In this paper we develop a refinement
strategy that eliminates these complicated domain dependent predicates.
As a result we obtain a meshing algorithm that is practical and
implementation-friendly.
|
|
|
Persistence-based
Handle and Tunnel Loops Computation Revisited for
Speed Up.
T. K. Dey and K.
Li. Shape Modeling International (SMI09),
2009. Special issue of Computer & Graphics, Article in
press,
doi:10.1016/j.cag.2009.03.008.
[Software]
Loops in surfaces
associated with topological features such as handles and
tunnels are important entities in many applications including
surface parameterization, feature identification, and topological
simplification. Recently, a persistent homology based algorithm
has been proposed to compute them. The algorithm has several
advantages including its simplicity, combinatorial nature
and independence from computing other extra structures. In
this paper, we propose changes to this loop computation algorithm
based on some novel observations. These changes reduce the computation
time of the algorithm dramatically. In particular, our experimental
results show that the suggested changes achieve considerable speed
up for large data sets without sacrificing loop qualities.
Note: This is a follow-up
paper of our
SIGGRAPH08 paper below.
|
|
|
Computing
Geometry-aware Handle and Tunnel Loops in 3D
Models.
T. K. Dey, K. Li,
J. Sun, and D. Cohen-Steiner. SIGGRAPH 2008, 45:1--45:9.
[Video][Software][Talk-slide][Web-page]
Many applications
such as topology repair, model editing, surface parameterization,
and feature recognition benefit from computing loops on surfaces
that wrap around their `handles' and `tunnels'. Computing
such loops while optimizing their geometric lengths is difficult.
On the other hand, computing such loops without considering
geometry is easy but may not be very useful. In this paper we strike
a balance by computing topologically correct loops that are
also geometrically relevant. Our algorithm is a novel application
of the concepts from topological persistence introduced recently
in computational topology. The usability of the computed loops
is demonstrated with some examples in feature identification and
topology simplification.
Note: See the paper below
On
computing handle and tunnel loops for our
first attempt on this problem.
|
|
|
Recursive
geometry of the flow complex
and topology of the flow complex filtration.
K.
Buchin, T. K. Dey, J. Giesen, and M. John. Comput.
Geom. Theory Application. (2008),
vol. 40, 115--157.
The flow complex
is a geometric structure, similar to the Delaunay tessellation,
to organize a set of (weighted) points in R^k. Flow shapes
are topological spaces correspoding to substructures of
the flow complex. The flow complex and flow shapes have found
applications in surface reconstruction, shape matching,
and molecular modeling. In this article we give an algorithm
for computing the flow complex of weighted points in any dimension.
The algorithm reflects the recursive structure of the flow
complex. On the basis of the algorithm we establish a topological
similarity between flow shapes and the nerve of a corresponding
ball set, namely homotopy equivalence.
This paper grew out of:
Alpha-Shapes and Flow Shapes are Homotopy Equivalent.
T. K. Dey, J. Giesen and M. John. Proceedings of the 35th Annual
ACM Symposium on Theory of Computing (STOC
2003) 493-502
|
|
|
Normal
variation with adaptive feature size
(2007)
The proof of the
normal variation lemma (Lemma 2) in Amenta-Bern
paper ``Surface reconstruction by Voronoi filtering", DCG,
1999, pg. 481-504, is not correct (which also appears in
my book on reconstruction). In this short note we fix the
problem and improve the bound on the normal variation. This
should improve various bounds derived afterwards using the
normal variation result.
|
|
|
Maintaining
Deforming Surface Meshes
S.-W. Cheng and T. K. Dey. Proc. 19th
ACM-SIAM Sympos. Discrete Algorithms (SODA 2008) (2008), 112--121.
We present a method to maintain a mesh approximating
a deforming surface, which is specified by
a dense set of sample points. We identify a reasonable
motion model for which a provably good surface mesh
can be maintained. Our algorithm determines the appropriate
times at which the mesh is updated to maintain a good approximation.
The updates use simple primitives, and no costly computation
such as line-surface intersection is necessary. Point insertions
and deletions are allowed at the updates. Each update takes
time linear in the size of the current sample set plus the new
sample points inserted. We also construct examples for which,
under the same model, no other algorithm makes asymptotically
fewer changes to the mesh than our algorithm.
This paper is based on the following flip paper available
as a preprint from computational geoemtry
arxiv.
|
|
|
Delaunay
Edge Flips in Dense Surface Triangulations
S.-W. Cheng and T. K. Dey. Pre-print
arXiv:cs.CG/0712.1959, 2007. short
version in EuroCG 2008.
Note: We are temporarily
retracting this result due to a bug in a Lemma (Lemma
3.1). We are trying to salvage the other results without using
Lemma 3.1. The abstract was:
Delaunay
flip is an elegant, simple tool to convert
a triangulation of a point set to its Delaunay triangulation.
The technique has been researched extensively for
full dimensional triangulations of point sets. However,
an important case of triangulations which are not full dimensional
is surface triangulations in three dimensions. In this
paper we address the question of converting a surface triangulation
to a subcomplex of the Delaunay triangulation with edge
flips. We show that the surface triangulations which closely
approximate a smooth surface with uniform density can be transformed
to a Delaunay triangulation with a simple edge flip algorithm.
The condition on uniformity becomes less stringent with increasing
density of the triangulation. If the condition is dropped completely,
the flip algorithm still terminates although the output surface
triangulation becomes ``almost Delaunay" instead of exactly Delaunay.
|
|
|
A
practical Delaunay meshing algorithm for a large class
of domains
S.-W. Cheng, T. K. Dey, and J. A. Levine.
Proc. 16th Internat. Meshing Roundtable (IMR 2007), 477--494.
[Talk
slides]
Recently
a Delaunay refinement algorithm has been proposed
that can mesh domains as general as piecewise
smooth complexes [CDR07]. In this paper we introduce
a novel modification of the algorithm to make
it implementable in practice. In particular, we replace
four tests of the original algorithm with only a single test
that is easy to implement. The algorithm has the following
guarantees. The output mesh restricted to each manifold element
in the complex is a manifold with proper incidence relations.
More importantly, with increasing level of refinement which
can be controlled by an input parameter, the output mesh becomes
homeomorphic to the input while preserving all input features. Implementation
results on a disparate array of input domains are presented to corroborate
our claims.
For the theory see the following paper:
Theory
of a practical Delaunay meshing algorithm for a large
class of domains. S.-W. Cheng, T. K. Dey and
J. Levine. Algorithms, Architecture and Information Systems
Security, B. Bhattacharya, S. Sur-Kolay, S. Nandy and A. Bagchi
(eds.), World Scientific Review Volume 3, 2008, 17--41.
|
|
|
On
computing handle and tunnel loops
T. K. Dey, K. Li, and J. Sun. IEEE
Proc. Internat. Conf. Cyberworlds (NASAGEM workshop) (2007), 357--366.
Journal version is in Computer-Aided Design, in press,
doi:10.1016/j.cad.2009.01.001.
[Talk
slides] HandleTunnel
software
Many applications seek to identify features
like `handles' and `tunnels' in a shape bordered
by a surface embedded in three dimensions. To this end
we define handle and tunnel loops on surfaces which
can help identifying these features. We show that a closed
surface of genus g always has g handle and g tunnel loops
induced by the embedding. For a class of shapes that retract
to graphs, we characterize these loops by a linking condition
with these graphs. These characterizations lead to algorithms
for detection and generation of these loops. We provide an
impementation with applications to feature detection and topology
simplification to show the effectiveness of the method.
|
|
|
Stability of critical points with interval persistence
T. K. Dey and R. Wenger. Discrete
& Computational Geometry, vol 38 (2007),
479--512. Tech Report OSU-CISRC-4/06-TR47, April
2006.
Scalar functions defined on a topological
space T are at the core of many applications
such as shape matching, visualization, and physical
simulations. Topological persistence is an approach
to characterizing these functions. It measures
how long topological structures in the level sets {x
in T : f(x) <= c} persist as c changes. Recently it was
shown that the critical values defining a topological
structure with relatively large persistence remain almost
unaffected by small perturbations. This result suggests
that topological persistence is a good measure for matching
and comparing scalar functions. We extend these results
to critical points in the domain
by redefining persistence and critical points and replacing
sub-level sets {x in T : f(x) <= c} with interval
sets {x in T : a<=f(x)< b}. With these modifications
we establish a stability result for critical points.
This result is strengthened for maxima that can be used
for matching two scalar functions.
|
|
|
Delaunay meshing of isosurfaces
T. K. Dey and J. A. Levine. Proc.
Shape Modeling International (SMI 2007), 241--250.
DelIso software
We
present an isosurface meshing algorithm DelIso, based on
the Delaunay refinement paradigm. This paradigm has
been successfully applied to mesh a variety of domains with
guarantees for topology, geometry, mesh gradedness, and triangle
shape. A restricted Delaunay triangulation, dual of the intersection
between the surface and the three dimensional Voronoi diagram,
is often the main ingredient in Delaunay refinement.
Computing and storing three dimensional Voronoi/Delaunay diagrams
become bottlenecks for Delaunay refinement techniques since
isosurface computations generally have large input datasets
and output meshes. A highlight of our algorithm is that we
find a simple way to recover the restricted Delaunay triangulation
of the surface without computing the full 3D structure. We employ
techniques for efficient ray tracing of isosurfaces to generate
surface sample points, and demonstrate the effectiveness of
our implementation on a variety of volume datasets. |
|
|
Delaunay refinement for piecewise
smooth complexes
S.-W. Cheng, T. K. Dey, and E. A. Ramos.
Proc. 18th Annu. ACM-SIAM Sympos.
Discrete Algorithms (SODA 2007),
1096--1105. Journal Version in Discrete &
Comput. Geom., 2008, article in press. doi.10.1007/s00454-008-9109-3.
Extended
Full Version
We present a Delaunay refinement algorithm for meshing
a piecewise smooth complex in three dimensions
with correct topology. The small angles between
the tangents of two meeting manifold patches pose difficulty.
We protect these regions with weighted points. The
weights are chosen to mimic the local feature size and to
satisfy a Lipschitz-like property. A Delaunay refinement
using the weighted Voronoi diagram is shown to terminate
with the recovery of the topology of the input. To this end,
we present new concepts and results including a new definition
of local feature size and a proof for a generalized topological
ball property.
|
|
|
Defining
and computing curve-skeletons with
medial geodesic function
T. K. Dey and J. Sun. Proc.
Sympos. Geometry Processing (SGP 2006), 143--152.
CurveSkel Software
Many applications in geometric modeling, computer
graphics, visualization, and computer vision
benefit from a reduced representation called curve-skeletons
of a shape. These are curves possibly with branches
which compactly represent the shape geometry and
topology. The lack of a proper mathematical definition
has been a bottleneck in developing and applying the
curve-skeletons. A set of desirable properties of these
skeletons has been identified and the existing algorithms
try to satisfy these properties mainly through a procedural
definition. We define a function called medial geodesic on
the medial axis which leads to a mathematical definition
and an approximation algorithm for curve-skeletons. Empirical
study shows that the algorithm is robust against noise, operates
well with a single user parameter, and produces curve-skeletons
with the desirable properties. Moreover, the curve-skeletons
can be associated with additional attributes that follow naturally
from the definition. These attributes capture shape eccentricity,
a local measure of how far a shape is away from a tubular one.
|
|
|
Identifying
flat and tubular regions of a shape
by unstable manifolds
S. Goswami, T. K. Dey, and C. Bajaj.
Proc. 11th ACM Sympos. Solid
Modeling Applications (SPM 2006),
27--37.
We present an algorithm
to identify the flat and tubular regions of a
three dimensional shape from its point sample. We
consider the distance function to the input point cloud
and the Morse structure induced by it on R^3. Specifically
we focus on the index 1 and index 2 saddle points and their
unstable manifolds. The unstable manifolds of index 2
saddles are one dimensional whereas those of index 1 saddles are
two dimensional. Mapping these unstable manifolds back
onto the surface, we get the tubular and flat regions. The
computations are carried out on the Voronoi diagram of the
input points by approximating the unstable manifolds with
Voronoi faces. We demonstrate the performance of our algorithm
on several point sampled objects. |
|
|
Normal
and feature approximations
from noisy point clouds.
T. K. Dey and J. Sun.
Proc. FST&TCS 2006,
LNCS 4337, 21--32.
NormFet
software
We consider the problem of approximating
normal and feature sizes approximations of
a surface from point cloud data that may be noisy.
These problems are central to many applications
dealing with point cloud data. In the noise-free case, the
normals and feature sizes can be approximated by the
centers of a set of unique large Delaunay balls called
polar balls. In presence of noise, polar balls do not
necessarily remain large and hence their centers may not
be good for normal and feature approximations. Earlier
works suggest that some large Delaunay balls can play the role
of polar balls. However, these results were short in explaining
how the big Delaunay balls should be chosen for reliable approximations
and how the approximation error depends on various factors.
We provide new analyses that fill these gaps. In particular,
they lead to new algorithms for practical and reliable normal and
feature approximations.
|
|
|
Anisotropic
surface meshing
S.-W. Cheng, T. K. Dey and E. A. Ramos.
Proc. ACM-SIAM Sympos. Discrete
Algorithms (SODA 2006), 202--211.
We study the problem
of triangulating a smooth closed implicit surface
S endowed with a 2D metric tensor that varies over
S. This is commonly known as the anisotropic surface
meshing problem. We extend the 2D metric tensor naturally
to 3D and employ the 3D anisotropic Voronoi diagram
of a set P of samples on S to triangulate S. We prove that
a restricted dual, Mesh P, is a valid triangulation
homeomorphic to S under appropriate conditions. We also
develop an algorithm for constructing P and Mesh P. In
addition to being homeomorphic to S, each triangle in
Mesh P is well-shaped when measured using the 3D metric tensors
of its vertices. Users can set upper bounds on the anisotropic
edge lengths and the angles between the surface normals at vertices
and the normals of incident triangles (measured both isotropically
and anisotropically). |
|
|
An Adaptive MLS Surface for
Reconstruction with Guarantees.
T. K. Dey and J. Sun.
Symposium on Geometry
Processing (SGP 2005),
43--52.
Conference
version.
Extended
version.
Technical Report
OSU-CISRC-4-05-TR26, April, 2005.
AMLS Software
Recent work have shown
that moving least squares (MLS) surfaces
can be used effectively to reconstruct surfaces
from possibly noisy point cloud data. Several
variants of MLS surfaces have been suggested, some
of which have been analyzed theoretically for guarantees.
These analyses, so far, have assumed uniform sampling
density. We propose a new variant of the MLS surface
that, for the first time, incorporates local feature sizes
in its formulation, and we analyze it for reconstruction
guarantees using a non-uniform sampling density. The
proposed variant of the MLS surface has several computational
advantages over existing MLS methods.
Also see
Extremal
Surface Based Projections
Converge and Reconstruct with Isotopy.
T. K. Dey, S. Goswami and J.
Sun. Technical Report OSU-CISRC-05-TR25,
April, 2005.
An early attempt
T. K. Dey, S. Goswami and J.
Sun. Smoothing
noisy point clouds
with Delaunay preprocessing and MLS.
Tech-report OSU-CISRC-3/04-TR17, 2004.
|
|
|
Normal
Estimation for Point
Clouds : A Comparison Study for a
Voronoi Based Method
T. K. Dey, G. Li and
J. Sun. Eurographics Sympos.
on Point-Based Graphics (2005), 39--46.
Many applications that process
a point cloud data benefit from a reliable
normal estimation step. Given a point cloud presumably
sampled from an unknown surface, the problem
is to estimate the normals of the surface at the
data points. Two approaches, one based on numerical
optimizations and another based on Voronoi diagrams are
known for the problem. Variations of numerical approaches
work well even when point clouds are contaminated with
noise. Recently a variation of the Voronoi based method is proposed
for noisy point clouds. The centrality of the normal estimation
step in point cloud processing begs a thorough study of the
two approaches so that one knows which approach is appropriate
for what circumstances. This paper presents such results.
|
|
|
Polygonal Surface
Remeshing with Delaunay Refinement
T. K. Dey, G. Li and
T. Ray. Proc.14th Internat.
Meshing Roundtable, (IMR 2005),
343--361.
Journal version in Engineering with Computers, vol. 26, page
289--301, 2010.
Conference
version
Extended
version
SurfRemesh
software
Polygonal meshes are used to
model smooth surfaces in many applications.
Often these meshes need to be remeshed for improving
the quality, density or gradedness. We apply the
Delaunay refinement paradigm to design a provable
algorithm for isotropic remeshing of a polygonal mesh
that approximates a smooth surface. The proofs provide
new insights and our experimental results corroborate
the theory.
|
|
|
Weighted
Delaunay Refinement for
Polyhedra with Small Angles
S.-W. Cheng, T. K. Dey
and T. Ray. Proc.14th Internat.
Meshing Roundtable (IMR
2005), 325--342.
Recently, a provable Delaunay
meshing algorithm called QMesh has been
proposed for polyhedra that may have acute input
angles. The algorithm guarantees bounded circumradius
to shortest edge length ratio for all tetrahedra
except the ones near small input angles. This guarantee
eliminates or limits the occurrences of all types of
poorly shaped tetrahedra except slivers. A separate
technique called weight pumping is known for sliver
elimination. But, allowable input for the technique
so far have been periodic point sets and piecewise linear
complex with non-acute input angles. In this paper, we incorporate
the weight pumping method into QMesh thereby ensuring that
all tetrahedra except the ones near small input angles have
bounded aspect ratio. Theoretically, the algorithm has
an abysmally small angle guarantee inherited from the weight
pumping method. Nevertheless, our experiments show that
it produces better angles in practice.
|
|
|
Critical points of distance
to an epsilon-sampling of a surface and flow-complex- based surface reconstruction.
T. K. Dey, J. Giesen,
E. A. Ramos and B. Sadri.
Proc. 21st Annu. Sympos. Comput.
Geom., (SOCG 2005), 218--227.
( Invited Journal version in Internat.
J. Comput. Geom. Applications, Vol 18, 2008, 29--61.)
Extended
version.
The distance function
to surfaces in three dimensions plays a
key role in many geometric modeling applications
such as medial axis approximations, surface
reconstructions, offset computations, feature
extractions and others. In most of these cases, the
distance function to the surface is approximated
by a discrete distance function where the distances
are measured from a discrete sample of the surface. The
critical points of the distance function determines the topology
of the geometric structures in question. Howvere, no
theoretical result exists linking the sampling and the
critical point structures of the distance functions. We
provide this link by showing that the critical points of
the discrete distance function either lie very close to the
surface or near the medial axis both quantified with the sampling
density. One implication of this result is that known Morse
theory based surface reconstruction algorithms do indeed
approximate the surface geometrically.
|
|
|
Manifold
Reconstruction from Point Samples
Siu-Wing Cheng, T. K.
Dey and E. A. Ramos. Proc. ACM-SIAM
Sympos. Discrete Algorithms, (SODA 2005), 1018--1027.
Extended
AbstractSee
also [Talk
slides]
We present an algorithm
to "reconstruct" a smooth k-dimensional
manifold M embedded in an Euclidean
space R^d from a "sufficiently dense" point sample
from the manifold. The algorithm outputs a
simplicial manifold that is homeomorphic and
geometrically close to M. The running time is O(nlogn)
where n is the number of points in the sample (the
multiplicative constant depends exponentially on the
dimension though). |
|
|
Delaunay
Triangulations Approximate
Anchor Hulls
T. K. Dey, Joachim Giesen
and Samrat Goswami. Comput. Geom. Theory Applications,
vol. 36 (2006), 131--143. (prelim. version in
(SODA 2005), 1028-1037).
Recent results establish
that a subset of the Voronoi diagram
of a point set that is sampled from a smooth boundary
of a shape approximates the medial axis.
The corresponding question for the dual Delaunay
triangulation is not addressed in the literature.
We show that, for two dimensional shapes, the Delaunay
triangulation approximates a specific structure
which we call anchor hulls. As
an application we demonstrate that our approximating
result is useful for the problem of shape matching.
|
|
|
Quality
meshing for polyhedra with small angles
S.-W. Cheng, T. K. Dey,
E. Ramos and T. Ray. International J. Comput.
Geom. & Applications, Vol. 15, No. 4 (2005),
421--461. Prelim. version in (SOCG
2004).
Extended
version
QualMesh
Software
We present an algorithm
to compute a Delaunay mesh conforming
to a polyhedron possibly with small input angles.
The radius-edge ratio of most output tetrahedra
are bounded by a constant, except possibly those
that are provably close to small angles. Further, the
mesh is graded, that is, edge lengths are at least
a constant fraction of the local feature sizes at
the edge endpoints. Unlike a previous algorithm, this
algorithm is simple to implement as it avoids computing
local feature sizes and protective zones explicitly. Our
experimental results confirm our claims and show that
few skinny tetrahedra remain.
|
|
|
Sampling
and meshing a surface with guaranteed topology
and geometry
S.-W. Cheng, T. K. Dey,
E. Ramos and T. Ray.Proc. 20th Sympos.
Comput. Geom. (SOCG 2004), 280--289
.
Extended
version,
in SIAM Journal Computing, Vol. 37 (2007), 1199--1227.
This paper presents
an algorithm for sampling and triangulating
a smooth surface in R3 where
the triangulation is homeomorphic to the
surface. The only assumption we make is that the
input surface representation is amenable
to certain types of computations, namely computations
of the intersection points of a line with the surface,
computations of the critical points of some height
functions defined on the surface and its restriction
to a plane, and computations of some silhouette points.
The algorithm ensures bounded aspect ratio, size optimality,
and smoothness of the output triangulation. Unlike
previous algorithms, this algorithm does not need
to compute the local feature size for generating the sample
points which was a major bottleneck. Experiments show
the usefulness of the algorithm in remeshing and meshing
CAD surfaces that are piecewise smooth.
|
|
|
Provable
surface reconstruction from
noisy samples
T. K. Dey and S. Goswami. Computationa
Geometry Theory & Applications, vol. 35, 2006,
124--141. Prelim. version in (SOCG 2004).
RobustCocone
software
We present an algorithm
for surface reconstruction in presence
of noise. We show that, under a reasonable noise
model, the algorithm has theoretical guarantees.
Actual performance of the algorithm is illustrated
by our experimental results.
|
|
|
Approximating
the Medial Axis from
the Voronoi Diagram with a Convergence
Guarantee
T. K. Dey and W. Zhao.
Algorithmica, vol. 38,
2003, 179--200.
Medial Software
The medial axis of a
surface in 3D is the closure of all points that
have two or more closest points on the surface.
It is an essential geometric structure in
a number of applications involving 3D geometric
shapes. Since exact computation of the medial axis
is difficult in general, efforts continue to improve
their approximations. Voronoi diagrams turn out to be
useful for this approximation. Although it is known
that Voronoi vertices for a sample of points from a
curve in 2D approximate its medial axis, similar result
does not hold in 3D. Recently, it has been discovered
that only a subset of Voronoi vertices converge to the
medial axis as sample density approaches infinity. However,
most applications need a non-discrete approximation as
opposed to a discrete one. To date no known algorithm can
compute this approximation straight from the Voronoi
diagram with a guarantee of convergence.We present
such an algorithm and its convergence analysis in this
paper. One salient feature of the algorithm is that it is
scale and density independent. Experimental results corroborate
our theoretical claims.
|
|
|
Hierarchy
of surface models
and irreducible triangulation
S.-W. Cheng, T. K. Dey
and S.-H. Poon.Computational Geometry
: Theory & Applications, Vol. 27, No. 2 (2004),
135--150
Given a triangulated
closed surface, the problem of constructing
a hierarchy of surface models of decreasing
level of detail has attracted much attention
in computer graphics. A hierarchy provides
a view-dependent refinement and facilitates the
computation of parameterization. For a triangulated
closed surface of n vertices and genus g, we prove that
there is a constant c>0 such that if n > c g, a greedy
strategy can identify \Theta(n) topology-preserving edge
contractions that do not interfere with each other. Further,
each of them affects only a constant number of triangles.
Repeatedly identifying and contracting such edges
produces a topology-preserving hierarchy of O(n+g^2) size
and O(logn +g) depth. Although several implementations
exist for constructing hierarchies, our work is
the first to show that a greedy algorithm can efficiently
compute a hierarchy of provably small size and low depth.
When no contractible edge exists, the triangulation is irreducible.
Nakamoto and Ota showed that any irreducible triangulation
of an orientable 2-manifold has at most max{342g-72,
4} vertices. Uisng our proof techniques we obtain a new
bound of mx{240g,4}. |
|
|
Shape
segmentation and matching with flow discretization
T. K. Dey, J. Giesen
and S. Goswami. Proc. Workshop Algorithms
Data Strucutres (WADS 03), LNCS
2748, F. Dehne, J.-R. Sack, M. Smid Eds., 25--36
Extended
version
Segmatch
Software
Geometric shapes
are identified with their features. For computational
purposes a concrete mathematical definition
of features is required. In this paper
we use a topological approach, namely dynamical
systems, to define features of shapes. To exploit
this definition algorithmically we assume
that a point sample of the shape is given as input
from which features of the shape have to be
approximated. We translate our definition
of features to the discrete domain while mimicking
the set-up developed for the continuous shapes.
The outcome of this approach is a clean mathematical
definition of features that are efficiently computable
with combinatorial algorithms. Experimental results
show that our algorithms segment shapes in two and
three dimensions into so-called features quite effectively.
Further, we develop a shape matching algorithm that
takes advantage of our robust feature segmentation
step. Performance of this algorithm is exhibited with
experimental results.
Also see the following
paper:
Shape
segmentation and
matching from noisy point clouds
T. K. Dey, J. Giesen
and S. Goswami. Proc. Eurographics Sympos.
Point-Based Graphics (2004), Marc Alexa
and S. Rusinkiewicz (eds) (2004), 193--199.
|
|
|
Quality
meshing with weighted
Delaunay refinement
S.-W. Cheng and T. K.
Dey.SIAM J. Computing, Vol. 33 (2003),
69--93 Preliminary version
in (SODA 2002).
Delaunay meshes with
bounded circumradius to shorten edge length
ratio have been propsed in the past for quality
meshing. The only poor quality tetrahedra
called slivers
that can occur in such a mesh can be eliminated
by the sliver exudation method.
This method has been shown to work for periodic
point sets, but not with boundaries. Recently a randomized
point-placement strategy has been proposed to
remove slivers while conforming to a given boundary.
In this paper we present a deterministic algorithm
for generating a weighted Delaunay mesh which respects
the input boundary and has no poor quality tetrahedron
including slivers. As in previous work, we assume that
no input angle is acute. This success is achieved
by combining the weight pumping method for sliver exudation
and the Delaunay refinement method for boundary conformation.
|
|
|
Shape
dimension and approximation
from samples
T. K. Dey, J. Giesen,
S. Goswami and W. Zhao. Discrete
& Comput. Geom., vol 29, 419--434 (2003)
Prelim. version in (SODA
2002).
There are many scientific
and engineering applications where
an automatic detection of shape dimension from
sample data is necessary. Topological dimensions
of shapes constitute an important global
feature of them. We present a Voronoi based dimension
detection algorithm that assigns a dimension
to a sample point which is the topological dimension
of the manifold it belongs to. Based on this dimension
detection, we also present an algorithm to approximate
shapes of arbitrary dimension from their samples.
Our empirical results with data sets in three dimensions
support our theory. |
|
|
A
simple algorithm
for homeomorphic surface reconstruction
N. Amenta, S. Choi,
T. K. Dey and N. Leekha. Intl.
Journal on Computational Geometry & Applications,
vol. 12, (2002), 125--141. Prelim. version in (SOCG 2000).
The problem of computing
a piecewise linear approximation to a
surface from a set of sample points is improtant
in solid modeling, computer graphics and
computer vision. A recent algorithm using
the Voronoi diagram of the sample points gave a guarantee
on the distance of the output surface from
the original sampled surface assuming that the
sample was sufficiently dense. We give a similar
algorithm, simplifying the computation and the proof
of the geometric guarantee. In addition, we guarantee
that our output surface is homeomorphic to the original
surface; to our knowledge this is the first such topological
guarantee for this problem.
Also see the following
paper:
Tight
Cocone : A water-tight
surface reconstructor
T.
K. Dey and S. Goswami. J. Computing Inform.
Sci. Engin., vol. 30, (2003), 302--307.
Cocone Software
|
|
|
Dynamic
skin triangulation
H-L. Cheng, T. K. Dey,
H. Edelsbrunner and J. Sullivan.
Discrete Comput. Geom., vol. 25,
(2001), 525--568 Prelim. version in (SODA 2001).
This paper describes
an algorithm for maintaining an approximating
triangulation of a deforming surface
in R 3 . The surface is the envelope of
an infinite family of spheres defined and controlled by
a finite collection of weighted points. The triangulation
adapts dynamically to changing shape, curvature,
and topology of the surface. |
|
|
Sliver
exudation
S.-W. Cheng, T. K. Dey,
H. Edelsbrunner, M. A. Facello and S.-H.
Teng.J. ACM, Vol. 47, (2000), 883--904
Prelim. version in (SOCG 1999).
A sliver is a tetrahedron
whose four vertices lie close to a
plane and whose orthogonal projection to that
plane is a convex quadrilateral with
no short edge. Slivers are notoriously common
in 3-dimensional Delaunay triangulations even
for well-spaced point sets. We show that if the
Delaunay triangulation has the ratio property
then there is an assignment of weights so
the weighted Delaunay triangulation contains no
slivers. We also give an algorithm to compute such
a weight assignment. |
|
|
A
simple provable algorithm
for curve reconstruction
T. K. Dey and P. Kumar.Proc.
10th. ACM-SIAM Symposium on Discrete
Algorithms (SODA '99) , 1999,
893--894
We present an algorithm
that provably reconstructs a curve in
the framework introduced by Amenta, Bern and Eppstein.
The highlights of the algorithm are:
(i) it is simple, (ii) it requires a sampling
density better than previously known, (iii) it
can be adapted for curve reconstruction in higher
dimensions straightforwardly.
|
|
|
Topology
preserving edge contraction
T. K. Dey, H. Edelsbrunner,
S. Guha and D. Nekhayev.Publications
de l' Institut Mathematique (Beograd), Vol.
60 (80), 23--45, 1999
We study edge contractions
in simplicial complexes and local
conditions under which they preserve the topological
type. The conditions are based on a
generalized notion of boundary, which lends itself
to defining a nested hierarchy of triangulable spaces
measuring the distance to being a manifold.
|
|
|
Transforming
curves on surfaces
T. K. Dey and S. Guha.Journal
of Computer and System Sciences,
vol. 58, 1999, 297--325. Preliminary version
in IEEE (FOCS 1995), 266-274
We describe an optimal
algorithm to decide if one closed curve
on a triangulated 2-manifold can be continuously
transformed to another, i.e., if they are homotopic.
Suppose C_1 and C_2 are two closed curves on a surface
M of genus g. Further, suppose T is a triangulation
of M of size n such that C_1 and C_2 are represented as edge-vertex
sequences of lengths k_1 and k_2 in T, respectively.
Then, our algorithm decides if C_1 and C_2 are homotopic
in O(n+k_1+k_2) time and space, provided g \not =
2 if M is orientable, and g \not 3, 4 if M is non-orientable.
This as well implies an optimal algorithm to decide
if a closed curve on a surface can be continuously contracted
to a point. Except for the three low genus cases, our
algorithm completes an investigation into the computational
complexity of two classical problems for surfaces
posed by the mathematician Max Dehn at the beginning of
this century. The novelty of our approach is in the
application of methods from modern combinatorial group
theory.
Reprint available upon
request |
|
|
Improved
bounds for planar
k-sets and related problems
T. K. Dey.Invited
paper in a special issue of Discrete &
Computational Geometry, Vol. 19, No.
3, (1998), 373-382 Prelim. version
in IEEE (FOCS 1997).
We prove an O(nk1/3)
upper bound for planar k-sets.
This is the first considerable improvement
on this bound after its early solutions
approximately twenty seven years ago. Our proof
technique also applies to improve the current
bounds on the combinatorial complexities of k-levels
in arrangements of line segments, k convex polygons
in the union of n lines, parametric minimum spanning
trees and parametric matroids in general.
|
|
|
Extremal
problems for geometric
hypergraphs
T. K. Dey and J. Pach.Discrete
& Computational Geometry, Vol.
19, No. 4, (1998), 473--484. Preliminary version
in ISAAC 96, LNCS 1178, 105-114
A geometric hypergraph
H is a collection of i-dimensional simplices,
called hyperedges or, simply, edges,
induced by some (i + 1)-tuples of a vertex set
V in general position in d-space. The topological
structure of geometric graphs, i.e., the case d =
2; i = 1, has been studied extensively, and it proved
to be instrumental for the solution of a wide range
of problems in combinatorial and computational
geometry. They include the k-set problem, proximity
questions, bounding the number of incidences between
points and lines, designing various efficient graph
drawing algorithms, etc. In this paper, we make an
attempt to generalize some of these tools to higher dimensions.
We will mainly consider extremal problems of the following
type. What is the largest number of edges (i-simplices)
that a geometric hypergraph of n vertices can have without
containing certain forbidden configurations? In particular,
we discuss the special cases when the forbidden configura
tions are k intersecting edges, k pairwise intersecting
edges, k crossing edges, k pairwise crossing edges, k
edges that can be stabbed by an i-flat, etc. Some of our estimates
will be tight. |
|
|
Computational
Topology
T. K. Dey, H. Edelsbrunner
and S. Guha. Advances in Discrere
and Computational Geometry, eds. B. Chazelle,
J. E. Goodman and R. Pollack. Contemporary
Mathematics, AMS, Providence, 1998 .
The authors of this
article believe there is or should be a
research area appropriately referred to as
computational topology. Its agenda includes
the identification and formalization of
topological questions in computer applications
and the study of algorithms for topological
problems. It is hoped this article can contribute
to the creation of a computational branch
of topology with a unifying influence on computing
and computer applications. |
|
|
Visibility
with multiple reflections
B. Aronov, A. Davis,
T. K. Dey, S. P. Pal and D. C. Prasad.Discrete
& Computational Geometry, Vol.
20, No. 61, (1998), 61--78. Preliminary
version in 5th SWAT, 1996,
LNCS 1097, 284-295
We show that the region
lit by a point light source inside a simple
n-gon after at most k reflections off the
boundary has combinatorial complexity O(n2k
), for any k – 1. A lower bound of Ω((n/k θ(1))2k
) is also established which matches the upper
bound for any fixed k. A simple near-optimal algorithm
for computing the illuminated region is presented,
which runs in O(n2k log n) time and O(n2k
) space for k > 1, and in O(n2 log2
n) time and O(n2 ) space for k =
1. |
|
|
Counting
triangle crossings and halving planes
T. K. Dey and H. Edelsbrunner.Invited
paper in a special issue, Discrete
& Computational Geometry, Vol. 12 (1994),
281--289 Prelim. version in SoCG 1995.
Every collection of
t > 2n^2 triangles with a total of n vertices
in R^3 has \Omega(t^4/n^6) crossing pairs.
This implies that one of their edges meets \Omega(t^3/n^6)
of the triangles. From this it follows
that n points in R^3 have only O(n^{8/3}) halving
planes.
Reprint available upon
request |
|
|
