Optimal Boundary Triangulations of an Interpolating Ruled Surface

Speaker:	Dr. Kai Tang
		Assistant Professor
		Department of Mechanical Engineering
		HKUST

Title:		"Optimal Boundary Triangulations of an Interpolating
		 Ruled Surface"

Date:		Monday, 3 October 2005

Time:		4:00pm - 5:00pm

Venue:		Lecture Theatre F (near lift nos. 25/26)
		HKUST

Abstract:

We investigate how to define a triangulated ruled surface interpolating
two polygonal directrices that will meet a variety of optimization
objectives which originate from many CAD/CAM and geometric modeling
applications. This optimal triangulation problem is formulated as a
combinatorial search problem whose search space however has the size
tightly factorial to the numbers of points on the two directrices. To
tackle this bound, we introduce a novel computational tool called
multi-layer directed graph and establish an equivalence between the
optimal triangulation and the single-source shortest path problem on the
graph. Well known graph search algorithms such as the Dijkstra's are then
employed to solve the single-source shortest path problem, which
effectively solves the optimal triangulation problem in O(mn) time, where
n and m are the numbers of vertices on the two directrices respectively.
Numerous experimental examples are provided to demonstrate the usefulness
of the proposed optimal triangulation problem in a variety of engineering
applications.


***********************
Biography:

Dr. Kai Tang received his BEng in Mechanical Engineering from Nanjing
Institute of Technology in China in 1982. Afterward, among the first
selected by China's Educational Ministry, he went to The University of
Michigan in 1984, enrolling in the Department of Electrical Engineering
and Computer Science, where he received MSc in 1986 and PhD in 1990, both
in Computer Engineering. From 1991 to 2001 for 10 years, he worked as a
software specialist in software industry, mostly in the area of
Computer-Aided Design and Manufacturing software development. He also for
a short period of one year worked as the chief engineer in a start-up
company focusing on voice recognition technology. In June 2001, he "went
back" to school and joined the faculty of the Department of Mechanical
Engineering at Hong Kong University of Science and Technology.

Dr. Tang's research interests are broad, but mostly focusing on designing
practical and efficient algorithms for solving numerical and geometrical
problems in the real world. His past work had a concentration on problems
stemming from mechanical design/manufacturing; recently he has grown
interest in modeling of "soft material" objects such as garment and shoe.