storb@sbsvax (Christoph Storb) (02/17/89)
5th Annual ACM Symposium
on
COMPUTATIONAL GEOMETRY
Universitaet des Saarlandes
Saarbruecken - West Germany
June 5 -- 7, 1989
Sponsored by
ACM SIGACT and SIGGRAPH,
by EATCS and GI.
In cooperation with
the Universitaet des Saarlandes
and VHS Saarbruecken.
---------------------------------------------------------
Program
=======
Monday, June 5
Chair: Micha Sharir (NYU and Tel Aviv University)
9:00 Opening Address
9:20 Construction of epsilon nets
J. Matousek (Charles University, Prague).
9:40 An efficient deterministic algorithm for
partitioning arrangements of lines and its applications
P. K. Agarwal (NYU).
10:00 Binary partitions with applications to hidden
surface removal and solid modelling
M. S. Paterson (University of Warwick, Coventry)
F. F. Yao (XEROX PARC).
10:20 A fast planar partition algorithm, II
K. Mulmuley (University of Chicago).
10:40 Coffee Break
11:10 Detecting and decomposing self-overlapping curves
P. W. Shor, C. J. Van Wyk (AT&T Bell Labs).
11:30 Area requirement and symmetry display in drawing graphs
G. Di Batista (University of Rome),
R. Tamassia (Brown University),
I. G. Tollis (University of Texas at Dallas).
11:50 Kink-free deformations of polygons
G. Vegter (University of Groningen).
12:10 An efficient algorithm for link-distance problems
Y. Ke (The Johns Hopkins University).
12:30 Lunch
Chair: Leonidas Guibas (DEC SRC and Stanford University)
14:00 Invited Talk:
Algorithms in real algebraic geometry and their applications
M. F. Roy (University of Rennes),
T. Recio (University of Cantabria).
15:00 Computing the irreducible real factors of an algebraic curve
E. Kaltofen (RPI).
15:20 Degree Complexity bounds on the intersection
of algebraic curves
S. S. Abhyankar, S. Chandrasekar, V. Chandru (Purdue University).
15:40 Hermite interpolation of rational space curves using real
algebraic surfaces
C. Bajaj, I. Ihm (Purdue University).
16:00 Coffee Break
16:30 On the parallel decomposability of geometric problems
M. J. Atallah, J. J. Isay (Purdue University).
16:50 Optimal parallel algorithms for visibility of a simple
polygon from a point
M. J. Atallah, D. Z. Chen (Purdue University).
17:10 Parallel computation of Davenport-Schin\-zel-Sequences
S. Chandran, D. Mount (University of Maryland).
19:00 Banquet
---------------------------------------------------------
Tuesday, June 6
Chair: Janos Pach (Hungarian Academy of Sciences)
9:00 Good splitters for counting points in
triangles
J. Matousek (Charles University, Prague),
E. Welzl (Freie Universitaet Berlin).
9:20 Computing partial sums in multi\-dimen\-sio\-nal
arrays
B. Chazelle, B. Rosenberg (Princeton University).
9:40 On the number of halving planes
I. Barany, Z. Furedi (Hungarian Academy of Sciences),
L. Lovasz (Eotvos University).
10:00 An acyclicity theorem for cell complexes
in d dimensions
H. Edelsbrunner (University of Illinois at Urbana).
10:20 Necessary and sufficient conditions for
hyperplane transversals
R. Pollack (NYU),
R. Wenger (University of Montreal).
10:40 Coffee Break
Chair: John Canny (University of California at Berkeley)
11:10 Efficient motion planning for an L-shaped object
D. Halperin (Tel Aviv University),
M. Overmars (University of Utrecht).
11:30 Placing the largest similar copy of a
convex polygon among polygonal obstacles
L. P. Chew, K. Kedem (Cornell University).
11:50 Compliant motion in a single polygon
J. Friedman (Stanford University),
J. Hershberger (DEC SRC),
J. Snoeyink (Stanford University).
12:10 An efficient algorithm for one-step planar
compliant motion planning with uncertainty
A. J. Briggs (Cornell University).
12:30 Lunch
Chair: Christoph Hoffmann (Purdue University)
14:00 Invited Talk:
Computing on Geometry
R. F. Sproull (Sutherland, Sproull and Assoc.).
15:00 Calculating approximate curve arrangements using rounded
arithmetic
V. Milenkovic (Harvard University).
15:20 Epsilon Geometry: Building robust algorithms from imprecise
computations
D. Salesin (Stanford University),
J. Stolfi (DEC SRC),
L. Guibas (DEC SRC and Stanford University).
15:40 Representing geometric structures in d dimensions:
Topology and order
E. Brisson (University of Washington).
16:00 Coffee Break
16:30 Subdivisions of n-dimensional spaces and n-dimensional
generalized maps
P. Lienhardt (University Louis Pasteur, Strasbourg).
16:50 Probing a scene of non-convex polyhedra
J. D. Boissonnat (INRIA),
M. Yvinec (Ecole Normale Superieure).
17:10 Determining sector visibility of a polygon
B. Bhattacharya (Simon Fraser University),
D. Kirkpatrick (University of British Columbia),
G. Toussaint (McGill University).
19:30 Business Meeting
---------------------------------------------------------
Wednesday, June 7
Chair: D. T. Lee (Northwestern University)
9:00 Finding tailored partitions
J. Hershberger (DEC SRC),
S. Suri (Bellcore).
9:20 Minimax geometric fitting of two corresponding sets of points
K. Imai (Kyushu Inst. of Technology),
S. Sumino, H. Imai (Kyushu University).
9:40 Bounded diameter minimum spanning trees and related problems
J. M. Ho, D. T. Lee (Northwestern University),
C. H. Chang (NYU),
C. K. Wong (IBM Yorktown).
10:00 Finding k points with minimum diameter and related problems
A. Aggarwal (IBM Yorktown),
H. Imai (Kyushu University),
N. Katoh (Kobe University of Commerce),
S. Suri (Bellcore).
10:20 Fast geometric approximation techniques and geometric
embedding problems
M. W. Bern (XEROX PARC),
H. J. Karloff (University of Chicago),
P. Raghavan, B. Schieber (IBM Yorktown).
10:40 Coffee Break
11:10 On geometric matching
O. Marcotte (University of Quebec, Montreal),
S. Suri (Bellcore).
11:30 Ray shooting and other applications of spanning trees
with low stabbing number
P. K. Agarwal (NYU).
11:50 Higher-dimensional Voronoi diagrams in linear expected time
R. A. Dwyer (N. Carolina State University).
12:10 On monotone paths among obstacles with applications
to planning assemblies
E. M. Arkin, R. Connelly, J. S. B. Mitchell (Cornell University).
12:30 Lunch
Chair: Mark Overmars (University of Utrecht)
14:00 Minimum partitioning simple rectilinear polygons
in O(n loglog n) time
W. T. Liou (National Tsing Hua University),
J. J. M. Tan (National Chiao Tung University),
R. C. T. Lee (National Tsing Hua University).
14:20 Sweeping arrangements of curves
J. Snoeyink (Stanford University).
J. Hershberger (DEC SRC).
14:40 Stabbing pairwise disjoint translates in linear time
P. Egyed (McGill University),
R. Wenger (University of Montr\eal).
15:00 Coffee Break
15:30 Computing the geodesic diameter of a 3-polytope
J. O'Rourke (Smith College),
C. Schevon (The Johns Hopkins University).
15:50 On the difficulty of tetrahedralizing 3-dimensional
non-convex polyhedra
J. Ruppert, R. Seidel (University of California at Berkeley).
16:10 Triangulating a non-convex polytope
B. Chazelle, L. Palios (Princeton University).
---------------------------------------------------------
Informations
============
Transportation:
---------------
Saarbruecken is easily reachable by train, plane via Frankfurt,
Paris or Luxemburg (note that you may need a visa) or car.
All hotels are located in the centre of Saarbruecken. There are
cab services at the airport and at the train station.
Lodging:
--------
A block of rooms has been reserved for conference participants until
April 30, 1989. Conference participants are urged to make their own
reservation as early as possible, as each hotel has only limited
space. For reservations please use the form provided.
Climate:
--------
Weather at the beginning of June is usually mild, sometimes a bit rainy.
Be prepared for anything.
Location:
---------
The conference is organized by the Universitaet des Saarlandes.
All conference sessions will be held in the `VHS Zentrum am
Schlossplatz' in Saarbruecken, Am Schlossplatz, Raum 4.
Registration:
-------------
Please register in advance using the form provided. Registration
rates increase after May 15, 1989. Registration
for the conference will be located in the foyer of the
VHS Zentrum and will open on Sunday from 6 pm to 9 pm and during the
sessions. Fees are listed elsewhere in this brochure. The registration
fee includes the sessions, one copy of the proceedings, the Sunday
reception, refreshments, and the Monday evening banquet.
Student registration does not include the banquet. Students should
bring evidence of student status to the registration desk.
Reception:
----------
A reception will be held Sunday, June 4, from 6 pm to 9 pm
in the `VHS-Zentrum am Schlossplatz'.
Banquet:
--------
The banquet will be on Monday evening, 7 pm in the castle of
Saarbruecken.
Business Meeting:
-----------------
There will be a business meeting on Tuesday evening, 7.30 pm in the
session hall.
Conference Fees:
----------------
by May 15 after May 15
member of ACM,
GI or EATCS 150 US$ 180 US$
non-member 180 US$ 210 US$
students 50 US$ 50 US$
Summer School:
--------------
In addition to the technical program, a summer school in computational
geometry will be held in the week preceding the conference, where
tutorials given by leading researchers will survey the state of the
art in the field. For further information please contact conference
chair.
Program Committee:
------------------
Richard Bartels D. T. Lee
John Canny Nimrod Megiddo
Kenneth Clarkson Mark Overmars
Leonidas Guibas Janos Pach
Christoph Hofmann Micha Sharir
Conference Chair:
-----------------
Kurt Mehlhorn
Fachbereich 10 - Informatik,
Universitaet des Saarlandes,
6600 Saarbruecken,
West Germany.
For further information please send e-mail to
storb%sbsvax.informatik.uni-saarland.dbp.de
or call -- (681) 302 3028.
Registration Form:
==================
Symposium on Computational Geometry `89
Please return to:
Ch. Storb
FB10 - Informatik
Universitaet des Saarlandes
D 6600 Saarbruecken
West Germany
Name: _______________________________________
Address: _______________________________________
_______________________________________
_______________________________________
_______________________________________
Payment: o cheque enclosed
o by money order
Date: _________ Signature: ______________
Room Reservation Form:
======================
Symposium on Computational Geometry `89
Please return to:
Verkehrsverein Saarbruecken
Rathaus
D 6600 Saarbruecken
West Germany
Category 1: 100.- to 200.- DM
Room with bath and toilet
Category 2: 80.- to 100.- DM
Room with shower and toilet
Category 3: 60.- to 70.- DM
Room with shower
Category 4: 40.- to 60.- DM
Room with c/w water
I choose the rooms category No. ______.
If this category is no more available, I would accept
category No. ______.
Please reserve _________ single room,
_________ twin.
Arrival date: __________.
Departure Date: __________.
Name: _______________________________________
Address: _______________________________________
_______________________________________
_______________________________________
_______________________________________
Date: _________ Signature: ______________
Please type or print.