Surface Reconstruction

Given a set of sample points on the surface of an object, the surface reconstruction problem is to compute a surface approximating the original surface. Many applications in CAD, computer graphics, computer vision and mathematical modeling involve the computation of a piecewise linear approximation to a surface from a set of sample points. We proposed surface reconstruction algorithms which have theoretical guarantees.

  • The Power Crust

  • A simple algorithm for homeomorphic surface reconstruction

Medial Axis Point Approximation

The medial axis is a skeletal representation of objects defined by the locus of the maximal balls tangent to the object surface at two or more places. However, exact computation of the medial axis of a 3D object is expensive even for simple polyhedra. Thus, a lot of research focused on efficient medial axis approximation for various types of input models. Among them, a popular method is to sample the surface of the 3D object and use a subset of the Voronoi diagram of the samples to approximate the medial axis. For a set of sample points with surface normals, we proposed a simple and efficient algorithm to compute a set of medial axis points using GPU.

  • The power crust, unions of balls, and the medial axis transform

  • Medial Axis Point Approximation using Nearest neighbors

Path Coverage Problem

Among the most fundamental problems in wireless ad-hoc sensor networks are coverage problems. To measure the best-case and the worst-case coverage of a given network, maximal support paths and maximal breach paths have been proposed in previous works. Previous results, however, considered only a single source and destination pair and thus would not provide a global look at the given sensor network. We introduced an arbitrary path coverage which considers all possible paths crossing the sensor field and showed the problem is closely related to the bottleneck Steiner tree problem. By this observation, we provided the additional deployment algorithm that surprisingly improves the path coverage.

  • Best and Worst-Case Coverage Problems for Arbitrary Paths in Wireless Sensor Networks

Bottleneck Steiner Tree Problem

The bottleneck Steiner tree problem (shortly BST) has been studied with many applications, like VLSI layout, multi-facility location, and wireless communication network design. Also, there has been effort on devising an exact algorithm for finding the locations of k Steiner points. Many researchers considered the variation of BST where a topology T of Steiner trees is fixed, called the bottleneck Steiner tree with fixed topology (BST-FT); the resulting Steiner tree should have the same topology as a given tree T. In this research, we presented the first exact algorithm for the BST problem.

  • Exact Algorithms for the Bottleneck Steiner Tree Problem

  • On Exact Solutions to the Euclidean Bottleneck Steiner Tree Problem

Cloth Simulation

Cloth simulation has been extensively researched in order to achieve realistic simulations of various fabrics. Since most fabrics are very flexible and do not have elasticity, the meshes resulted from realistic cloth simulations can have highly detailed features such as wrinkles. We propose a novel, multi-resolution method to efficiently perform large-scale cloth simulation. By simplifying dynamically smooth regions of the dress mesh, our method achieves 9 times performance improvement by reducing 73.8% of the vertices of the original mesh.

  • Multi-resolutional Cloth Simulation