Meeting 4: Adjacency Data Structures

Administrative stuff:

Exercise 1: please put README, gvis in your ~/Public
directory on athena, make them world readable/executable

Tomorrow, we'll look at some of the executables in class.

We have now covered fundamental geometric objects, such
as points, lines, and halfspaces, and operators for combining
them, deducing sidedness relations, etc.  We also saw several
specific geometric dualities relating for example points in one
space to lines in another.

Today we will consider data structures for encoding adjacency.
All of you are familiar with adjacency, for example, in an abstract
graph, in which vertices are adjacent to edges, and vice versa.
In geometry this notion of adjacency is extended in several ways.

First, a general-dimensional object (say, a polyhedron in 3D) has
several component objects (in this case, vertices, edges, and faces),
and each of these can be adjacent on others in a restricted fashion.

Second, an ADS is typically associated with a geometric
embedding, consisting of coordinate data for each component.

Finally, objects may have to satisfy some global geometric
constraint.  For example, an ADS might represent a planar
subdivision (thus having an embeddable graph).  Or an ADS
might represent a polyhedral object which must be manifold.

Justin Legakis

-> Adjacency Demos <-

Readings:

• Guibas, L. and Stolfi, J., Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams
• Baumgardt, B., Winged-Edge Polyhedron Representation

• OpenGL CDT (quad-edge implementation)
• LEDA
• CGAL

Demonstration suggestions:

To discuss:

• How else do ADS's differ from abstract graphs?
• What is space cost to encode a geometric object this way ?
• What is the time cost ?
• How could you build a "sanity checker" for various ADS's?

Next time, we will see our first application topic, 2D convex hulls.
Convex hulls nicely combine all of the material we have covered
so far.  Geometric primitives (points, halfspaces) are crucial inputs
to convex hull algorithms, as are fundamental operators for
sidedness, etc.  Duality transforms allow us to compute convex
intersections of halfspaces using an algorithm for the convex hull
of points.  Finally, adjacency data structures allow the compact
representation of the convex hull -- the object we have gone to
so much trouble to generate !

Last Meeting .... Next Meeting .... Course Page .... Meeting Schedule

Created: Feb 1998