Joseph Mitchell, Stony Brook University

Joseph S. B. Mitchell received a BS (1981, Physics and Applied Mathematics), and an MS (1981, Mathematics) from Carnegie-Mellon University, and Ph.D. (1986, Operations Research) from Stanford University. Mitchell was with Hughes Research Labs (1981-86) and then on the faculty of Cornell University (1986-1991). He now serves as Professor of Applied Mathematics and Statistics and Research Professor of Computer Science at the University at Stony Brook. Mitchell has received various research awards (NSF Presidential Young Investigator, Fulbright Scholar, President's Award for Excellence in Scholarship and Creative Activities) and numerous teaching awards. His primary research area is computational geometry, applied to problems in computer graphics, visualization, air traffic management, manufacturing, and geographic information systems. Mitchell has served for several years on the Computational Geometry Steering Committee, often as Chair. He is on the editorial board of the journal Discrete and Computational Geometry, as well as the Journal of Graph Algorithms and Applications, and is an Editor-in-Chief of the International Journal of Computational Geometry and Applications. He served as the co-chair of the program committee for the 21st ACM Symposium on Computational Geometry (2005).

Title: Geometric Optimization Problems in Computing Inner and Outer Shape Approximations

Abstract:
We study two classes of optimization problems in shape approximation: (1) Finding the ``largest'' subset of a specified type (e.g., convex) within a domain; and (2) Finding the ``smallest'' shape of a specified type (e.g., union of simple convex shapes) that completely covers a given set. Both problems arise naturally in shape approximation, where one desires good inner and outer shape approximations. They are motivated by applications in computer graphics and solid and physical modeling. We study the problems from the point of view of approximation and optimization. For some problems we give provable guarantees on the quality of the solutions and anaylze their efficiency.