FIRST CGC WORKSHOP ON COMPUTATIONAL GEOMETRY October 11-12, 1996 Sponsored by Center for Geometric Computing in cooperation with the Johns Hopkins Department of Computer Science, which is celebrating its 10-year anniversary ---------------------------------------------------------------------------- We are pleased to have hosted the first in a series of annual fall workshops on Computational Geometry, sponsored by the Center for Geometric Computing (CGC), continuing a tradition established by the Mathematical Sciences Institute at SUNY- Stony Brook (click here for last year's proceedings). The CGC is a collaborative center of the Brown, Duke, and Johns Hopkins Universities, and is funded by the U.S. Army Research Office. Location: Johns Hopkins University, Baltimore, Maryland. (Click here for directions.) The meeting location was Shaffer Hall, Room 3. Themes: The focus of this meeting is to bring together researchers from academia, industry, and Army to stimulate collaboration on problems of common interest arising in geometric computations. Topics include: 1. Algorithmic methods in geometry; 2. Applications of computational geometry, including robustness and implementation issues; 3. Computer graphics; 4. Animation of geometric algorithms; 5. Computer-aided design, solid modeling, mesh generation; 6. Geographic information systems; 7. Robotics and machine vision. ---------------------------------------------------------------------------- Related Events: * 5th International Meshing Roundtable, sponsored by Sandia National Laboratories, hosted by ANSYS, Inc., to be held in Pittsburgh, Pennsylvania, U.S.A., on October 10-11, 1996. The workshop partially overlaps this roundtable in both time and scope. * 37th IEEE Symposium on Foundations of Computer Science (FOCS '96), to be held in Burlington, Vermont, immediately after the workshop, on October 14-16, 1996. ---------------------------------------------------------------------------- Format: Following the tradition of the first five MSI Workshops on Computational Geometry, the format of the workshop was informal, extending over 2 days, with several breaks scheduled for discussions. Invited Speakers: Bernard Chazelle (Princeton) Dimitris Metaxas (Univ. Penn.) Dinesh Manocha (Univ. North Carolina) Supporting Materials: The Call for Papers. Official Participant List. A booklet of abstracts was distributed at the workshop and is available electronically below (click here for last year's proceedings). There will be no formal (physical) proceedings for this workshop, but selected papers will be invited to a special issue of International Journal of Computational Geometry and Applciations editted by Pankaj Agarwal. Registration was on-site, and included the abstract booklet and coffee breaks. There was no registration fee. ---------------------------------------------------------------------------- PROGRAM AND ABSTRACTS Friday, October 11, 1996, Shaffer Hall, Room 3 8:45am: Opening Remarks 9:00am: Invited Lecture: Physics-Based Modeling Techniques for Shape and Motion Estimation, Dimitris Metaxas (U. Penn.) 9:50am: Useful Metrics for Modular Robot Motion Planning, A. Pamecha, I. Ebert-Uphoff, G.S. Chirikjian (Johns Hopkins) 10:10am: Motion via Pushing, P.K. Agarwal (Duke), L.-C. Latombe (Stanford), R. Motwani (Stanford), P. Raghavan (IBM) 10:30am: Coffee Break 11:00am: A Visibility-Based Pursuit-Evasion Problem (also available as a full paper), L.J. Guibas, J.-C. Latombe, S.M. LaValle, D. Lin, R. Motwani (Stanford) 11:20am: A Competitive Strategy for Learning a Polygon, F. Hoffmann (Freie U.-Berlin), C. Icking (Fern U.-Hagen), R. Klein (Fern U.-Hagen), K. Kriegel (Freie U.-Berlin) 11:40am: RAPID: Randomized Pharmacophore Identification for Drug Design, L.E. Kavraki (Rice), J.-C. Latombe, R. Motwani, C. Shelton, S. Venkatasubramanian (Stanford) 12:00 noon: Lunch (local restaurant guide will be provided) 2:00pm: Invited Lecture: Computational Geometry at the Crossroads, Bernard Chazelle (Princeton) 2:50pm: New Lower Bounds for Halfspace Emptiness, J. Erickson (Duke) 3:10pm: On Minimum-Area Hulls (also available as a full paper), E.M. Arkin, Y.-J. Chiang (SUNY-SB), M. Held (U. Salzburg), J. Mitchell (SUNY-SB), V. Sacristan (U. Politecnica de Catalunya), S. Skiena (SUNY-SB), T.-C. Yang (Kyungsung U.) 3:30pm: Soda Break 4:00pm: Geometric Computing Over the World Wide Web, R. Tamassia (Brown) 4:20pm: Intractability of Assembly Sequencing, AND/OR Scheduling, and Removing a Unit Disk (also available as a full paper), M. Goldwasser, R. Motwani (Stanford) 4:40pm: Incremental Construction of the Generalized Voronoi Diagram, the Generalized Voronoi Graph, and the Hierarchical Generalized Voronoi Graph (also available as a full paper), H. Choset (CMU) ---------------------------------------------------------------------------- Saturday, October 12, 1996, Shaffer Hall, Room 3 9:00am: Invited Lecture: Towards Interactive Walkthough of Large CAD Models, Dinesh Manocha (UNC) 9:50am: Triangulation-Based Object Reconstruction Methods, C.L. Bajaj, F. Bernardini (Purdue) 10:10am: Finding the Conforming Closure of Quadtree/Octree Structures - Refining Quadrilateral and Hexxahedral Element Meshes, R. Schneiders (RWTH-Aachen) 10:30am: Coffee Break 11:00am: Optimal Dynamic Interval Management in External Memory (also available as a full paper), L. Arge, J.S. Vitter (Duke) 11:20am: Stabbing Orthogonal Objects in 3-Space, D.M. Mount, F.-T. Pu (U. Maryland) 11:40am: Binary Space Partitions for Fat Rectangles (also available as a full paper), P.K. Agarwal, E.F. Grove (Duke), T.M. Murali (Brown), J.S. Vitter (Duke) 12:00 noon: Lunch (local restaurant guide will be provided) 2:00pm: Path Planning and Expansive Configuration Spaces (also available as a full paper), D. Hsu, J.-C. Latombe, R. Motwani (Stanford) 2:20m: Computational Physics Meets Computational Geometry, J. Glimm, S.R. Simanca, T. Smith, F. Tangerman (SUNY-SB) 2:40pm: A Computational-Geometry-Based Tool for the Cellular Design of Millimeterwave Mobile Communications Systems in Urban Environments (also available as a full paper), F.J. Velez (U. da Beira Interior), J.M. Brazio (Inst. Superior Tecnico) 3:00pm: Soda Break 3:30pm: Random Triangulations and Trees, L. Devroye (McGill), P. Flajolet (INRIA), F. Hurtado, M. Noy (U. Politecnica de Catalunya), W. Steiger (Rutgers) 3:50pm: A Duality Between Small-Face Problems in Arrangements of Lines and Heilbronn-Type Problems, G. Barequet (Johns Hopkins) 4:10pm: Clusters of Stars, I. Streinu (Smith) ---------------------------------------------------------------------------- Accommodations: We reserved blocks of rooms in several local inns, which expired on September 15, 1996. * Broadview Apartments. 116 W. University Pkwy, Baltimore, MD, 21218; (410)243-1216. An apartment building, with furnished apartments available on a daily basis, across the street from the University. Single/double: $55/60 (0 rooms allocated, but they should have 11 rooms available). * Carlyle Apartments. 500 W. University Pkwy, Baltimore, MD, 21218; (410)889-4500, fax: (410)467-3073. An apartment building, with furnished apartments available on a daily basis, a short walk from the University. Single/double: $61.88 (7 rooms allocated.) * Cross Keys Inn. Village of Cross Keys, 5100 Falls Rd., Baltimore, MD; (410)532-6900, (800)532-KEYS; fax: (410)532-2403. A full-service hotel located in a quiet wooded community a short (10-minute) drive/ride from the University (a van service is available at $10 per trip for the entire group, which can be as large as 13). Single/double: $95. (25 rooms allocated.) * Doubletree Inn at the Colonnade. 4 West University Pkwy., Baltimore, MD 21218; (410)235-5400, (800)222-TREE, fax: (410)366-6734. A full-service hotel across the street from the University. Single/double: $115. (25 rooms allocated, but just for October 10 and 11.) * Hopkins Inn. 3404 St. Paul St., Baltimore, MD 21218; (410)235-8600, fax: (410)235-7051. A lovely bed-and-breakfast inn just around the corner from the University. Single/double: $79. (11 rooms allocated.) ---------------------------------------------------------------------------- Organizers: Pankaj Agarwal (pankaj@cs.duke.edu), Michael Goodrich (goodrich@jhu.edu), S. Rao Kosaraju (kosaraju@cs.jhu.edu), Joe Mitchell (jsbm@ams.sunysb.edu), Franco Preparata (franco@cs.brown.edu), Roberto Tamassia (rt@cs.brown.edu), Jeff Vitter (jsv@cs.duke.edu) For further information please contact Michael Goodrich (Dept. of Computer Science, Johns Hopkins Univ., Baltimore, MD 21218; goodrich@jhu.edu; (410)516-7708). ---------------------------------------------------------------------------- [Image] ----------------------------------------------------------------------------