Digital image compression
and transmission is a problem that (with the growth of the world wide web)
is rapidly growing in prominence, and
may be a fertile source of links between geometry and
One example is a recent note in the
11th ACM Symp. Comp. Geom., in Schwarz et al. describe a fast algorithm
for finding the minimum area parallelogram enclosing a given polygon,
motivated by a problem in signal processing of compressing
image data via "rational decimation systems".
two-dimensional filter banks based on geometric decompositions of the
W. Chen and E. Lee, Berkeley.
pyramids and trees, quadtree data structures for
binary tree predictive image coding.
- Level set
methods for following the evolution of interfaces, J. Sethian,
Berkeley. The basic idea is to solve various "advancing front" type problems
such as finding shortest paths around obstacles, by evolving a surface
in one higher dimension that describes the dynamics of the front.
Includes movies and Java applets describing applications to
VLSI design, medical image processing, noise removal from images, and
robot motion planning.
- A Quadtree Structured Video-phone Codec, L. Hanzo and A. Schober,
- Dr. Christian Schwarz's home page at the Max-Planck-Inst. fuer
Informatik includes pointers to longer versions of his papers on
finding minimal enclosing parallelograms and on the application of
this problem to rational decimation systems.
- US Patents
describe video and image coding methods based on quadtrees.
Geometry in Action,
a collection of applications of computational geometry.
from a common source file.