scot@KINSMAN.DARTMOUTH.EDU (Scot Drysdale) (03/04/91)
7th Annual Symposium on
COMPUTATIONAL GEOMETRY
June 10--12, 1991
Red Jacket Mountain View
North Conway, New Hampshire
Sponsored by the ACM Special Interest Groups for
Graphics and for Automata and Computability Theory
LOCATION: The 7th ACM Symposium on Computational Geometry will be held
in North Conway, New Hampshire at the Red Jacket Mountain View Inn.
North Conway is a resort town on the edge of the White Mountain National
Forest. The hotel is located on a 25 acre hilltop site, with a view of
Mount Washington, the highest peak in New England.
The area is best known for its mountains and outdoor activities.
It has hundreds of hiking trails, ranging from strolls by ponds
and waterfalls to strenuous hikes up mountain peaks to cliffs frequented
by technical rock climbers. The easy way to ``climb'' a mountain is to take
the auto road or cog railway to the top of Mount Washington. Canoes can be
rented on the nearby Saco River. The hotel has tennis courts and indoor
and outdoor pools, and there are golf courses in the town.
Family attractions in the area include covered bridges, the Conway
Scenic Railroad, Heritage New Hampshire, Storyland, alpine slides, water
slides, and amusement parks. Bargain hunters will find dozens of outlet
stores in the area.
FOR MORE INFORMATION contact:
Scot Drysdale, Dept. of Mathematics and Computer Science
Dartmouth College
Hanover, NH 03755.
Tel: 603/646-2101.
Email: scot.drysdale@dartmouth.edu
I can mail a LaTeX version of the advanced program and registration
materials, or can send hard copy in a couple of weeks. Members of
SIGACT and members of SIGGRAPH who live in New England will be mailed
hard copy of the advance program. The LaTeX file will be distribted
over the network as a separate posting.
PROGRAM
Sunday, June 9, 1991
Reception 7:30--10:00 pm, New Hampshire room, Red Jacket.
Monday, June 10, 1991
Session 1: 8:30--9:50 am
Chair: Emo Welzl, Freie Universitat Berlin
8:30 Efficient Partition Trees.
Jiri Matousek, Charles University
8:50 Counting Circular Arc Intersections.
Pankaj Agarwal, Duke University, Micha Sharir, Tel Aviv and
New York University
9:10 Efficient Ray Shooting and Hidden Surface Removal.
Mark de Berg, Utrecht University, Dan Halperin, Tel Aviv University,
Mark Overmars, Jack Snoeyink, Marc van Kreveld, Utrecht University
9:30 Efficient Hidden Surface Removal for Objects with Small Union Size.
Matthew Katz, Tel Aviv University, Mark Overmars, Utrecht University,
Micha Sharir, Tel Aviv University
Coffee Break 9:50--10:20 am
Session 2: 10:20--12:00 am
Chair: Frank Dehne, Carleton University
10:20 Intersection Queries for Curved Objects.
Pankaj Agarwal, Duke University, Marc van Kreveld, Mark Overmars,
Utrecht University
10:40 Shortest Path Queries in Rectilinear Worlds of Higher Dimension.
Mark de Berg, Marc van Kreveld, Utrecht University, Bengt Nilsson,
Alberts-Ludwigs Universitat
11:00 Dynamization of the Trapezoid Method for Planar Point Location.
Yi-Jen Chiang, Roberto Tamassia, Brown University
11:20 Computing Shortest Transversals of Sets.
Binay Bhattacharya, Simon Fraser University, Jurek Czyzowicz,
Universite du Quebec a Hull, Peter Egyed, Godfried Toussaint,
McGill University, Ivan Stojmenovic, Jorge Urrutia, University
of Ottawa
11:40 Optimal Algorithms for Some Smallest Intersection Radius Problems.
Binay Bhattacharya, Simon Fraser University, Sreesh Jadhav,
Asish Mukhopadhayay, Indian Institute of Technology, Jean-Marc Robert,
McGill University
Lunch Break 12:00--1:45 pm
Session 3: Invited Lecture
1:45 Orthoganal Trees.
H. S. M. Coxeter, University of Toronto
Session 4: 2:45--3:45 pm
Chair: Ricky Pollack, New York University
2:45 A Pivoting Algorithm for Convex Hulls and Vertex Enumeration
of Arrangements and Polyhedra.
David Avis, McGill University, Komei Fukuda, University of Tsukuba
3:05 Nonoverlap of the Star Unfolding.
Boris Aronov, Polytechnic University, Brooklyn, Joseph O'Rourke,
Smith College
3:25 A Generalization of Dehn-Sommerville Relations to Simple Stratified
Spaces.
Ketan Mulmuley, University of Chicago
Excursion: Leave from Red Jacket at 4:30 pm
Clambake: 7:30 pm, Red Jacket.
If the weather is bad, the excursion and clambake will be moved to Tuesday.
The last Tuesday session and business meeting will be moved to Monday.
Times will remain the same.
Tuesday, June 11, 1991
Session 5: 8:30--9:50 am
Chair: Mike Goodrich, Johns Hopkins University
8:30 Randomized, Multidimensional Search Trees.
Ketan Mulmuley, University of Chicago
8:50 Dynamic Point Location in Arrangements of Hyperplanes.
Ketan Mulmuley, Sandeep Sen, University of Chicago
9:10 A Simple On-line Randomized Incremental Algorithm for
Computing Higher Order Voronoi Diagrams.
Franz Aurenhammer, Otfried Schwarzkopf, Freie Universitat Berlin
9:30 Randomized Parallel Algorithms for Trapezoidal Diagrams.
Kenneth Clarkson, AT&T Bell Laboratories, Richard Cole, New York
University, Robert Tarjan, Princeton University
Coffee Break 9:50--10:20 am
Session 6: 10:20--12:00 am
Chair: Chee Yap, New York University
10:20 On the Convex Hull of the Integer Points in a Disc.
Antal Balog, Institute of Advanced Study, Princeton, Imre Barany,
Yale University and New York University
10:40 The Two Guards Problem.
Christian Icking, Rolf Klein, Universitat-Gesamthochschule Essen
11:00 Extremal Point Containment Problems.
Sivan Toledo, Tel Aviv University
11:20 Approximate Matching of Polygonal Shapes.
Helmut Alt, Bernd Behrends, Johannes Blomer, Freie Universitat Berlin
11:40 The Upper Envelope of Voronoi Surfaces and its Applications.
Daniel Huttenlocher, Cornell University, Klara Kedem, Tel Aviv
University, Micha Sharir, Tel Aviv and New York University
Lunch Break 12:00--1:45 pm
Session 7: Invited Lecture
1:45 Minimal Surfaces, Crystals, and Norm on R^n.
Frank Morgan, Institute of Advanced Study, Princeton
Session 8: 2:45--3:45 pm
Chair: Kokichi Sugihara, Tokyo University
2:45 Multiplicatively Weighted Crystal Growth Voronoi Diagrams.
Barry Schaudt, Scot Drysdale, Dartmouth College
3:05 Nearest Neighbor Problems.
Gordon Wilfong, AT&T Bell Laboratories
3:25 Enumerating k Distances for n Points in the Plane.
Matthew Dickerson, Middlebury College, Scot Drysdale, Dartmouth College
Coffee Break: 3:45--4:15 pm
Session 9: 4:15--5:15 pm
Chair: Chanderjit Bajaj, Purdue University.
In case of bad weather on Monday this session will be
moved to Monday, same time, in exchange for the excursion.
4:15 Transitions in Geometric Minimum Spanning Trees.
Clyde Monma, Subhash Suri, Bellcore, Morristown
4:35 How to Take Short Cuts.
Claire Kenyon, Richard Kenyon, Ecole Normale Superieure Paris
4:55 Construction of Multidimensional Spanner Graphs, with Applications
to Minimum Spanning Trees.
Jeffrey Salowe, University of Virginia
Business meeting, 8:30--10:30 pm, New Hampshire room.
If the weather is bad on Monday this meeting will be held on Monday, same
time.
Wednesday, June 12, 1991
Session 10: 8:30--9:50 am
Chair: Hiroshi Imai, Tokyo University
8:30 Geometric Algorithms for a Minimum Cost Assignment Problem.
Takeshi Tokuyama, Jun Nakano, IBM Tokyo Research Laboratory
8:50 On Upward Drawing Testing of Triconnected Digraphs.
Paola Bertolazzi, IASI-CNR, Roma, Giuseppe Di Battista,
Universita di Roma
9:10 A Packing Problem with Applications to Lettering of Maps.
Michael Formann, Frank Wagner, Freie Universitat Berlin
9:30 Distance Visibility Graphs.
Collette Coullard, Northwestern University, Evanston, Anna Lubiw,
University of Waterloo
Coffee Break 9:50--10:20 am
Session 11: 10:20--12:00 am
Chair: Peter Shor, AT&T Bell Laboratories
10:20 Walking on an Arrangement Topologically.
Tetsuo Asano, Osaka Electro-Communication University, Leonidas Guibas,
Stanford University, Takeshi Tokuyama, IBM Tokyo Research Laboratory
10:40 On the Sum of Squares of Cell Complexities in Hyperplane Arrangements.
Boris Aronov, Polytechnic University, New York, Jiri Matousek,
Charles University, Micha Sharir, Tel Aviv and New York University
11:00 On the Complexity of a Single Cell in Certain Arrangements
of Surfaces in 3-space.
Dan Halperin, Tel Aviv University
11:20 Arrangements of Segments that Share Endpoints: Single Face Results.
Esther Arkin, Cornell University, Dan Halperin, Klara Kedem,
Tel Aviv University, Joseph Mitchell, Cornell University,
Nir Naor, Tel Aviv University
11:40 Numerical Stability of Algorithms for Line Arrangements.
Steven Fortune, AT&T Bell Laboratories, Victor Milenkovic,
Harvard University
Lunch Break 12:00--1:30 pm
Session 12: 1:30--2:50 pm
Chair: Herbert Edelsbrunner, University of Illinois at Urbana-Champaign
1:30 Polynomial-size Nonobtuse Triangulation of Polygons.
Marshall Bern, XEROX Palo Alto Research Center, David Eppstein,
University of California, Irvine
1:50 Crossing Families.
Boris Aronov, Polytechnic University, Brooklyn, Paul Erdos, Hungarian
Academy of Sciences, Wayne Goddard, Daniel Kleitman, Michael Klugerman,
MIT, Janos Pach, Hungarian Academy of Sciences, Leonard Schulman, MIT
2:10 Optimality of the Delaunay Triangulation in R^d.
V. T. Rajan, IBM Watson Research Center
2:30 Decomposition and CSG Representation of Polyhedra with Arbitrary Genus.
Tamal Dey, Purdue University