12th Annual Video Review of
Computational Geometry

part of the
19th ACM Symposium on Computational Geometry

June 8-10, 2003   --   San Diego, USA
In conjunction with FCRC 2003
Sponsored by ACM SIGACT and SIGGRAPH


Video Review

This video review of computational geometry appears as a DVD-Video, distributed to participants of the 19th ACM Symposium on Computational Geometry. For better distribution, this year we are making the videos freely available on the web.


  1. The Asteroid Surveying Problem and Other Puzzles
    by Timothy M. Chan, Alexander Golynski, Alejandro López-Ortiz, and Claude-Guy Quimper
    [QuickTime] -- [Windows Media] -- [Short Paper]
  2. VASCO: Visualizing and Animating Spatial Constructs and Operations
    by František Brabec, Hanen Samet, and Cemal Yilmaz
    [QuickTime] -- [Windows Media] -- [Short Paper]
  3. Billboard Clouds for Extreme Simplification
    by Xavier Décoret, Frédo Durand, François Sillion, and Julie Dorsey
    [QuickTime] -- [Windows Media] -- [Short Paper]
  4. A 3-D Visualization of Kirkpatrick's Planar Point Location Algorithm
    by John Iacono
    [QuickTime] -- [Windows Media] -- [Short Paper]
  5. Morphing between Shapes by Using their Straight Skeletons
    by Gill Barequet and Evgeny Yakersberg
    [QuickTime] -- [Windows Media] -- [Short Paper]
  6. 3DTreeDraw: A Three Dimensional Tree Drawing System
    by Tom Murtagh and Seok-Hee Hong
    [QuickTime] -- [Windows Media] -- [Short Paper]
  7. Online Dispersion Algorithms for Swarms of Robots
    by Tien-Ruey Hsiang, Esther M. Arkin, Michael A. Bender, Sándor P. Fekete, and Joseph S. B. Mitchell
    [QuickTime] -- [Windows Media] -- [Short Paper]
  8. Finding a Curve in a Map
    by Carola Wenk, Helmut Alt, Alon Efrat, Lingeshwaran Palaniappan, and Günter Rote
    [QuickTime] -- [Windows Media] -- [Short Paper]
  9. Fast Penetration Depth Estimation Using Rasterization Hardware and Hierarchical Refinement
    by Young J. Kim, Miguel A. Otaduy, Ming C. Lim, and Dinesh Manocha
    [QuickTime] -- [Windows Media] -- [Short Paper]


Each video is available online in three formats. Windows Media (9) is recommended for machines running Microsoft Windows, though it may also play on Linux machines with appropriate software. QuickTime is recommended for machines running MacOS, and should also work well on most other machines (Windows and Linux) with appropriate extra software. All formats should stream (quickly start playing without requiring full download) with a video player supporting progressive downloads. Short (1- or 2-page) papers describing the videos are also available through the ACM Digital Library's online proceedings, provided you or your instutition has a subscription.

Recommended Players

Windows users should already have Windows Media Player installed; note that version 9 or higher is required for the Windows Media videos. Macintosh users should already have QuickTime (version 5 or higher) installed; Windows users can also download this software to play the QuickTime videos. Linux users may want to try the video player mplayer especially for the QuickTime and Windows Media videos.


These videos were selected from the submissions by the following video program committee: This video review was produced by Tom Buehler in the Computer Graphics Group at MIT. Kathleen Dickey designed the menus. Many thanks go to Tom and Kathleen for their hard work preparing the DVD and the web proceedings. Thanks also to the Computer Graphics Group for supporting this production.

When rescuing this web page from the past site, which was broken, to this site http://www.computational-geometry.org, the webmaster had to remove some of the formats originally provided, to save storage.

  12th Annual Video Review of Computational Geometry

19th ACM Symposium on Computational Geometry 2003