Title: On Some Geometric Optimization Problems with Applications 
       in Manufacturing, Graph Visualization and Structural Biology.
Speaker: Jun Luo
University of Texas at Dallas

Date: Friday,  Jan 6, 2006
Time 11-12 Venue: Room 3464, HKUST   


Abstract 
I will present approximation algorithms for cutting out a polygon P 
with n vertices from another convex polygon Q with m vertices by 
line cuts and ray cuts. For line cuts we require both P and Q are 
convex while for ray cuts we require Q is convex and P is ray cuttable. 
Our results answer a number of open problems and are either the first 
solutions or  significantly improve over previously known solutions. For 
the line cutting version, we prove a key property that leads to a simple, 
constant factor approximation algorithm. For the ray cutting version, we 
prove it is possible to compute in almost linear time a cutting sequence 
that is an O(log^2 n)-factor approximation of an optimal cutting sequence. 
No algorithms were previously known for the ray cutting version.
Then I will briefly talk about two other problems: (1) Stabbing Balls 
and Simplifying Proteins. (2) Proximity Problems on Line Segments 
Spanned by Points.