From owner-theorynt@LISTSERV.NODAK.EDU Tue Jun 10 13:25:01 1997 Received: from Sunburn.Stanford.EDU (Sunburn.Stanford.EDU [171.64.67.178]) by robotics.Stanford.EDU (8.8.5/8.8.5) with ESMTP id NAA09495 for ; Tue, 10 Jun 1997 13:25:01 -0700 (PDT) Received: from listserv.nodak.edu (listserv.NoDak.edu [134.129.111.8]) by Sunburn.Stanford.EDU (8.8.4/8.8.4) with ESMTP id NAA10440; Tue, 10 Jun 1997 13:14:52 -0700 (PDT) Received: from listserv (134.129.111.8) by listserv.nodak.edu (LSMTP for Windows NT v1.1a) with SMTP id <0.3B138480@listserv.nodak.edu>; Tue, 10 Jun 1997 15:09:02 -0500 Received: from LISTSERV.NODAK.EDU by LISTSERV.NODAK.EDU (LISTSERV-TCP/IP release 1.8c) with spool id 704200 for THEORYNT@LISTSERV.NODAK.EDU; Tue, 10 Jun 1997 15:08:57 -0500 Received: from listserv (134.129.111.8) by listserv.nodak.edu (LSMTP for Windows NT v1.1a) with SMTP id <0.377B4290@listserv.nodak.edu>; Tue, 10 Jun 1997 15:08:56 -0500 Received: from LISTSERV.NODAK.EDU by LISTSERV.NODAK.EDU (LISTSERV-TCP/IP release 1.8c) with spool id 704187 for THEORY-A@LISTSERV.NODAK.EDU; Tue, 10 Jun 1997 15:08:55 -0500 Received: from usc.edu by listserv.nodak.edu (LSMTP for Windows NT v1.1a) with SMTP id <0.3556DBF0@listserv.nodak.edu>; Tue, 10 Jun 1997 15:08:52 -0500 Received: from pollux2.usc.edu (pollux2.usc.edu [128.125.253.192]) by usc.edu (8.8.4/8.7.2/usc) with ESMTP id NAA02930 for ; Tue, 10 Jun 1997 13:08:51 -0700 (PDT) Received: (from ierardi@localhost) by pollux2.usc.edu (8.8.4/8.8.4/usc) id NAA04435 for theory-a@listserv.nodak.edu; Tue, 10 Jun 1997 13:08:20 -0700 (PDT) X-Sender: daver@gauss Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Approved-By: Doug Ierardi Approved-By: Theory-A - TheoryNet World-Wide Events Message-ID: Date: Tue, 10 Jun 1997 13:08:20 PDT Reply-To: Theory-A - TheoryNet World-Wide Events , David Rappaport Sender: TheoryNet List From: David Rappaport Subject: CCCG '97 Call for Participation Comments: To: THEORY-A@LISTSERV.NODAK.EDU To: THEORYNT@LISTSERV.NODAK.EDU Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from QUOTED-PRINTABLE to 8bit by robotics.Stanford.EDU id NAA09495 X-Mozilla-Status: 0001 Content-Length: 14937 The Ninth Canadian Conference on Computational Geometry Queen's University, Kingston, Ontario, CANADA August 11-14, 1997 Program and Registration Information. You can access all of the following information, and much more, by visiting our web site at: http://www.qucis.queensu.ca/cccg97/index.html A registration form is included at the end of this file. Program Committee David Avis, McGill University Prosenjit Bose, Universite du Quebec a Trois-Rivieres Henk Meijer, Queen's University David Rappaport, Queen's University (Conference Organizer) Tom Shermer, Simon Fraser University James Stewart, University of Toronto Cao an Wang, Memorial University Local Arrangements: S.G. Akl, N. Barker, R. Dawes, H. Meijer, D. Rappaport Invited Speakers J. Akiyama -- Tokai University W. Haken -- University of Illinois E. Fiume -- University of Toronto J. Mitchell -- SUNY Stony Brook PROGRAM Sunday, August 10 18:00-21:00 Reception and Registration at the University Club Monday, August 11 All technical sessions will be held in room 205 of Walter Light Hall. 08:45 Opening remarks Session MON1 09:00 Vertex pi-lights for monotone mountains Joseph O'Rourke 09:20 Constructing piecewise linear homeomorphisms of polygons with holes Rephael Wenger, Mark Babikov and Diane L. Souvaine 09:40 On folding rulers in regular polygons Sue Whitesides and Naixun Pei 09:40 On the number of internal and external visibility edges of polygons Jorge Urrutia 10:20 Break Session MON2 10:40 On a partition of point sets into convex polygons Masatsugu Urabe. 11:00 Domino tilings and two-by-two squares Jurek Czyzowicz, Evangelos Kranakis and Jorge Urrutia 11:20 Covering a set of points by two axis-parallel boxes Michael Segal and Sergei Bespamyatnikh 11:40 Encoding a triangulation as a permutation of its point set Markus O. Denny and Christian A. Sohler 12:00-14:00 Lunch Session MON3 Invited Talk 14:00 TBA Wolfgang Haken 15:00-15:10 Break Session MON4 15:10 A note on the tree graph of a set of points in the plane Eduardo Rivera-Campo and Virginia Urrutia-Galicia 15:30 A straight-line embedding of two or more rooted trees in the plane M. Kano 15:50 A balanced partition of points in the plane and tree embedding problems Atsushi Kaneko 16:10 Parallel algorithms for longest increasing chains in the plane and related problems Kevin S. Klenk, Mikhail J. Atallah and Danny Z. Chen 16:30-16:45 Break Session MON5 16:45 Open Problem Session. Tuesday, August 12. Session TUE1 09:00 Planar segment visibility graphs H. Everett, C. T. Hoàng, K. Kilakos and M. Noy 09:20 The visibility graph contains a bounded-degree spanner Gautam Das 09:40 Contracted visibility graphs of line segments L. Gewali, J. Bagga, S. Dey, J. Emert and J. McGrew 10:00 Geometric matching problem of disjoint compact convex sets by line segments Kiyoshi Hosono and Katsumi Matsuda 10:20-10:40 Break Session TUE2 10:40 Handling rotations in the placement of curved convex polygons François Rebufat 11:00 Almost optimal on-line search in unknown streets Evangelos Kranakis and Anthony Spatharis 11:20 An on-line algorithm for exploring an unknown polygonal environment by a point robot S. K. Ghosh and J. W. Burdick 11:40 Understanding discrete visibility and related approximation algorithms S. K. Ghosh and J. W. Burdick 12:00-14:00 Lunch Session TUE3 Invited Talk 14:00 Why Taro can do geometry Jin Akiyama 15:00-15:10 Break Session TUE4 15:10 A quantum-searching application note Ngoc-Minh Lê 15:30 Some methods to determine the sign of a long integer from its remainders Toshiyuki Imai 15:50 A quadratic non-standard arithmetic Dominique Michelucci 09:40 Analysis of a class of k-dimensional merge procedures, with an application to 2D Delaunay triangulation in expected linear time after two-directional sorting Jean-Michel Moreau and Christophe Lemaire 16:30-16:45 Break 16:45 Business Meeting 18:30 Banquet at the Kingston Yacht Club. Wednesday, August 13 Session WED1 09:00 On-line searching in geometric trees Sven Schuierer 09:20 Biased search and k-point clustering Binay K. Bhattacharya and Hossam ElGindy 9:40 Walking in the visibility complex with applications to visibility polygons and dynamic visibility Stéphane Rivière 10:00 The 3D visibility complex: A unified data-structure for global visibility of scenes of polygons and smooth objects Fredo Durand, George Drettakis and Claude Puech 10:20-10:40 Break Session WED2 10:40 The width of a convex set on the sphere C.I. Grima, F. J. Cobos, J. C. Dana and A. Márquez 11:00 Diameter of a set on the cylinder C.I. Grima, F. J. Cobos, J. C. Dana and A. Márquez 11:30 Testing roundness of a polytope and related problems Artur Fuhrmann 11:55 On hardness of roundness calculation Sergey P. Tarasov 12:00-14:00 Lunch Session WED3 Invited Talk 14:00 Applied geometry for computer graphics Eugene Fiume 15:00-15:10 Break Session WED4 15:10 Reconstruction of 3-D surface object from its pieces Göktürk Üçoluk and Hakki Toroslu 15:30 Sampling and reconstructing manifolds using alpha-shapes Fausto Bernardini and Chandrajit L. Bajaj 15:50 Periodic B-spline surface skinning of anatomic shapes Fabrice Jaillet, Behzad Shariat and Denis Vandorpe 16:10 Shape reconstruction using skeleton-based implicit surface Serge Pontier, Behzad Shariat and Denis Vandorpe 16:30-16:45 Break Session WED5 Chair 16:45 Dynamizing domination queries in 2-dimensions: The paper stabbing problem revisited Michael G. Lamoureux, J. D. Horton and Bradford G. Nickerson 17:05 Fast piercing of iso-oriented rectangles Christos Makris and Athanasios Tsakalidis 17:25 Shooter location problems revisited Binhai Zhu and Cao An Wang Thursday, August 14 Session THU1 Invited Talk 09:00 Approximation algorithms for geometric optimization problems Joseph Mitchell Session THU2 10:00 Label placement by maximum independent set in rectangles Pankaj K. Agarwal, Mark van Kreveld and Subhash Suri 10:20 Easy triangle strips for TIN terrain models Jack Snoeyink and Bettina Speckmann 10:40 Partitioning algorithms for transportation graphs and their applications to routing Doug Ierardi and Cavit Aydin 11:00-11:20 Break Session THU3 11:20 Stability of Voronoi neighborship under perturbations of the sites Frank Weller 11:40 An iterative algorithm for the determination of Voronoi vertices in polygonal and non-polygonal domains François Anton and Chrisopher Gold 12:00 Some tools for modeling and analysis of surfaces Jürgen Wirtgen, Carsten Dorgerloh, Jens Lüssem, and Morakot Pilouk 12:20 An increasing-circle sweep-algorithm to construct the Delaunay diagram in the plane D. Schmitt, B. Adam, P. Kauffmann and J.-C. Spehner End of conference. ACCOMMODATION Please note that the Canadian Olympic Training Regatta (CORK) will be held in Kingston from August 11 to August 24. This event draws thousands of visitors to the city and hotel rooms are consequently in great demand at that time. Reservations are STRONGLY ADVISED. CCCG '97 has arranged for a total of one hundred rooms in the conference hotels and residence, but these rooms will be released if not reserved by July 11. Quoted rates are in Canadian funds and do not include taxes. The principal residence for the Conference will be the Victoria Hall student residence (Queen's Crescent). 50 rooms have been reserved. For those who prefer hotel accommodation, 25 rooms have been reserved at the Ramada Inn. As well, a few rooms have been reserved in two of Kingston's bed & breakfast inns. These rooms will be released on July 12, if not taken up by then. Please state that you are part of the CCCG'97 conference when reserving your rooms. Some other hotels are also listed below for your convenience. Quoted rates are in Canadian funds (currently a Canadian dollar is worth about 0.75 U.S. dollars) and do not include taxes unless otherwise stated. Conference participants should contact residence or hotels directly, not through the Conference secretariat. If parking is required, please specify with your Victoria Hall reservation. Mention you are with the CCCG'97 conference Victoria Hall, Queen's Crescent, Kingston, Ont., Canada, K7L 3N6. All rooms $45.75 (tax included). (Double occupancy $55.46). Parking available - ask when reserving room. Breakfast included. Vegetarian meals available. Washrooms private but not in rooms. For reservations call 613-545-2223. FAX 613-545-6624. Please mention CCCG'97. E-mail: johnson@post.queensu.ca. Hochelaga Inn, 24 Sydenham St. South, Kingston, Ont., Canada, K7L 3G9. B&B rooms range from $90 to $120. Parking available. Breakfast included. Five minutes walk to campus. Phone or FAX 613-549-5534. Hotel Belvedere, 141 King St. East, Kingston, Ont., Canada, K7L 2Z9. Rooms range from $99 to $130. Parking available. Breakfast included. Ten minutes walk from campus. For reservations call 613-548-1565 or 1-800-559-0584. FAX 613-546-4692. Ramada Inn, 1 Johnson St., Kingston, Ont., Canada, K7L 5H7. Rates range from $99-$130. Indoor pool and sauna. All rooms a lake view. Coffee maker, mini-bar, and iron/board in each room. Fifteen minutes walk to campus. Reservations: 613-549-8100 or 1-800-272-6232. FAX: 613-547-3241. REGISTRATION INFORMATION Please pre-register using the form provided. Registration rates increase after July 11, 1997. Payment may be made by Visa or MasterCard (note that credit card payments will be processed in Canadian funds); payment may also be made by personal cheque in Canadian dollars drawn on a Canadian bank or by international money order or bank draft, which must be for Canadian dollars drawn on a Canadian bank. Cheques in other currencies cannot be accepted due to the excessive collection fees levied during the currency conversion process. Cheques and money orders should be made payable to Queen's University/CCCG'97. Fees are refundable, minus a $30 cancellation charge, provided a written request is received by the Conference Office no later than August 4, 1997. Full payment must accompany the registration form. Persons registering after July 11 may not receive the proceedings until after the workshop. Registration packages will be distributed at the Welcoming Reception. Hospitality information and late registration will also be available at the reception. After the workshop begins registration and information will be available at the technical session site in Walter Light Hall. The full registration fee includes a copy of the workshop proceedings, refreshments, the welcoming reception, admission to all invited talks and technical sessions and the conference banquet. A student registration fee is available which includes all items mentioned except the banquet. (Student registrations must be signed by the student's supervisor.) The one day registration fee includes neither a copy of the proceedings, nor a banquet ticket. Accompanying persons are welcome to attend all social functions. Additional banquet tickets may be purchased in advance or at the conference. Refunds for banquet tickets cannot be made after August 4, 1997. REGISTRATION FORM ---------------- cut here -------------------------------------------------- CCCG '97 CCCG '97 CCCG '97 CCCG '97 CCCG '97 CCCG '97 Registration Form MAIL OR FAX TO: CCCG '97, Department of Computing and Info. Science, Queen's University, Kingston, Ont., Canada, K7L 3N6 FAX 613-545-6513 Note: All prices are quoted in Canadian dollars. Carefully read the instructions before you complete the registration form. Type or print clearly: First Name_____________________________Last Name______________________________ Affiliation___________________________________________________________________ Street Address________________________________________________________________ City__________________________State or Province_______________________________ Country________________________Postal or Zip Code_____________________________ Telephone________________FAX________________Email____________________________ Supervisor's signature for student registration_______________________________ Registration fees (taxes included). Please circle items. By July 11 After July 11 Regular $200 $250 Student $120 $150 One-day $150 $150 Extra proceedings $20 $20 (subject to availability) Quantity ___ Extra banquet $40 $40 tickets Quantity ___ TOTAL AMOUNT ______________________________________$CAN Banquet: Regular___ Vegetarian___ Other(please specify)______________________ Registrants living outside Canada can apply for tax refunds. (Forms are available at the conference.) G.S.T. registration number is R107 868 705. Mode of payment: __VISA __MasterCard __cheque __money order __bank draft Credit card number__________________________________Expiry Date__________ I hereby authorize Queen's University to debit my credit card for the amount above. Signature of cardholder__________________________________________________ Make your cheque/money order/bank draft payable to Queen's University/CCCG '97. Please refer to the section titled REGISTRATION INFORMATION for more details.