arvind@utcsri.UUCP (05/29/87)
Date: Wed, 20 May 87 09:23:05 EDT
From: Derick Wood <dwood@waterloo.csnet>
Subject: Symposium on Computation Geometry
SYMPOSIUM
ON
COMPUTATIONAL GEOMETRY
Waterloo, Ontario, 8-10 June 1987
Sponsored by ACM SIGGRAPH and ACM SIGACT
Conference Chair: Derick Wood
Program Chair: Chee K. Yap
Program Committee
Herbert EdelsbrunnerLeo J. Guibas
A. Robin Forrest Tomas Lozano-Perez
Steve Fortune Micha Sharir
Alain Fournier Godfried T. Toussant
Ron L. Graham
CONFERENCE INFORMATION
LOCATION: The conference is located in Waterloo, Ontario,
Canada, in Mennonite country. The city of Waterloo is located
approximately 110 kilometers west of Toronto. U.S. citizens must
bring appropriate identification -- a passport or birth certifi-
cate is ideal, but a driver's license should also work. If you
are not a citizen of the U.S. or Canada you may require a visa;
enquire in advance. Currently, the Canadian dollar costs about
75 U.S. cents. Although U.S. dollars are accepted here, you
should change money before buying anything. There is a bank on
campus.
The conference will be held at the University of Waterloo
Conference Centre, Village II, Waterloo (1-519-884-5400). This
is about a one-hour drive from Toronto International Airport.
Alternatively, it is about a three-hour drive from Buffalo Inter-
national Airport.
FLIGHT DISCOUNT INFORMATION: AIR CANADA will provide you with 20%
discount for an in-Canada flight and 25% for a U.S.-Canada flight
to this conference.
When booking your flight with Air Canada mention the Sympo-
sium and the Symposium Number 871078 (The number is more impor-
tant)
LOCAL TRANSPORTATION: From Toronto Ai
port, Airways Transit
operates a-door-to-door minibus service. Go to the Ground Tran-
sportation Desk on the Arrivals Level. This should be booked in
advance by calling 1-519-658-5521. If you are arriving on Satur-
day or Sunday, you should mention the ACM Conference to obtain
the special rate of CAN $17.
ACCOMMODATION: Inexpensive dormitory accommodations are avail-
able at the University of Waterloo, ``Village II'' residence (CAN
$26.00 single, $22.25 twin per person; this includes breakfast
and tax). Services include daily towel and linen service. For
these University accommodations, please phone 519-884-5400.
A block of rooms is also available at the Waterloo Inn, (475
King St. North, Waterloo, Ontario N2J 2Z5, 1-519-884-0220 for
those desiring hotel accommodations (CAN $60 single, $70 double,
plus tax, per night). You must contact the Waterloo Inn directly
if you wish to stay there mentioning the ACM conference. This
modern hotel is a ten minute drive from the conference centre.
REGISTRATION
Please register in advance using the form provided. Registration
rates go up markedly after 15 May 1987. A registration desk will
be open Sunday evening from 7:30 pm as well as throughout the
conference. Registrants receive one copy of the proceedings,
three lunches and one dinner. Additional copies of the proceed-
ings will be available at the registration desk.
Copies of the proceedings will also be available for pur-
chase from ACM after the conference (call toll free: 1-800-342-
6626 (in Baltimore, Canada, or Alaska 301-528-4261) or write to:
ACM Order Department, P.O. Box 64145, Baltimore, MD 21264).
REGISTRATION RATES
ACM and/or SIGGRAPH
or SIGACT member $155
Non-member $185
Full-time student $ 50
ACTIVITIES: The Stratford and Shaw Festivals are close by
If
you are interested call 1-519-273-1600 (Stratford) and 1-416-
468-2172 (Shaw).
FURTHER INFORMATION: Contact Derick Wood, Department of Computer
Science, University of Waterloo, Waterloo, Ontario, Canada N2L
3G1 (519-888-4456 or dwood at waterloo.csnet).
THE PROGRAM
Monday Morning
All sessions are held in the Great Hall, Village II.
Session Chair: Ron Graham
9:30 Computing the Link Center of a Simple Polygon
W. Lenhart (Williams College), R. Pollack (N.Y.U.), J. Sack
(Carleton University), R. Seidel (IBM Almaden), M. Sharir
(N.Y.U. and Tel Aviv University), S. Suri (Johns Hopkins
University), G. Toussaint (McGill University), C. Yap (N.Y.U.)
and S. Whitesides (McGill University).
9:50 Finding the Visibility Graph of a Simple Polygon in Time
Proportional to Its Size
J. Hershberger (Stanford University)
10:10 Jordan Sorting Via Convex Hulls of Certain Non-simple Polygons
F. Aurenhammer (Technical Universit of Graz)
10:30 The Weighted Region Problem
C. Papadimitriou (Stanford University)
and J. Mitchell (Cornell University)
10:50 Coffee
11:20 On the Geodesic Voronoi Diagram of Point Sites in a
Simple Polygon
B. Aronov (N.Y.U.)
11:45 Optimal Shortest Path Queries in a Simple Polygon
L. J. Guibas (DEC/SRC, Stanford University) and J. Hershberger
(Stanford University)
12:05 The All-Geodesic-Furthest Neighbor Problem for Simple Polygons
S. Suri (Johns Hopkins University)
12:30 Lunch
Monday Afternoon
Session Chair: Godfried Toussaint
2:30 Invited speaker: Branko Grunbaum (Washington)
New Directions in the Theory of Polyhedra
3:20 Oriented Projective Geometry
J. Stolfi (DEC/SRC)
3:40 Primitives for the Manipulation of Three-Dimensional Subdivisions
D. P. Dobkin and M. J. Laszlo (Princeton University)
4:00 Break
4:30 A Graph Based Approach to Object Feature Recognition
L. De Floriani (Isttuto per la Matematica Applicata del
C.N.R.)
4:50 Polygon Properties Calculated From The Vertex Neighborhoods
W. R. Franklin (Rensselaer Polytechnic Institute)
5:10 Numerical Stability of Geometric Algorithms
T. Ottmann, G. Thiemt, and C. Ullrich (Universitat
Karlsruhe)
5:30 Discrete Simulation of NC Machining
R. L. Drysdale and R. B. Jerard (Dartmouth College)
7.00 Banquet
Tuesday Morning
Session Chair: A. Robin Forrest
9:00 Invited speaker: Ed Catmull (Pixar Corp.)
Visualization of Volumes
9:50 Moving a Ladder in Three Dimensions: Upper and Lower Bounds
Y. Ke and J. O'Rourke (Johns Hopkins University)
10:10 On Detecting the Orientation of Polygons and Polyhedra
B.K. Natarajan (Carnegie-Mellon University)
10:30 Coffee
11:00 Simplified Voronoi Diagrams
J. Canny and B. Donald (MIT)
11:25 An Optimal O(nlogn) Algorithm for Contour Reconstruction from Rays
P. D. Alevizos (University of Patras), J. Boissonnat
(I.N.R.I.A.) and M. Yvinec (Ecole Normale Superieure)
11:45 Compliant Motion Planning with Geometric Models
C. Bajaj and M. Kim (Purdue University)
12:05 Lunch
Tuesday Afternoon
Session Chair: Micha Sharir
2:30 On the Number of Faces in Higher-Dimensional Voronoi Diagrams
R. Seidel (IBM Almaden)
2:50 Toughness and Delaunay Triangulations
M. Dillencourt (University of Maryland)
3:15 Joint Triangulations and Triangulation Maps
A. Saalfeld (Bureau of Census)
3:35 Parallel Processing for Efficient Subdivision Search
N. Dadoun and D. G. Kirkpatrick (University of British
Columbia)
3:55 Break
4:25 Constrained Delaunay Triangulations
L. P. Chew (Dartmouth College)
4:50 An Optimal Algorithm for Constructing the Delaunay Triangulation of a
Set of Line Segments
C. Wang and L. Schubert (University of Alberta)
5:10 A Note on Relative Neighborhood Graphs
J. W. Jaromczyk and M. Kowaluk (University of Kentucky)
5:30 Simultaneous Containment of Several Polygons
F. Avnaim and J. Boissonnat (I.N.R.I.A.)
9.00 Business Meeting
Wednesday Morning
Session Chair: Steve Fortune
9:00 Invited speaker: Sheeram Abhyankar (Purdue)
Glimpses of Algebraic Geometry
9:50 Rectilinear Shortest Paths Through Polygonal Obstacles in
2
O(nlog n) Time
K. Clarkson, S. Kapoor and P. Vaidya (AT&T Bell Laboratories)
10:10 A Bucketing Algorithm for the Orthogonal Segment Intersection
Search Problem and Its Practical Efficiency
M. Edahiro (NEC Corporation), K. Tanaka (NEC Corporation),
T. Hoshino (Sophia University) and T. Asano (Sophia University)
10:30 Coffee
11:00 Covering a Simple Orthogonal Polygon with a Minimum Number of
Orthogonally Convex Polygons
R. A. Reckhow and J. Culberson (University of Alberta)
11:25 Fast Algorithms for Computing the Largest Empty Rectangle
A. Aggarwal (IBM T.J. Watson Center and S. Suri (Johns Hopkins
University)
11:45 Variations on Visibility
J. I. Munro (University of Waterloo), M. H. Overmars
(University of Utrecht) and D. Wood (University of Waterloo)
12:05 Lunch
Wednesday Afternoon
Session Chair: Herbert Edelsbrunner
2:30 Algorithms for Line Transversals in Space
D. Avis and R. Wenger (McGill University)
2:50 Congruence, Simularity, and Symmetries of Geometric Objects
H. Alt (FU Berlin), K. Melhorn (Universitat des Saarlandes),
H. Wagener (TU Berlin) and E. Welzl (TU Graz)
3:15 Establishing Order in Planar Subdivisions
D. G. Kirkpatrick (University of British Columbia)
3:35 Computing Simple Circuits From a Set of Line Segments is
NP-Complete
D. Rappaport (Queen's University)
3:55 Break
4:25 Partitioning and Geometric Embedding of Range Spaces of Fin-
ite Vapnik-Chervonenkis Dimension
N. Alon, D. Haussler and E. Welzl (Technical University of Graz)
4:45 Constructing Low Degree Blending Surfaces
J. Warren (Rice University)
5:05 Analyzing Surfaces: The Truth About Elimination Theory
A. Schwartz and C. M. Stanton (University of Michigan)
5.25 Adjourn