[comp.software-eng] Short Course: Hierarchical Data Structures for Computer Graphics...

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.