Forced Orientation of Graphs [PDF]

With Babak Farzad, Amin Saberi, Ebad S. Mahmoodian, and Mohammad Mahdian

Bulletin of Iranian Mathematical Society, Vol 32, No 1, 2006.

The concept of forced orientation of graphs was first introduced by G. Chartrand et al. in 1994. If, for a given assignment of directions to a subset S of the edges of a graph G, there exists an orientation of E(G) - S, such that the resulting graph is strongly connected, then that given assignment is said to be extendible to a strong orientation of G. A forcing set for a strong orientation D of G is a subset of edges of G, for which the assignment of orientations from D, can uniquely be extended to all edges, reproducing D. We denote the size of the smallest forcing set for a strong orientation D of G by fD(G).  The main result of this paper shows that all minimal forcing sets for any particular strong orientation D of G have the same cardinality. We also characterize those graphs G that have strong orientations D, for which fD(G) is equal to the trivial maximum of |E(G)|.

How Fast is the k-Means method? [PDF]

With Sariel Har-Peled

ACM-SIAM Symposium on Discrete Mathematics (SODA), 2005

Full version in Algorithmica (2005) 41:185-202 [PDF]

In this paper, we present polynomial upper and lower bounds on the number of iterations performed by the k-means method (a.k.a. Lloyd's method). k-means method is a widely popular heuristic method for k-means clustering. The popularity of the method is due to its simplicity and ease of implementation. Our upper bounds on the number of rounds of the k-means are polynomial in the number of points, number of clusters, and the spread of the point set. We also present a lower bound, showing that in the worst case the k-means heuristic needs to perform Ω(n) iterations, for n points on the real line and two centers. Surprisingly, the spread of the point set in this construction is polynomial. This is the first construction showing that the k-means heuristic requires more than a polylogarithmic number of iterations. Furthermore, we present two alternative algorithms, with guaranteed performance, which are simple variants of the k-means method. Results of our experimental studies on these algorithms are also presented.

Critical Points of the Distance to an epsilon-Sampling of a Surface and Flow-Complex-Based Surface Reconstruction [PDF]
With Tamal K. Dey, Joachim Giesen, and Edgar Ramos
Symposium on Computational Geometry (SoCG), 2005
Full version is due to appear in the SoCG’05 special issue of International Journal of Computational Geometry and Applications (IJCGA).

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 cases, the distance function induced by the surface is approximated by a discrete distance function induced by a discrete sample of the surface. The critical points of the distance function determine the topology of the set inducing the function. However, no earlier theoretical result has linked the critical points of the distance to a sampling of geometric structures to their topological properties. We provide this link by showing that the critical points of the distance function induced by a discrete sample of a surface either lie very close to the surface or near its medial axis and this closeness is quantified with the sampling density. Based on this result, we provide a new flow-complex-based surface reconstruction algorithm that, given a tight ε-sampling of a surface, approximates the surface geometrically, both in Hausdorff distance and normals, and captures its topology.

Medial Axis Approximation and Unstable Flow Complex [PDF]

With Edgar A. Ramos, and Joachim Giesen

Symposium on Computational Geometry (SoCG), 2006.

Full version is due to appear in the SoCG’06 special issue of International Journal of Computational Geometry and Applications (IJCGA).

The medial axis of a shape is known to carry a lot of information about it. In particular a recent result of Lieutier establishes that every bounded open subset of Rn has the same homotopy type as its medial axis. In this paper we provide an algorithm that, given a sufficiently dense but not necessarily uniform sample from the surface of a shape with smooth boundary, computes a core for its medial axis approximation, in form of a piecewise linear cell complex, that captures the topology of the medial axis of the shape. We also provide a natural method to freely augment this core in order to enhance it geometrically all the while maintaining its topological guarantees. The definition of the core and its extension method are based on the steepest ascent flow induced by the distance function to the sample. We also provide a geometric guarantee on the closeness of the core and the actual medial axis.

Geometric and Topological Guarantees for the WRAP Reconstruction Algorithm [PDF]

With Edgar A. Ramos

ACM-SIAM Symposium on Discrete Mathematics (SODA), 2007.

Full version (in revision) [PDF]

We describe a variant of Edelsbrunner's WRAP algorithm for surface reconstruction, for which we can prove geometric and topological guarantees within the ε-sampling model. The WRAP algorithm is based on ideas from Morse theory applied to the flow map induced by certain distance function. The variant is made possible by a previous result on the "separation'' of critical points for a related distance function that directly applies in this case. Though the variant is easily proposed, in order to prove the quality guarantees for the output, we need to closely investigate the geometric properties of the flow map.

Untangling Triangulations through Local Explorations [PDF]

With Pankaj K. Agarwal and Hai Yu

Symposium on Computational Geometry (SoCG), 2008 (to appear).

In many applications it is often desirable to maintain a valid mesh within a certain domain that deforms over time. During a period for which the underlying mesh topology remains unchanged, the deformation moves the vertices of the mesh and thus potentially turns a mesh invalid, or as we call it, tangled. We introduce the notion of locally removable region, which is a certain tangled area in the mesh that allows for local removal and re-meshing. We present an algorithm that is able to quickly compute, through local explorations, a minimal locally removable region containing a seed tangled region in the invalid mesh. By re-meshing within this area, the seed tangled region can then be removed from the mesh without introducing any new tangled region. The algorithm is output-sensitive in the sense that it never explores outside the output region.Our algorithm exploits several novel insights into the structure of the tangled mesh, which may be of independent interest in contexts beyond mesh untangling.

I/O-Efficient Algorithms for Computing Contour Lines on a Terrain [PDF]

With Lars Arge, Pankaj K. Agarwal and Thomas Mølhave

Symposium on Computational Geometry (SoCG), 2008 (to appear).

A terrain ∑ is the graph of a bivariate function. We assume that ∑ is represented as a triangulated surface with

n vertices. A contour (or contour line) of ∑ is a connected component of a level set of ∑. Generically,  each contour is a closed polygonal curve; at “critical”' levels these curves may touch each other. We present I/O-efficient algorithms for the following two problems related to computing contours of ∑:

Given two real parameters h and d > 0, we present an I/O-optimal algorithm that report all contours of ∑ at heights h + kd, for every positive integer k, using O(Sort(N)+T/B) I/Os, where T is the total number edges in the output contours, B is the “block size,” and Sort(N) is the number of I/Os needed to sort N elements. The algorithm uses O(N/B) disk blocks. Each contour is generated individually with its composing segments sorted in clockwise order. Moreover, our algorithm generates information on how the contours are nested.

We can preprocess ∑, using O(Sort(N)) I/Os, into a linear-size data structure so that all contours  at a given height can be reported using O(logB N + T/B) I/Os, where T is the output size.  Each contour is generated individually with its composing segments sorted in clockwise order.

Surface and Medial Axis Topology Through Distance Flows Induced by Discrete Samples [PDF]

Supervised by Edgar A. Ramos

PhD Thesis

Department of Computer Science, University of Illinois at Urbana-Champaign, 2006.

On the Number of Steps of Lloyd’s k-Means Method [PDF]

Supervised by Sariel Har-Peled

Masters Thesis

Department of Computer Science, University of Illinois at Urbana-Champaign, 2004.

The lambda-Medial Axis [PDF]

Talk describing the work of Frédéric Chazal and André Lieutier on lambda-Medial Axis in UIUC computer science theory seminar.

Undirected st-Connectivity in Log-Space [PDF]

Talk describing the result of Oded Reingold in UIUC computer science theory seminar.

A Core for Medial Axis Approximation [PDF]

SoCG’06 talk for the paper Medial Axis Approximation and Unstable Flow Complex.

Analysis Edelsbrunner’s WRAP Under Sampling Assumptions [PDF]

SODA’07 talk for the paper Geometric and Topological Guarantees for the WRAP Reconstruction Algorithm.

Surface and Medial Axis Topology Through Distance Flows Induced by Discrete Samples [PDF]

PhD Defense presentation slides.

Manifold Reconstruction As A Subcomplex of the Flow Complex

Short Abstract [PDF]

EWCG’08 (to appear).

It is known that the critical points of the distance function induced by a dense sample P of a submanifold ∑ of Rn are distributed into two groups, one lying close to ∑ itself, called the shallow, and other close to medial axis of ∑, called deep critical points. We prove that under (uniform) sampling assumption, the union of stable manifolds of the shallow critical points have the same homotopy type as ∑ itself and the union of the stable manifolds of the deep critical points have the homotopy type of the complement of ∑. The separation of critical points under uniform sampling entails a separation in terms of distance of critical points to the inducing sample. This means that if the sample is a dense enough sample for more than one submanifold of Rn, all such submanifolds are reconstructed as unions of stable manifolds of shallow critical points, in a filtration of the flow complex based on the distance of critical points to sample.