chucko@saturn.ucsc.edu (Chuck Stein) (06/11/88)
The University of California
Eighteenth Annual
INSTITUTE IN COMPUTER SCIENCE
presents courses in:
* Scientific Visualization * Fault Tolerant Computing
* Parallel Computation * Image Engineering
* Data Compression * Machine Learning
at
Techmart, Santa Clara
and
on campus in Santa Cruz
Following is a course description for:
-------------------------------------------------------------------------
Hierarchical Data Structures for Computer Graphics,
Image Processing, and Geographic Information Systems
September 14-16
Instructor: HANAN SAMET
X418 Computer Engineering (2)
The objective of this seminar is to introduce and understand the use of
the current and emerging developments in hierarchical data structures
for multi-dimensional data applications in computer graphics, image
processing, and geographic information systems. Attendees will gain
an appreciation for the simplicity of these methods, the differences
between them, and how to evaluate their appropriateness for their
applications.
Who Should Attend
This course is designed to introduce a wide range of professionals to
the use of hierarchical data structures in the handling of spatial data.
Engineers, mathematicians, analysts, programmers, cartographers, and
technical managers will all benefit by learning about how to use these
new methods in applications in areas that include computer graphics,
image processing, solid modeling, and geographic information systems.
Description
This three day seminar provides a comprehensive introduction to the
use of hierarchical data structures for handling multidimensional data.
It consists of three parts. In the first part, hierarchical data structures
such as the quadtree are defined and motivated in the context of
representing two-dimensional region data. You will be shown the
basics of manipulating a quadtree and how it is interchangeable with
more traditional region representations. Operations that find use in
computer graphics applications such as the computation of geometric
properties, overlay translation, and image approximation are
discussed in greater detail. Hierarchical representations are
compared to other related data structures by examining their time and
space requirements.
The second part stresses hierarchical representations of points, lines,
rectangles, and three-dimensional data. The representation of point
data is important in applications that require searching and finds use
in dealing with large off-line databases found in geographic
information systems, computer graphics, image processing, and
numerous other applications that involve spatial databases. For line
data the representations are evaluated in the context of preserving
accuracy. For rectangle data the evaluation is in the context of
searching and set operations. Rectangle data arises in the
approximation of data of a geographic nature and in VLSI applications.
Uses of the octree (a quadtree in three dimensions) are also
reviewed.
The third part examines an existing geographic information system
which employs hierarchical data structures to represent point, line, and
region data in a consistent manner.
Prerequisite: A familiarity with computer terminology and some
programming experience.
Seminar Outline
Part I: Two-Dimensional Region Data
l. Introduction
*Sample application
*Historical background
*Why use quadtrees instead of hexagons or other tessellations
2. Alternative Quadtree Implementations
*Explicit pointers
*Linear quadtrees
*Tree traversals
*Bintrees
3. Manipulating Quadtrees Using Neighbor Finding Methods
*Alternatives
*Horizontal and vertical neighbors
*Diagonal neighbors
* Ropes and nets
*Expected execution costs
4. Interchangeability with Other Representations
*Building quadtrees from binary arrays
*Building quadtrees from boundary codes
*Converting a quadtree to a boundary code
*Building quadtrees from rasters or run representations
*Converting a quadtree to a run representation
5. Geometric Operations
*Perimeter
*Connected component labeling
*Euler number or Genus
*Linear quadtree methods
6. Transformations and Computer Graphics
*Set operations
*Areas, centroids, moments
*Translation
*Rotation
*Windowing
7. Quadtree Approximation Methods
*Pyramid-based
*Compression
*Transmission
*Successive Approximation
8. Skeletons
*Distance
*Quadtree skeletons
*Quadtree medial axis transforms (QMAT)
*Construction of a quadtree from a QMAT
9. Space Requirements
*Storage
*Optimal quadtrees
Part II: Points, Lines, Rectangles, and Volumes
l. Multidimensional Point Data
*Non-hierarchical representations
*Grid method
*Point quadtrees
*K-d trees
*MX quadtrees
*PR quadtrees
*Bit interleaving
*EXCELL
*Grid File
*Range searching
2. Line Data
*Boundary codes
*Vectors
*Strip trees
*Binary Searchable Polygonal Representation
*Edge quadtrees
*Line quadtrees
*PM quadtrees
3. Rectangle Data
*Plane-sweep methods
*Quad-CIF trees
*Grid File
*R-trees
4. Three-Dimensional Data
*Arrays
*Boundary methods
*Constructive solid geometry
*Octrees
Part III: Quadtree-Based Geographic Information Systems
l. Example System
*Experimental results
*Query language
Text: Notes and copies of the instructor's transparencies will be
provided. Participants will be provided with the survey
"The Quadtree and Related Hierarchical Data Structures" by
H. Samet.
Instructor: HANAN SAMET is a Professor of Computer Science at the
University of Maryland, College Park.
Fee: Credit, $875 (EDP C6031)
Dates: Three Days, Wed.-Fri., Sept. 14-16, 9 a.m.-5 p.m.
Place: Techmart, 5201 Great America Pkwy., Santa Clara
-----------------------------------------------------------------------
RESERVATIONS:
Enrollment in these courses is limited. If you wish to attend a course
and have not pre-registered, please call (408) 429-4535 to insure that
space is still available and to reserve a place.
DISCOUNTS:
Corporate, faculty, IEEE member, and graduate student discounts and
fellowships are available. Please call Karin Poklen at (408) 429-4535
for more information.
COORDINATOR:
Ronald L. Smith, Institute in Computer Science, (408) 429-2386.
FOR FURTHER INFORMATION:
Please write Institute in Computer Science, University of California
Extension, Santa Cruz, CA 95064, or phone Karin Poklen at (408) 429-
4535. You may also enroll by phone by calling (408) 429-4535. A
packet of information on transportation and accommodations will be sent
to you upon receipt of your enrollment.