Colloquia

Computing Inner and Outer Shape Approximations

Joseph Mitchell
Department of Applied Mathematics and Statistics
SUNY at Stony Brook

Thursday, February 2, 2006
JEC 3117 - 4:00 p.m. to 5:00 p.m.
Refreshments at 3:30 p.m.

Abstract:

We study two classes of optimization problems in shape approximation:

(1) Finding the "largest" subset of a specified type within a polygon ; and (2) Finding the "smallest" pair of boxes that cover a given set of points or polyhedra. Both problems arise from an attempt to construct good inner and outer shape approximations and are motivated by applications in computer graphics.

(1) In polygons we seek to compute the "largest" subset of a prescribed type, e.g., a longest line segment ("stick") or a maximum-area triangle or convex body ("potato"). Exact polynomial-time algorithms are known for some of these problems, but their time bounds are high (e.g., for the longest stick, and for the largest convex polygon in a simple n-gon). We devise efficient approximation algorithms for these problems. In particular, we give near-linear time algorithms for a -approximation of the biggest stick, an -approximation of the maximum-area convex body, and a -approximation of the maximum-area fat triangle or rectangle. In addition, we give efficient methods for computing large ellipses inside a polygon (whose vertices are a dense sampling of closed smooth curve). Our algorithms include both deterministic and randomized methods, one of which has been implemented (for computing large area ellipses in a well sampled closed smooth curve).

(This is joint work with Olaf Hall-Holt, Matthew Katz, Piyush Kumar, and Arik Sityon.)

(2) We study the problem of covering a set of points or polyhedra in with two axis-aligned boxes in order to minimize a function of the measures of the two boxes, such as the sum or the maximum of their volumes. This 2-box cover problem arises naturally in the construction of bounding volume hierarchies, as well as in shape approximation and clustering. Existing algorithms solve the min-max version of the exact problem in quadratic time. Our results are more general, addressing min-max, min-sum and other versions. Our results give the first approximation schemes for the problem, which run in nearly linear time, as well as some new exact algorithms. We give -approximation algorithms for minimizing the maximum or sum of volumes (or surface areas, diameters, widths, or girths) of the two boxes in . We investigate also the problem of computing balanced coverings, in which each box covers at least a fraction of the input objects, and we discuss the application to constructing provably-good bounding volume hierarchies of polyhedra. We also generalize our results to higher dimensions.

(This is joint work with Esther Arkin and Gill Barequet.)

Bio:

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).

Hosted by: Daniel Freedman (x4785)

For more information:

Last updated: January 16, 2006