(Message inbox:33) Return-Path: Received: from THEORY.CS.CMU.EDU by missing.link.cs.cmu.edu id ac25546; 23 Jul 96 8:16 EDT Received: from listserv.NoDak.edu by THEORY.CS.CMU.EDU id ai14115; 23 Jul 96 8:03:32 EDT Received: from listserv (134.129.111.8) by listserv.nodak.edu (LSMTP for Windows NT v1.0a) with SMTP id 8B6ECF20 ; Tue, 23 Jul 1996 6:59:51 -0500 Received: from LISTSERV.NODAK.EDU by LISTSERV.NODAK.EDU (LISTSERV-TCP/IP release 1.8b) with spool id 340665 for THEORYNT@LISTSERV.NODAK.EDU; Tue, 23 Jul 1996 06:59:27 -0500 Received: from listserv (134.129.111.8) by listserv.nodak.edu (LSMTP for Windows NT v1.0a) with SMTP id 7B305B50 ; Tue, 23 Jul 1996 6:59:24 -0500 Received: from LISTSERV.NODAK.EDU by LISTSERV.NODAK.EDU (LISTSERV-TCP/IP release 1.8b) with spool id 340563 for THEORY-A@LISTSERV.NODAK.EDU; Tue, 23 Jul 1996 06:59:04 -0500 Received: from pollux.usc.edu by listserv.nodak.edu (LSMTP for Windows NT v1.0a) with SMTP id 6E005980 ; Tue, 23 Jul 1996 6:59:02 -0500 Received: (from ierardi@localhost) by pollux.usc.edu (8.7.2/8.7.2/usc) id EAA23964 for theory-a@listserv.nodak.edu; Tue, 23 Jul 1996 04:58:59 -0700 (PDT) Approved-By: Doug Ierardi Approved-By: Theory-A - TheoryNet World-Wide Events Message-ID: <9607091712.AA17827@scs.carleton.ca> Date: Tue, 23 Jul 1996 04:58:58 PDT Reply-To: Theory-A - TheoryNet World-Wide Events , Frank Fiala Sender: TheoryNet List From: Frank Fiala Subject: CCCG'96 - Call for Participation Comments: To: Multiple recipients of list THEORY-A To: Local Distribution FINAL PROGRAM THE EIGHTH CANADIAN CONFERENCE ON COMPUTATIONAL GEOMETRY CCCG'96 August 12-15, 1996 Carleton University, Ottawa, Canada Program Committee: Evangelos Kranakis (Carleton) Program Co-chair Joerg-Ruediger Sack (Carleton) Program Co-chair Jurek Czyzowicz (U. du Quebec a Hull) Frank Fiala (Carleton) Anil Maheshwari (TIFR Bombay & Carleton) David Rappaport (Queen's) Jorge Urrutia (Ottawa) Organizing Committee: Frank Fiala (Carleton) Conference Chair Rosemary Carter (Carleton) Barbara Coleman (Carleton) Sponsored by: Carleton University CCCG '96 PROGRAM All events are held at Carleton University, Colonel By Drive, Ottawa. Registration takes place in the Foyer of the Tory Building and lectures are in Room 360, Tory Building. Lunches and the banquet are served in the Commons Building. Sunday Evening, August 11, 1996 19:00 - Registration and Welcome 21:00 Foyer, Tory Building Monday, August 12, 1996 Session M1, Room 360, Tory Building 8:20 Opening Address 8:30 INVITED TALK Robust proximity queries in implicit Voronoi diagrams Roberto Tamassia (Brown) - joint work with Giuseppe Liotta (Roma, Italy) and Franco P. Preparata (Brown) 9:20-9:30 Break Session M2 9:30 O-Convexity: Computing hulls, approximations, and orientation sets V. Martynchik, N. Metelski (Belarussian Academy of Sciences), and D. Wood (Hong Kong U. of Science & Technology) 9:50 Efficient algorithms for counting and reporting pairwise intersections between convex polygons Prosenjit Gupta (Max-Planck-Institut, Germany), Ravi Janardan (Minnesota), and Michiel Smid (King's College, UK) 10:10 Convex hulls of bounded curvature Jean-Daniel Boissonnat and Sylvain Lazard (INRIA, France) 10:30 Enclosing k points in the smallest axis parallel rectangle Michael Segal and Klara Kedem (Ben-Gurion U., Israel) 10:50-11:10 Break Session M3 11:10 Finding the set of all minimal nested convex polygons J. Bhadury (New Brunswick) and R. Chandrasekaran (Texas at Dallas) 11:30 Optimizing a corridor between two polygons with an application to polyhedral interpolation Gill Barequet (Tel-Aviv, Israel) and Barbara Wolfers (Freie U. Berlin, Germany) 11:50 Heuristics for the generation of random polygons Thomas Auer and Martin Held (U. Salzburg, Austria) 12:10 Orthogonal polygon reconstruction L. Jackson and S.K. Wismath (Lethbridge) 12:30-14:00 Lunch, 2nd Floor, Commons Building Session M4 14:00 Correcting topological defects of tessellations Dong Wang and John A. Goldak (Carleton) 14:20 Generating rooted triangulations with minimum degree four David Avis and Chiu Ming Kong (McGill) 14:40 On stable line segments in triangulations Andranik Mirzaian (York), Cao An Wang (Memorial), and Yin-Feng Xu (Xi'an Jiaotong U., China) 15:00 Diamonds are not a minimum weight triangulations best friend Prosenjit Bose (U. du Quebec a Trois-Rivieres), Luc Devroye (McGill), and Willian Evans (UBC) 15:20-15:50 Break Session M5 15:50 Stabbing information of a simple polygon Hazel Everett (U. du Quebec a Montreal), Ferran Hurtado, and Marc Noy (Politecnica de Catalunya, Spain) 16:10 K-transversals of parallel convex sets Nina Amenta (Xerox Park) 16:30 Fast stabbing of boxes in high dimensions Franck Nielsen (INRIA, France) 16:50 Shooter location problem Subhas C. Nandy, Krishnendu Mukhopadhyaya and Bhargab B. Bhattacharya (Indian Statistical Institute) Tuesday, August 13, 1996 Session Tu1, Room 360, Tory Building 8:30 INVITED TALK Computational geometry for interrogative visualization Chandrajit Bajaj (Purdue) 9:20-9:30 Break Session Tu2 9:30 An optimal algorithm for dynamic post-office problem in R21 and related problems Sergei N. Bespamyatnikh (Ural State U., Russia) 9:50 A topology oriented algorithm for the Voronoi diagram of polygons Toshiyuki Imai (U. Tokyo, Japan) 10:10 On non-smooth convex distance functions Ngoc-Minh L (Hagen, Germany) 10:30 Time-optimal proximity graph computations on enhanced meshes Stephan Olariu (Old Dominion), Ivan Stojmenovic (Ottawa), and Albert Y. Zomaya (Western Australia) 10:50-11:10 Break Session Tu3 11:10 Deforming curves in the plane for tethered-robot motion planning Susan Hert and Vladimir Lumelsky (Wisconsin-Madison) 11:30 Heuristic motion planning with movable obstacles Thomas Chadzelek, Jens Eckstein, and Elmar Schoemer (Saarland, Germany) 11:50 Viewing a set of spheres while moving on a linear flightpath Frank Follert (Saarland, Germany) 12:10 Approximating shortest paths in arrangments of lines Prosenjit Bose (U. du Quebec a Trois-Rivieres), William Evans, David Kirkpatrick, Michael McAllister, and Jack Snoeyink (UBC) 12:30-14:00 Lunch, 2nd Floor, Commons Building Session Tu4 14:00 Velocity planning for a robot moving along the shortest straight line path among moving obstacles K. Krithivasan, A. Rema (IIT Madras, India), Stefan Schirra, and P.I. Vijaykumar (Max-Planck-Institut, Germany) 14:20 Lower bounds for computing geometric spanners and approximate shortest paths Danny Z. Chen (Notre Dame), Gautam Das (Memphis), and Michiel Smid (King's College, UK) 14:40 On the reachable regions of chains Naixun Pei and Sue Whitesides (McGill) 15:00 Heuristic motion planning with many degrees of freedom Thomas Chadzelek, Jens Eckstein, and Elmar Schoemer (Saarland, Germany) 15:20-15:50 Break Session Tu5 15:50 Computing largest circles separating two sets of segments Jean-Daniel Boissonnat (INRIA, France), Jurek Czyzowicz (U. du Quebec a Hull), Olivier Devillers (INRIA, France), Jorge Urrutia (Ottawa), and Mariette Yvinec (URA CNRS, France) 16:10 On the permutations generated by rotational sweeps of planar point sets Hanspeter Bieri and Peter-Michael Schmidt (U. Bern, Switzerland) 16:30 Maximal length common non-intersecting paths Jurek Czyzowicz (U. du Quebec a Hull), Evangelos Kranakis, Danny Krizanc (Carleton), and Jorge Urrutia (Ottawa) 19:00 Banquet, Green Room, Commons Building, Carleton University Wednesday, August 14, 1996 Session W1, Room 360, Tory Building 8:30 Maintaining multiple levels of detail in the overlay of hierarchical subdivisions Paola Magillo and Leila Floriani (Genova, Italy) 8:50 Distance-based subdivision for translational LP containment Karen Daniels (Harvard and Miami) and Victor J. Milenkovic (Miami) 9:10 Variable resolution terrain surfaces E. Puppo (Genova, Italy) 9:30-9:50 Break Session W2 9:50 Generalizing halfspaces Eugene Fink (Carnegie Mellon) and Derick Wood (Hong Kong U. of Science & Technology) 10:10 Efficient algorithms for guarding or illuminating the surface of a polyhedral terrain Prosenjit Bose (U. du Quebec a Trois-Rivieres), David Kirkpatrick, and Zaiqing Li (UBC) 10:30 The surveillance of the walls of an art gallery Aldo Laurentini (Politecnico di Torino, Italy) 10:50-11:10 Break Session W3 11:10 On rectangle visibility graphs. III. External visibility and complexity Thomas C. Shermer (Simon Fraser) 11:30 Maintaining visibility of a polygon with a moving point of view Danny Z. Chen and Ovidiu Daescu (Notre Dame) 11:50 Visibility graph of a set of line sements: A dynamic sequential algorithm and its parallel version Yosser Atassi (CRIN-CNRS, France) 12:10 Dynamic algorithms for approximate neighbor searching Sergei N. Bespamyatnikh (Ural State U., Russia) 12:30-14:00 Lunch, 2nd Floor, Commons Building Session W4 14:00 Three-dimensional restricted-orientation convexity Eugene Fink (Carnegie Mellon) and Derick Wood (Hong Kong U. of Science & Technology) 14:20 Efficient algorithms for the smallest enclosing cylinder problem Elmar Schoemer, Juergen Sellen (Saarland, Germany), Marek Teichmann, and Chee Yap (Courant Institute, NYU) 14:40 On the Omega(n^4/3) weak lower bounds for some 3D geometric problems Binhai Zhu (Los Alamos N.L.) 15:00-15:20 Break Session W5 15:20 Business meeting followed by problem -17:20 session Thursday, August 15, 1996 Session Th1, Room 360, Tory Building 8:30 INVITED TALK Computational geometry impact potential: A business and industrial perspective Prabhakar Raghavan (IBM) 9:20-9:30 Break Session Th2 9:30 Probalistic algorithms for efficient grasping and fixturing Marek Teichmann (Courant Institute, NYU) 9:50 On a problem of immobilizing polygons Jurek Czyzowicz (U. du Quebec a Hull), Ivan Stojmenovic (Ottawa), and Tomasz Szymacha (Warsaw U., Poland) 10:10 Finding an o(n^2 logn) algorithm is sometimes hard Antonio Hernandez Barrera (Hiroshima, Japan) 10:30 Improved orthogonal drawings of 3-graphs Therese Biedl (Rutgers) 10:50-11:10 Break Session Th3 11:10 Algorithms on polygonal embeddings of graphs Leizhen Cai (Chinese U. of Hong Kong) 11:30 Optimal orthogonal drawings of connected plane graphs Therese Biedl (Rutgers) 11:50 Straight line embeddings of planar graphs on point sets Netzahualcoyotl Castaneda (Mexico) and Jorge Urrutia (Ottawa) 12:10 Extending rectangular range reporting with query sensitive analysis Robin Y. Flatland and Charles V. Stewart (Rensselaer Polytechnic Institute) 12:30-14:00 Lunch, 2nd Floor, Commons Building Session Th4 14:00 The complexity of rivers in triangulated terrains Mark de Berg (Utrecht, The Netherlands), Prosenjit Bose (U. du Quebec a Trois-Rivieres), Katrin Dobrint (Microsoft), Marc van Kreveld, Mark Overmars, Marko de Groot (Utrecht, The Netherlands), Thomas Roos (ETH Zurich, Switzerland), Jack Snoeyink, and Sidi Yu (UBC) 14:20 Computing the angularity tolerance Mark de Berg (Utrecht, The Netherlands), Henk Meijer (Queen's, Kingston), Mark Overmars (Utrecht, The Netherlands), and Gordon Wilfong (Bell Labs) 14:40 The complexity of illuminating polygons by alfa-flood-lights Jay Bagga (Ball State U., IN), Laxmi Gewali, and David Glasser (U. Nevada, Las Vegas) 15:00 End of the conference GENERAL INFORMATION CONFERENCE LOCATION CCCG'96 will be held at Carleton University, Ottawa, Ontario, Canada. Ottawa, the modern and cosmopolitan capital of Canada, takes its name >From the Algonquin Indian tribe, the Odawa. It is a metropolitan area of about one million people and is located at the confluence of the Ottawa, Rideau and Gatineau rivers and the historic Rideau Canal. It is a city of parks, pleasant driveways with bicycle paths, cross-country skiing (in winter), and of flowers (especially tulips in May). The Parliament Buildings stand on a cliff top overlooking the Ottawa River; highlights here include "Changing of the Guard" at 10 a.m. and the "Sound and Light" show in the evenings. Canada's capital boasts one of the finest collections of cultural attractions in the world and no visit would be complete without a visit to at least some of them. Twelve national museums, the best in English and French theatres, the NAC (National Arts Centre) orchestra, are among the world's finest. Other attractions include the Supreme Court and the National Library. The city is well-known for its lovely drives beside the river, canal and north into the Gatineau Hills. Much of Gatineau Park is wilderness but parts are devoted to outdoor recreation, including camping, swimming, fishing, and hiking. The weather in the middle of August is usually warm, with the average minimum 17oC and average maximum 26oC. Occasional rain is possible. The Carleton University campus is only 10 minute drive from Parliament. On the west, the campus is separated by the Rideau Canal from the Central Experimental Farm, with its botanical gardens, livestock, and Agricultural Museum. To the southeast is the Rideau River, bordered on the opposite bank by the pleasant woods and picnic grounds of Vincent Massey Park. For more information about Ottawa (weather, cultural activities, hotels, sight seeing, etc): http://www.tourottawa.org/ TRANSPORTATION Ottawa Macdonald-Cartier International Airport is located on the south side of the city. An airport shuttle, running every 30 minutes, provides transportation to and from major hotels for $9. A taxi to Carleton University costs about $15, to downtown, about $23. Travelling by car >From the airport, follow the Airport Parkway, which runs north and becomes Bronson Avenue when it crosses the Rideau River. Carleton University campus is immediately west of Bronson Avenue. To enter it, turn left on Sunnyside (the second set of trafic lights when traveling >From the airport). To reach downtown, continue northward. Carleton University is connected with the downtown area by a city bus Route 7, which operates from early morning until after midnight. Conference transportation will be provided from and to Embassy/Ramada hotels in the morning and evening. PASSPORTS AND VISAS Participants are advised to check their individual circumstances for entry into Canada. ACCOMMODATION The Carleton University Residences are the primary accommodation for the conference. They offer comfortable single or double rooms with shared facilities. There is no charge for children under two. The rates for Bed and Breakfast are: Single $37 / night, double $45 / night (plus taxes). Reservations must be made, mentioning CCCG'96, by contacting: Maria Neil Tour and Conference Centre 261 Stormont House Carleton University 1125 Colonel By Drive Ottawa, ON, K1S 5B6 Canada Tel: (613)-520-2600 Ext. 8408 Fax: (613)-520-3952 Email: mneil@ccs.carleton.ca We have also reserved blocks of rooms, at reduced rates, in three downtown hotels which are about a 10 minute drive from the campus. Please contact the hotel directly, mentioning CCCG'96 at Carleton University. Ramada Hotel & Suites 111 Cooper Street (close to the Rideau Canal) Ottawa, Canada K2P 2E3 Tel: 1-800-267-8378 or (613)-238-1331; Fax: (613)-230-2179; $75 single or double. Mention event # 6389. Cut off date for reservations is July 11. Embassy Hotel & Suites 25 Cartier Street (next to Ramada Hotel) Ottawa, Canada K2P 1J2 Tel: 1-800-661-5495 or (613)-237-2111; Fax:(613)-563-1353; $67 single; $74 double. Cut off date for reservations is July 11. Days Inn - Ottawa City Center 123 Metcalfe Street Ottawa, Canada K1P 5L9 Tel: 1-800-DAYS INN or (613)-237-9300; Fax:(613)-237-2163; $60 single; $65 double. If you want to make other accommodation arrangements, you might contact the Canada's Capital Information Centre for help, tel: 1-800-465-1867 or (613)-239-5000. 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. REGISTRATION Please register in advance using the form provided. Registration rates increase after July 12, 1996. The conference registration and information desk will be in the Foyer of the Tory Building at Carleton University. It will be open as follows: August 11 19:00-21:00 August 12-14 8:00-11:30 and 14:30-16:30 August 15 8:00-12:00 The registration fee includes a copy of the proceedings, refreshments, four lunches, banquet, and social events. Students may register for a reduced fee. FURTHER INFORMATION For further information, contact CCCG'96 School of Computer Science Carleton University 1125 Colonel By Drive Ottawa, ON, K1S 5B6 Canada Tel: (613)-520-4333 or (613) 520-4330 Fax: (613)-520-4334 Email: cccg96_local@scs.carleton.ca _____________________________________________________________ CCCG'96 REGISTRATION FORM CDN$ US$ __ Regular registration 250 185 __ Late registration (after 12 July) 300 225 __ Full-time student registration 175 130 __ Additional lunch (CDN$ 7.50 each) ______________ __ Additional banquet (CDN$ 40 each) ______________ __ Extra proceedings (CDN$ 50 each) ______________ TOTAL ______________ Registration fee includes: a copy of the proceedings, refreshments, four lunches, banquet, and social events. Additional proceedings can be purchased during the conference. Name: ___________________________________________________ Affiliation:_____________________________________________ Address:_________________________________________________ _________________________________________________________ _________________________________________________________ Phone number:_______________________ E-mail:_________________________ Dietary restrictions: ( ) kosher ( ) vegetarian Please fill out the above registration form and mail with cheque to CCCG '96 School of Computer Science Carleton University 1125 Colonel By Drive Ottawa, Canada K1S 5B6 Tel.: (613)-520-4333 or(613)-520-4330 Fax: (613)-520-4334 Email: cccg96_local@scs.carleton.ca