USC, Los Angeles, CA, USA
Jin Huang, Xiaohan Shi, Xinguo Liu, Kun Zhou, Li-Yi Wei, Shang-Hua Teng, Hujun Bao, Baining Guo, Heung-Yeung Shum
ACM SIGGRAPH 2006 Papers, 2006 – GRAPH
In this paper we present a general framework for performing constrained mesh deformation tasks with gradient domain techniques. We present a gradient domain technique that works well with a wide variety of linear and nonlinear constraints. The ...
Jin Huang, Xiaohan Shi, Xinguo Liu, Kun Zhou, Li-Yi Wei, Shang-Hua Teng, Hujun Bao, Baining Guo, Heung-Yeung Shum
ACM Transactions on Graphics, vol. 25,no. 3,2006 – TOG
In this paper we present a general framework for performing constrained mesh deformation tasks with gradient domain techniques. We present a gradient domain technique that works well with a wide variety of linear and nonlinear constraints. The ...
Daniel A. Spielman, Shang-Hua Teng
Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004 – STOC
We present algorithms for solving symmetric, diagonally-dominant linear systems to accuracy ε in time linear in their number of non-zeros and log (κf (A) ε), where κf (A) is the condition number of the matrix defining the linear system. Our ...
Siddhartha Chatterjee, John R. Gilbert, Robert Schreiber, Shang-Hua Teng
20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, 1993 – POPL
Data-parallel languages like Fortran 90 express parallelism in the form of operations on data aggregates such as arrays. Misalignment of the operands of an array operation can reduce program performance on a distributed-memory parallel machine by ...
Daniel A. Spielman, Shang-Hua Teng
Journal of the ACM, vol. 51,no. 3,2004 – JACM
We introduce the smoothed analysis of algorithms, which continuously interpolates between the worst-case and average-case analyses of algorithms. In smoothed analysis, we measure the maximum over inputs of the expected performance of an algorithm ...
Daniel A. Spielman, Shang-Hua Teng
FOCS 1996: Burlington, 1996 – FOCS
Spectral partitioning methods use the Fiedler vector-the eigenvector of the second-smallest eigenvalue of the Laplacian matrix-to find a small separator of a graph. These methods are important components of many scientific numerical algorithms and ...
Siu-Wing Cheng, Tamal K. Dey, Herbert Edelsbrunner, Michael A. Facello, Shang-Hua Teng
Journal of the ACM, vol. 47,no. 5,2000 – JACM
A silver is a tetrahedon whose four vertices lie close to a plane and whose orthogonal projection to that plane is a convex quadrilateral with no short edge. Silvers are notoriously common in 3-dimensional Delaunay triangulations even for ...
Gary L. Miller, Dafna Talmor, Shang-Hua Teng, Noel Walkington
Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 1995 – STOC
We present new geometrical and numerical analysis structure theorems for the Delaunay diagram of point sets in R~ for a fixed d where the point sets arise naturally in numerical methods. In particular, we show that if the largest ratio of the ...
Gary L. Miller, Shang-Hua Teng, William P. Thurston, Stephen A. Vavasis
Journal of the ACM, vol. 44,no. 1,1997 – JACM
A collection of n balls in d dimensions forms a k-ply system if no point in the space is covered by more than k balls. We show that for every k-ply system &Ggr;, there is a sphere S that intersects at most O(k1/dn1−1/d) balls of &Ggr; and ...
Daniel A. Spielman, Shang-Hua Teng
twelfth annual symposium on Computational geometry, 1996 – SoCG
We demonstrate that the geometric separator algorithm of Miller, Teng, Thurston, and Vavasis finds a 3/4-separator of size 1.84+ for every n node planar graph. Our bound is derived from an analysis of disk packings on the sphere