## Algorithms from Computational Geometry

Over the course of several years, Franklin & Marshal students and I have developed a number of QuickTime® movies to show the progress of algorithms from computational geometry. The collection [will be] available here.

The topics include: binary space partition, the convex hull, the convex hull in three dimensions, the Delaunay triangulation, line intersection, motion planning, the painter's algorithm, point-in-polygon, polygon triangulation, the range tree, and the Voronoi diagram. As an example, below: one frame of a movie of the plumbline algorithm for solving the point-in-polygon problem.

On the associated web pages, you will find a description of the algorithms from computational geometry and the QuickTime movies which visualize them. The movies can be downloaded from this site, or you may write to the author and obtain a CD with the movies. At present, YouTube favors movies in a "landscape" format, either 4:3 or 16:9, and most of my QuickTime movies are in a "portrait" format, usual 1:1.25. They do not show well on YouTube, and so I have not used that venue.

In what follows, if one clicks on the "thumbnail," one will download the movie. In many browsers, this will place the movie on a new web page, from which it may be copied to the user's computer, but at least one can watch the movie. If this fails to download to the computer, click on the text "downlaod zip," to obtain a zipped file of the movie.

Some movies have built-in pauses (actually, invisible sprites) which stop the movie at certain places and pose a question to the student or user. These movies will have a 'Q' in the file name.

As an experiment, we made some movies with an embedded QuickTime virtual reality (QTVR) segment. The movie pauses, and the user can drag the object on the screen (a frame of a visualization) to examine it from all sides. These movies have "VR" in their file name. The "Q" and "VR" movies may not display propertly on your browser; please obtain the zipped file, or contact the author.

For all of these algorithms, one or both of these references will help: O'Rourke, Joseph,

chapter 5. DeBerg, M., van Kreveld, M., Overmars, M., Schwarzkopf, O.,

The topics include: binary space partition, the convex hull, the convex hull in three dimensions, the Delaunay triangulation, line intersection, motion planning, the painter's algorithm, point-in-polygon, polygon triangulation, the range tree, and the Voronoi diagram. As an example, below: one frame of a movie of the plumbline algorithm for solving the point-in-polygon problem.

On the associated web pages, you will find a description of the algorithms from computational geometry and the QuickTime movies which visualize them. The movies can be downloaded from this site, or you may write to the author and obtain a CD with the movies. At present, YouTube favors movies in a "landscape" format, either 4:3 or 16:9, and most of my QuickTime movies are in a "portrait" format, usual 1:1.25. They do not show well on YouTube, and so I have not used that venue.

In what follows, if one clicks on the "thumbnail," one will download the movie. In many browsers, this will place the movie on a new web page, from which it may be copied to the user's computer, but at least one can watch the movie. If this fails to download to the computer, click on the text "downlaod zip," to obtain a zipped file of the movie.

Some movies have built-in pauses (actually, invisible sprites) which stop the movie at certain places and pose a question to the student or user. These movies will have a 'Q' in the file name.

As an experiment, we made some movies with an embedded QuickTime virtual reality (QTVR) segment. The movie pauses, and the user can drag the object on the screen (a frame of a visualization) to examine it from all sides. These movies have "VR" in their file name. The "Q" and "VR" movies may not display propertly on your browser; please obtain the zipped file, or contact the author.

For all of these algorithms, one or both of these references will help: O'Rourke, Joseph,

*Computational Geometry in C.*Cambridge University Press, 1994;chapter 5. DeBerg, M., van Kreveld, M., Overmars, M., Schwarzkopf, O.,

*Computational Geometry: Algorithms and Applications.*Springer, 2000 (second edition); chapter 7.**Other Algorithms.**We have also made movies for algorithms for Binary Space Partitioning, the Painter's Algorithm, and Range Tree algorithms. For information about these, please contact me.