
Surface ReconstructionGiven 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.Related articles:

Medial Axis Point ApproximationThe 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.Related articles:

Bottleneck Steiner Tree ProblemThe bottleneck Steiner tree problem (shortly BST) has been studied with many applications, like VLSI layout, multifacility 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 (BSTFT); 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.Related articles:

Path Coverage ProblemAmong the most fundamental problems in wireless adhoc sensor networks are coverage problems. To measure the bestcase and the worstcase 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.Related articles:

Cloth SimulationCloth 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, multiresolution method to efficiently perform largescale 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.Related articles: