Computing Inner and Outer Shape Approximations
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.
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
(This is joint work with Esther Arkin and Gill Barequet.)
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