dehne@scs.carleton.CA (Frank Dehne) (07/23/90)
FINAL PROGRAM
Second Canadian Conference in
Computational Geometry
August 6-10, 1990
University of Ottawa
Ottawa, Canada
Program Committee:
Jurek Czyzowicz (Univ. du Queb c Hull)
Frank Dehne (Carleton Univ.)
Eduardo Rivera Campo (M xico)
J rg-R diger Sack (Carleton Univ.)
Godfried Toussaint (McGill Univ.)
Jorge Urrutia (Univ. of Ottawa) (Chair)
Sponsored by:
Carleton University
University of Ottawa
Universit du Queb c Hull
--------------------------------------------------------
REGISTRATION FORM
Registration fee $ 60.00 Can
Registration fee includes: Sunday reception, Wednesday
informal reception, coffee breaks, and proceedings.
Name:
Affiliation:
Address:
Phone number:
E-mail:
PLEASE FILL OUT THE ABOVE REGISTRATION
FORM AND MAIL WITH CHEQUE TO
Second Canadian Conference in Computational
Geometry
c/o Jorge Urrutia
Department of Computer Science
University of Ottawa
Ottawa, Canada K1N 9B4
Tel.: (613) 564-5447
E-mail: scccg@uot.csi2
FAX: (613) 564-5045
--------------------------------------------------------
PROGRAM
All events, except Sunday reception and Wednesday informal
reception are held at the University of Ottawa, Fateaux Hall.
Sunday Evening, August 5, 1990
19:00 - Welcome Reception,
21:00 Novotel Hotel, Besserer Room.
Monday, August 6, 1990
Room 147, Fateaux.
8:45 Opening Address
9:00 INVITED TALK, Franco Preparata
(Univ. of Illinois at Urbana)
10:00-10:15 Break
Session 1A, Room 147, Fateaux
Point Sets 1
10:15 Maintaining the minimal distance of a
point set in less than linear time.
Michael Smid (Saarbr cken)
10:40 An optimal-time algorithm for ham-sandwich cuts
in the plane.
Chi-Yuan Lo (AT&T, Rutgers) and
William Steiger (Rutgers)
11:05 Computing a point in the center of a point set in
three dimensions.
N. Naor (Tel-Aviv) and M. Sharir (Tel-Aviv,
Courant)
Session 1B, Room 135, Fateaux
Implementation Issues 1
10:15 Geometry of bivariate splines.
W. Whiteley (Champlain Regional College)
10:40 A unified linear-space approach to geometric mini-
max problems.
T. Asano (Osaka), M.E. Houle (Kyushu), H. Imai
(Tokyo) and K. Imai (Tsuda College)
11:05 Accurate and efficient algorithms for proximity
problems.
P. Schorn (Z rich)
11:30-11:45 Break
Session 2A, Room 147, Fateaux
Point sets 2
11:45 Geometric clusterings.
V. Capoyleas (Rutgers), G. Rote (Waterloo) and G.
Woeginger (Graz)
12:10 Canonical cyclic orderings for point sets in the
plane.
A. Saalfeld (Bureau of the Census)
Session 2B, Room 135, Fateaux
Implementation Issues 2
11:45 Topology-oriented approach to robustness and its
applications to several Voronoi-diagram
algorithms.
K. Sugihara, Y. Ooishi and T. Imai (Tokyo)
12:10 Rounding face lattices in d dimensions.
V. Milenkovic (Harvard)
12:35 Lunch
Session 3A, Room 147, Fateaux
Separability 1
15:00 Separating bi-chromatic points by parallel lines.
T. Asano, J. Hersenberg, J. Pach, E. Sontang, D.
Souvaine and S. Suri
15:25 Separating convex sets on the plane.
J. Czyzowicz (Hull), E. Rivera Campo (M xico), J.
Urrutia (Ottawa) and J. Zaks (Haifa)
15:50 On the expected number of k-sets,
I. B r ny (Hungary, Yale) and W. Steiger (Rutgers)
Session 3B, Room 135, Fateaux
Parallel Algorithms
15:00 An optimal parallel L1 metric Voronoi diagram
algorithm.
Y. C. Wee (Korea) and S. Chaiken (State Univ. of
New York at Albany)
15:25 Efficient parallel algorithms on circular arcs.
L. Chen (Ohio State Univ)
15:50 Decomposing the star graph into disjoint cycles.
K. Qiu, H. Meijer and S. Akl (Queens Univ.)
16:15-16:30 Break
Session 4A, Room 147, Fateaux
Separability 2
16:30 Polygonal separators and digital shape
recognition.
B. Bhattacharya and T. Shermer (Simon Fraser)
16:55 A note on separation of plane convex sets.
E. Rivera Campo (M xico)
Session 4B, Room 135,Fateaux
Stabbing
16:30 Good splitters with applications to ray shooting.
R.B. Yeuda and S. Fogel (Technion, Haifa)
16:55 Maximal stabbing of segments in the plane.
B. Jones and Y. Kee (Saskatchewan)
Tuesday, August 7, 1990
9:00 INVITED TALK: Herbert Edelsbrunner
(Univ. of Illinois at Urbana)
10:00-10:15 Break
Session 5A, Room 147, Fateaux
Motion Planning 1
10:15 Watchman routes under limited visibility.
S. Ntafos (Texas)
10:40 Characterizing weak visibility polygons and
related problems.
S.K. Ghosh, A. Maheshwari (Bombay), S.P. Pal
(Bangalore), S. Saluja and C.E.V. Madhavan
(Bombay)
11:05 Improved combinatorial bounds and efficient
techniques for certain motion planning problems
with three degrees of freedom.
D. Halperin (Courant) and M. Sharir (Courant, Tel-
Aviv)
Session 5B, Room 135, Fateaux
Triangulations 1
10:15 Good triangulations in the plane.
T. K. Dey (Purdue)
10:40 A robust parallel triangulation and shelling
algorithm.
I. Beichl and F. Sullivan (Natl. Inst. of
Standards and Tech. Maryland)
11:15 Triangulating polygons with holes.
R. Bar-Yeuda and R. Grinwald (Technion)
11:30-11:45 Break
Session 6A, Room 147, Fateaux
Motion Planning 2
11:45 Optimal motion of covisible points among
obstacles in the plane.
J.B. Mitchell and E. L. Wynters (Cornell)
12:10 On coordinate motion through a maze.
J. Friedmann (Stanford), J. Hersenberg (DEC) and
J. Snoeynik (Stanford)
Session 6B, Room 135, Fateaux
Triangulations 2
11:45 The atomic strain tensor.
P.H. Mott, A.S. Argon (MIT) and U.W. Sutter
(Z rich)
12:10 Barycentric triangulations of generalized maps.
P. Lienhardt (Louis Pasteur Univ.)
12:35 Lunch
Session 7A, Room 147, Fateaux
Motion Planning and Order
15:00 Spherical orders, planar lattices and obstruction
graphs.
S. Foldes (Ecole Polytechnique, McGill)
15:25 Enumerating one-directional blocking relations
and embedding them in small areas on the plane.
W.P. Liu and I. Rival (Ottawa)
15:50 A new approach for drawing a hierarchical graph.
P. Eades, X. Lin (Queensland) and R. Tamassia
(Brown)
Session 7B, Room 135,Fateaux
Polygons 1
15:00 Dexterous rotations of polygons.
D. Rus (Cornell)
15:25 Structure detection for polygon decomposition.
M. Roussille, V. Bruy re and P. Dufour (Mons-
Hainau, Belgium)
15:50 Monotone pieces of chains.
V. Chandru (Purdue), V.T. Rajan (IBM Watson
Res.) and R. Swaminathan (Purdue)
16:15-16:30 Break
Session 8A, Room 147, Fateaux
Motion Planning 3
16:30 Planar conflict resolution for air traffic
control.
Y. Chen, M. Hsieh (U.S. California), A.
Inselberg(U.S. California, IBM) and H.Q. Lee
(NASA)
16:55 Optimal polygon placement by translation.
S.P. Pal, B. Dasgupta and C.E.V. Madhavan (Indian
Inst. of Science)
Session 8B, Room 135, Fateaux
Implementation Issues 3
16:30 An object oriented workbench for experimental
geometric computation.
P. Schorn (Z rich)
16:55 Free-form surface modeling using implicit patches.
B. Guo (Cornell)
Wednesday, August 8, 1990
9:00 PROBLEM SESSION
10:00-10:15 Break
Session 9A, Room 147, Fateaux
Polygons 2
10:15 Visibility in finitely oriented polygons.
V. Estivill-Castro and V. Rhaman (Waterloo)
10:40 An O(N log* N) time algorithm for covering simple
polygons with squares.
R. Bar-Yeuda and E. Ben-Chanoch (Technion)
11:05 Polyhedra: Faces are better than vertices.
L. S. Heat, P.K. Paripaty and J.W. Roach
(Virginia)
Session 9B, Room 135, Fateaux
Voronoi Diagrams 1
10:15 Finding constrained and weighted Voronoi
diagrams in the plane.
C.A. Wang (Memorial) and P.Y. Tsin (Windsor)
10:40 Fast algorithms for bounded Voronoi diagrams of
restricted polygons.
A. Lingas (Lund)
11:15 Voronoi diagrams over dynamic scenes.
T. Ross (W rzburg)
11:30-11:45 Break
Session 10A, Room 147, Fateaux
Polygons 3
11:45 An efficient divide-and-conquer approximation
algorithm for hyperrectangular partitions.
T. Gonzalez, M. Razzazi (Santa Barbara) and Si-
Qing Zheng (Louisiana)
12:10 On the complexity of shattering using
arrangements.
R. Freimer, J.S.B. Mitchel and C.D. Piatko
(Cornell)
Session 10B, Room 135, Fateaux
Voronoi Diagrams 2
11:45 Voronoi diagrams coming from discrete groups on
the plane.
M.L. Maz n and T. Recio (Cantalabria)
12:10 Finding geodesic Voronoi diagrams of points in
the presence of rectilinear barriers.
Y.H. Tsin (Windsor) and C.A. Wang (Memorial)
AFTERNOON FREE
Evening Informal Reception.
Time and place to be announced.
Thursday, August 9, 1990
9:00 INVITED TALK: Selim Akl
(Queen's University)
10:00-10:15 Break
Session 11A, Room 147, Fateaux
Visibility and Polygons
10:15 Minimal obscuring sets: the parallel view case.
N. Mouaward (McGill)
10:40 Linear-time algorithms for weakly-monotone
polygons.
P.J. Hefferman (Cornell)
11:05 An algorithm for recognizing palm polygons.
S. K. Ghosh, A. Maheshwari (TIFR, Bombay) and
S. P. Pal and C.E.V. Madhavan (Bangalore)
Session 11B, Room 135, Fateaux
Convex Hulls
10:15 An algorithm to find the faces of the convex
hull in higher dimensions.
W.M. Stewart (New Brunswick)
10:40 Numerical stability of a convex hull algorithm for
simple polygons.
J.W. Jaromczyk and G.H. Wasilkowski (Kentucky)
11:15 Las Vegas gift-wrapping is twice as fast.
R.A. Dwyer (North Carolina)
11:30-11:45 Break
Session 12A, Room 147, Fateaux
Visibility
11:45 Guarding convex sets on the plane.
J. Czyzowicz (Hull), E. Rivera-Campo (Mexico), J.
Urrutia (Ottawa) and J. Zaks (Haifa)
12:10 Optimum watchmen in spiral polygons.
B.J. Nilsson (Lund) and D. Wood (Waterloo)
Session 12B, Room 135, Fateaux
Voronoi Diagrams 3
11:45 Dynamic Voronoi diagrams and Delaunay
triangulations.
C.L. Bajaj and W.J. Bouma (Purdue)
12:10 An on-line construction of higher order Voronoi
diagrams and its randomized analysis.
J.D. Boissonnat, O. Devillers and M. Teillaud
(INRIA)
12:35 Lunch
Session 13A, Room 147, Fateaux
Ham-sandwich
15:00 Ham-sandwich sectioning of polygons.
M. Diaz (Johns Hopkins) and J. O'Rourke (Smith
College)
15:25 The convergence rate of the sandwich algorithm for
approximating convex figures in the plane.
G. Rote (Waterloo)
15:50 Cutting the volumes of convex polyhedra by a
plane.
I. Stojmenovic (Ottawa)
Session 13B, Room 135,Fateaux
Polygons 4
15:00 The complexity of minimum convex nested
polyhedra.
G. Das and D. Joseph (Wisconsin)
15:25 Constrained integer approximation to 2-d line
intersections.
S. Metha, M. Mukherjee and G. Nagy (Rensselaer)
15:50 Weighted 1-center problem in a simple polygon.
S. Kabadi (New Brunswick), Y.P. Aneja (Windsor)
and K.P.K. Nair (New Brunswick)
16:15-16:30 Break
Session 14A, Room 147, Fateaux
Steiner Trees
16:30 A reduced grid for rectilinear Steiner minimal
trees.
G.M. Shute (Minnesota)
16:55 Using partitioning and clustering techniques to
generate rectilinear Steiner trees.
L.L. Deneen and J.B. Dezell (Minnesota)
Session 14B, Room 135, Fateaux
Polygons 5
16:30 Circumscribing polygon of disjoint line segments.
A. Mirzain (York)
16:55 Minimum polygon covers of parallel line
segments.
H. Meijer and D. Rappaport (Queen's)
Friday, August 10, 1990
Session 15A, Room 147, Fateaux
Visibility 1
9:00 Link length of rectilinear watchman tours in grids.
E. Kranakis (Amsterdam), D. Krizank (Amsterdam,
Rochester) and L. Meertens (Amsterdam)
9:25 Computing polygonal chords and the farthest
visibility polygon.
T.C. Kao and G.D. Knott (Maryland)
10:50 Shortest paths, visibility, and optimization in
planar curvilinear objects.
E.A. Melissaratos and D. Souvaine (New
Brunswick)
Session 15B, Room 135, Fateaux
Implementations
9:00 An all round sweep algorithm for 2-dimensional
nearest-neighbor problems.
K. Hinrichs (Siegen), J. Nievergelt and P. Schorn
(Z rich)
9:25 Algorithms for semi-on-line updates on
decomposable problems.
M. Smid (Saarlanders)
10:50 Testing geometric objects.
K. Romanik and C. Smith (Maryland)
11:15-11:30 Break
Session 16A, Room 147, Fateaux
Visibility 2
11:30 Towards a general theory of visibility.
S. Schuierer (Freiburg), G.J.E. Rawlins (Indiana)
and D. Wood (Waterloo)
11:55 Minimum covers for grids and orthogonal
polygons by periscope guards.
L.P. Gewali (Nevada) and S. Ntafos (Texas)
Session 16B, Room 135, Fateaux
Circular arcs, TSP
11:30 Offsets of circular arc figures.
S. Whitesides and R.Y. Zhao (McGill)
11:55 Tree traveling salesman problem.
S.N. Kabadi (New Brunswick) and R.
Chandrasekaran (Texas)
11:55-12:10 Break
12:10- INVITED TALK : Godfried Toussaint.
13:10 (McGill University)
GENERAL INFORMATION
REGISTRATION
Please register in advance using the form provided. The
conference registration and information desk will be in the
Foyer of the Fateaux Hall at the University of Ottawa. It
will be
open as follows:
August 6 8:30-12:00 and 15:00-17:00
August 7 8:30-12:00
August 8 8:30-12:00
The registration fee includes a copy of the proceedings,
refreshments, Sunday and Wednesday receptions.
ACCOMMODATION
The following arrangements have been made for
accommodation for participants to the Second Canadian
Conference in Computational Geometry. Three
accommodation choices are available to conference
participants.
1) A block of 150 rooms has been reserved at the student
residences at the University of Ottawa .
2) A block of 50 rooms has been reserved at the
Journey's
End Hotel, situated within three blocks of the University of
Ottawa Campus, a five minute walk.
3) A block of 75 rooms has been reserved at the Novotel
Hotel, also within three blocks of campus.
The University of Ottawa Campus, the Journey's End and the
Novotel are located at the heart of the downtown core of
Ottawa. Participants wishing to take advantage of the
attractions offered by our city will find the location of all
of
the lodging places offered ideal.
The prices for accommodation ($CAN) (not including tax) are:
1) U. of O.: $28.35 (single); $37.80 (twin)
2) Journey's End: $70.88 (one person); $77.88
(two persons); $81.88 (three
persons); $85.88 (four persons)
3) Novotel: $90.00 (single, double or twin),
$105.00 (triple or quad)
Deadline for reservations:
The blocks of rooms will be held for the participants until
the following dates:
1) U. of O.: July 15, 1990
2) Journey's End: July 15, 1990
3) Novotel: July 16, 1990
After these dates, reservations will depend on
availability. Ottawa is a popular tourism center and during
August all downtown hotels are very busy. We strongly
advise you to reserve as soon as possible to avoid
problems obtaining accommodation. Reservations must be
arranged directly with the University or the hotel of your
choice. Please be sure to mention that you are attending the
Second Canadian Conference in Computational Geometry.
(1) University of Ottawa: Please contact the residence
office @ (613) 564-3463.
(2) Journey's End: 290 Rideau Street, Ottawa, Ont,
K1N 5Y3. Tels: 1-800-668-4200 and (613) 563-7511
(3) Novotel Ottawa: 33 Nicholas Street, Ottawa, Ont.
K1N 9M7. Tels: 1-800-221-4542 and (613) 230-3033,
FAX: (613) 230-7865
After this date, the rooms will be released and the regular
rates will apply to available rooms.
If you want to make other
accommodation arrangements, some other downtown
hotels are the Roxborough, 1-800-263-8967, $67
single/double; the Skyline, 1-800-268-1444, $120 single,
$130 double; the Delta, 1-800-268-1133, $125 single, $140
double. Please confirm these rates directly with the hotels.
Summer is also a popular camping time. The National Capital
Commission, (613)-239-5000, has a campground at the
Lebreton Flats, just 10 minutes walk from Parliament Hill.
Numerous campgrounds are at the outskirts of Ottawa. For
information call (613)-237-5158.
TRANSPORTATION
Ottawa International Airport on the south side of the city is
served by Air Canada, Canadian Airlines International, KLM,
Eastern, Pilgrim, City Express, First Air, and Wardair. An
airport shuttle, running every 30 minutes, provides
transportation to and from major hotels for about $6. A taxi
to the University of Ottawa and the downtown area costs about
$17.
INFORMATION ABOUT OTTAWA
The capital of Canada is a beautiful city with a metropolitan
area of 850,000 people. It is located at the confluence of
the Ottawa, Rideau and Gatineau rivers and the historic
Rideau Canal.
The Parliament Buildings stand on a cliff top
overlooking the Ottawa River. The Peace Tower observation
deck at 89.5 metres offers an excellent view of the Capital
Region, including the Ottawa Valley and the Gatineau Hills to
the north. In July and August the lawn of Parliament Hill is
the
scene of Changing the Guard at 10 a.m. and the Sound and
Light
show in the evening. The newly built Canadian Museum of
Civilization and National Gallery of Canada are nearby. Other
attractions available to visitors include the National Arts
Centre, Supreme Court, National Museum of Natural Sciences,
National Museum of Science and Technology, and National
Aviation Museum. Many parkways crisscross the city and add
to its warm and livable atmosphere.
The University of Ottawa is located in downtown Ottawa along
the east bank of the Rideau Canal. There are many places of
interest within walking distance of the campus, including
Parliament Hill, the National Gallery of Canada, the Currency
Museum, the War Museum, and the National Arts Centre, to
name but a few. Nearby is the Byward Market where a range of
restaurants sure to satisfy any taste and budget can be
found.
Evening entertainment can be found not only in the Market,
but also in downtown Hull, Qu bec (a fifteen minute walk from
the Byward Market across the Alexandra Bridge over the Ottawa
River ). The weather in the middle of August is usually warm,
with the average minimum 17oC and average maximum 26oC.
Occasional rain is possible.