From: formann@math.fu-berlin.de (Michael Formann)
Newsgroups: news.announce.conferences
Subject: 8th Annual ACM Symposium on Computational Geometry
Keywords: computational geometry, symposium, conference, program, registration
Date: 7 Apr 92 00:00:25 GMT
Expires: Fri, 12 Jun 1992 07:00:00 GMT
Organization: Free University of Berlin, Germany


                  8th  Annual  Symposium  on

                         COMPUTATIONAL

                           GEOMETRY



                           June  10-12,  1992


                         BerlinerCongressCenter

                             Berlin, Germany



                              Supported by

                    Deutsche Forschungsgemeinschaft
                                Land Berlin
                       Freie Universitaet Berlin
                             Queen Elizabeth 2
                            Deutsche Reichsbahn
                ACM Special Interest Groups for Graphics
                and for Automata and Computability Theory

______________________________________________________________________


                   Reservation and Registration Form

                           Hotel Reservation

            BerlinerCongressCenter/Spreehotel
            (Breakfast included, Shower and WC in room)
            Single            150 DM []
            Double            185 DM []
            Triple            220 DM []


            Charlottenburger Hof (Breakfast not included)
            For Students. 30 minutes distance from conference site.
                      With shower/WC            Without shower/WC
            Single            100 DM []
            Double            130 DM []                     90 DM []
            Triple            160 DM []                    120 DM []
            Quad                                           150 DM []


           Please check the appropriate room rate. Prices are per room.

            Arrival date and time     ___________________

            Departure date            ___________________


           First name  ...................Last name ....................

           Affiliation .................................................

                       .................................................

           Address .....................................................

                   .....................................................

                   .....................................................

           Phone .......................................................

           Email .......................................................

           Fax   .......................................................

           I want to share a room. []

           Roommate(s) .................................................

                 .......................................................

                 ........................................................

           Please find roommates for me. []

                  I am female.       []          I am male.         []

           Dietary Restriction:

                  Vegetarian         []          Kosher             []



______________________________________________________________________


                            Advance Registration

            Registration Fee               Before May 1     After May 1
            Regular                           200 DM []        250 DM []
            Student                           100 DM []        150 DM []

           The Student fee is subsidized, and it applies only to full time
           students with written certification by their advisors.  Partici-
           pants affiliated outside Western Europe, North America, New
           Zealand, Australia, and Japan also pay Student fee and, in ad-
           dition, may apply for financial support.

           The conference fee includes a copy of the proceedings, the re-
           ception, lunches, the excursion (with dinner), and coffee-breaks
           for Regulars as well as for Students. The students proceedings
           were provided by J.F.Lehmanns Med. Buchhandlung.

           Additional Proceedings will be available during the conference.
           Additional tickets for lunches and excursions are available and
           should be ordered in advance using this form.

           To register and hold your hotel reservation compute your total
           amount below and forward it to us:

            Hotel deposit                                      150   DM
            Registration                                   _________ DM
            Extra proceedings       _____  x 40 DM         _________ DM
            Extra lunch (per day)   _____  x 30 DM         _________ DM
            Extra excursion         _____  x 40 DM         _________ DM
            Public transport ticket ______ x 30 DM         _________ DM
            ____________________________________________________________

            Total amount                                   __________DM


           Preferably enclose a bank check made out in German marks
           (DM) and payable to "Computational Geometry".  Or trans-
           fer  to  account  "Computational  Geometry",  account  number
           8104450000 with Berliner Bank (German bank code number
           10020000). Alternatively, use Visa card.


           Payment method:    Bank Check []     Transfer []    Visa []

           Visa card #: __________________________Expiration date: _________

           Signature: ______________________________________________________



           Mail  your  reservation  and  registration  to  Susanne
           Schoettker. (Address see Conference Information)

           Cutoff date.  The block of rooms will be released on May 1,
           1992, and reservations cannot be guaranteed after that time.

           Cancellations. If you are not able to attend the conference, we
           need your cancellation not later than May 23. (Direct notice to
           Susanne Schoettker.)

           Method of payment in hotels. The BerlinerCongressCenter and
           the Spreehotel honor Visa, Eurocard,MasterCard, and American
           Express, you may also pay cash in German marks.


______________________________________________________________________



                           Conference  Information
           The 8th Annual ACM Symposium on Computational Geometry
           will be held in Berlin, Germany. Today Berlin is one of the most
           fascinating cities in the heart of Europe. Here the far-reaching
           social upheavals,which are currently taking place in Germany
           and Europe, are the most evident. Now the old links which for
           centuries connected Berlin with cities such as Paris, Warsaw,
           Prague, London, Vienna, St. Petersburg, and Moscow can be
           taken up again. The geographical and political situation pre-
           destines Berlin to increasingly become a forum for the mental
           convergence and for the strengthening and further development
           of democratic structures.
           Location:  The symposium will take place at the BerlinerCon-
           gressCenter (BCC, Maerkisches Ufer 54, Berlin-Mitte), which is
           located right in the heart of the city on the banks of the river
           Spree directly at the S- and U-Bahn station Jannowitzbruecke.
           We have reserved blocks of rooms from June 6 to June 14 in the
           BCC itself and also in the Spreehotel (Wallstrasse 59, Berlin-
           Mitte)  which  is  2  minutes  walking  distance  from  the  BCC.
           For students there is a cheaper hotel, Charlottenburger Hof
           (Stuttgarter Platz 14,  Berlin-Charlottenburg),  which is con-
           nected to the BCC by city railway (S-Bahn, 30 minutes).
           Weather:  Expect temperatures between 17 degrees C and 25 degrees C.
           In general, the climate in Berlinis moderately continental, rain
           is less likely in June, but a raincoat or an umbrella might be a
           good idea.
           Excursion and Dinner:   The excursion will be a boat-trip
           on board the ship "Schoeneberg", over the rivers and channels
           and passing the historical part of the city. During the excursion
           a tourist guide will give a brief review of architecture, history
           and the most recent events during the peaceful revolution in
           English.  The music band "Die neapolitanische Allianz" and
           an original "Berliner Buffet" dinner will guarantee a pleasant
           atmosphere.
           Currency:    The currency in Germany is "Deutsche Mark (DM)"
           (German marks). Approximate exchange rates:

           1 DM ~ US$ 0.61                1 DM ~ 80 Yen

           Organization:    The Symposium is organized by the Insti-
           tut fur Informatik, Fachbereich Mathematik, Freie Universit{t
           Berlin by Frank Wagner, Michael Formann, Susanne Schoettker,
           and Emo Welzl. We would like to thank Scot and Lina.


            Additional        Susanne Schoettker
            Information       Institut fur Informatik
                              Fachbereich Mathematik
                              Freie Universit{t Berlin
                              Arnimallee 2-6
                              W-1000 Berlin 33
                              Germany

            e-mail: geometry@tcs.fu-berlin.de
            Fax:    +49/30/8385913            Tel:    +49/30/8383771

______________________________________________________________________


                        Transportation Information

                         Overland  Transportation

           By train:  The Deutsche Reichsbahn has been selected as
           the official overland transportation for this symposium.
           In the last two years the quality and the frequency of the trains
           to and from Berlin has been tremendously increased.  At the
           time of our conference we will have the following situation:
           During   the   day   there  are   the   following   direct   Inter-
           City/EuroCity connections (mostly every two hours) to Berlin:

               -  Within Germany from Bonn, Bremen, Dresden, Frank-
                  furt/Main,   Freiburg,   Hamburg,   Karlsruhe,   Koeln,
                  Leipzig, Muenchen, Nuernberg, Wuerzburg, as well as from
                  several other cities;

               -  Czechoslovakia from Praha;

               -  Poland from Warszawa;

               -  Switzerland from Basel, Zurich, Bern and Geneve.

           Coming  from  Luxembourg  you  should  use  the  train  via
           Trier/Koeln, from where trains run every two hours to Berlin
           during the day.
           During the night there run trains (with sleeping cars) from
           Basel, Bern, Geneve, Muenchen, Stuttgart, Frankfurt/Main and
           Bonn as well as from Hoek van Holland (connection from Great
           Britain) via Utrecht, Paris via Aachen, Wien via Praha or via
           Linz/Passau; from Kobenhavn and Malmoe from eastern Europe
           (Moskva, Kiew, St. Petersburg, Sofia, Budapest, Bucuresti, and
           Warszawa). Coming from Belgium you may use the through
           coach connection from Oostende (connection from London) via
           Bruxelles to Berlin.
           The German railways offer attractive prices: From all over West
           Germany you can use the "Supersparpreis" if you depart from
           Berlin not earlier than Saturday 3:00 in the morning. Regard-
           less of the distance the ticket-price is DM 210,- in the first-class
           and DM 140,- in the second-class for a two-way ticket.
           If you travel in groups, the "Mitfahrerpreis" applies on railway
           lines of the "Deutsche Bundesbahn".  In this case every "Mit-
           fahrer" (fellow-passenger) gets 50% discount on the normal fare
           as well as on the "Supersparpreis".
           From your destination in Berlin (Hauptbahnhof or Lichtenberg)
           you will reach the Conference Center within some minutes by
           S-Bahn, this is included in your train ticket. Participants who
           stay not only for the conference and/or stay at the Charlot-
           tenburger Hof should order a public transport ticket through
           us.
           By car:  Due to the extremely hazardous situation during the
           rush-hours one should avoid driving by car. Note that the old
           motorways from the GDR have not yet been adapted to West
           German standards.


______________________________________________________________________


                         Overseas Transportation

           By ship:   QUEEN ELIZABETH 2 has been selected as
           the official overseas transportation for this symposium.
           Travel  to  or  from  the  symposium  aboard  QUEEN ELIZA-
           BETH 2 on a legendary jetlag free 5-day transatlantic crossing
           between New York and Southampton, England, and enjoy free
           one-way British Airways World Traveller Class air transporta-
           tion between London and any of 77 North American gateway
           cities:
           Choice of Sailing Dates        From/To

            June   1-6, 1992               New York/Southampton
            June 14-19, 1992               Southampton/New York

          Your Special ACM Symposium Rates:
          ____________________________________________________________
           Class             Category     Per Person Fare
           First                G             $3300
           Transatlantic        J             $2020
           (Both categories feature outside staterooms, 2 beds.  G-grade
           has bath; J-grade has shower).
           Included in Fares
           1. QE2 accommodations as booked,all on board meals and en-
           tertainment, and the services of an experienced cruisestaff.
           2. Transfer by rail and jetfoil/ship from Southampton to Berlin.
           3. Free one way British Airways (economy) air transportation
           between London and 77 North American gateway cities. Length
           of stay and other restrictions may apply.
           Not Included in Fares
           1. Port taxes and handling($150/pp). 2. Bar expenses. 3. Do-
           mestic travel between your home city and New York. 4. Op-
           tional pre- and post-conference hotelpackages (e.g. in London).
           5. Air travel between Berlin and London.
           By plane:   Berlin is easily reachable by plane from all over the
           world and has three international airports (Schoenefeld, Tegel,
           and Tempelhof) which are very well connected to the conference
           site by public transport.
           For Further Information And To Make Reservations
           We encourage you to make your reservations as soon as possible
           to guarantee availability. Call:

                  Travel Agents International
                  P.O. Box 3303
                  North Conway, NH 03860

                  (800) 537-3040 (USA outside of New Hampshire)
                  (800) 833-3037 (Canada)
                  (603) 356-5400 (otherwise)

           Travel Agents International offers optional conference packages
           to include transfers between ship/airport/hotel, and/or all air
           transportation to Berlin; early bookings provide significant sav-
           ings.


______________________________________________________________________


                                     Program

           Tuesday, June 9, 1992

           Reception 19:00-21:00, BerlinerCongressCenter


           Wednesday, June 10, 1992

           Session 1: 9:00-10:20

           Chair: Raimund Seidel, University of California at Berkeley

              9:00   A subexponential bound for linear programming,Jiri
                     Matousek, Charles University, Prague and Freie Uni-
                     versitaet Berlin, Micha Sharir, Tel Aviv University and
                     New York University,  Emo Welzl,  Freie Universit{t
                     Berlin
              9:20   A class  of  convex  programs  with  applications  to
                     computational geometry, Martin Dyer, University of
                     Leeds
              9:40   Linear optimization queries, Jiri Matousek, Charles
                     University, Prague and Freie Universitaet Berlin,
                     Otfried Schwarzkopf, Freie Universitaet Berlin and
                     Utrecht University

             10:00   Degenerate convex hulls in high dimensions without
                     extra storage, Guenter Rote, Technische Universitaet
                     Graz

            Coffee Break 10:20-10:40

            Session 2: 10:40-12:00

            Chair: Binay Bhattacharya, Simon Fraser University

            10:40    Optimal parallel algorithms for triangulated simple
                     polygons, John Hershberger, DEC Systems Research
                     Center, Palo Alto
            11:00    Incremental  flipping  works  for  regular  triangula-
                     tions, Herbert Edelsbrunner, N.R. Shah, University
                     of Illinois at Urbana-Champaign
            11:20    A cubic bound for conform Delaunay triangulations,
                     Herbert Edelsbrunner, Tiow Seng Tan, University of
                     Illinois at Urbana-Champaign
            11:40    An optimal parallel algorithm for detecting weak vis-
                     ibility of a simple polygon, Danny Z. Chen, Purdue
                     University

            Lunch Break 12:00-14:00

            Session 3: 14:00-15:40

            Chair: David Avis, McGill University

            14:00    Invited Lecture: Digital geometry, Azriel Rosen-
                     feld, University of Maryland
            15:00    An efficient approach to removing geometric degen-
                     eracies, Ioannis Emiris,John Canny, University of
                     California at Berkeley

            15:20    Numerical stability of algorithms for 2d Delaunay
                     triangulations and Voronoi diagrams, Steven For-
                     tune, AT&T Bell Laboratories, Murray Hill

            Coffee Break 15:40-16:00

            Session 4: 16:00-17:00

            Chair:   Kurt Mehlhorn, Max-Planck-Institut fur Informatik,
                     Saarbruecken

            16:00    Approximate decision algorithms for point set con-
                     gruence,  Paul J. Heffernan,  William Paterson Col-
                     lege,  Stefan  Schirra,  Max-Planck-Institut  fur  Infor-
                     matik, Saarbruecken
            16:20    Measuring the resemblance of polygonal curves, Hel-
                     mut Alt, Michael Godau, Freie Universitaet Berlin
            16:40    On dynamic Voronoi diagrams and the minimum
                     Hausdorff distance for point sets under Euclidean
                     motion in the plane, Daniel P. Huttenlocher, Cornell
                     University, Klara Kedem, Cornell University and Tel
                     Aviv University,Jon M. Kleinberg, Cornell University

            Excursion: 19:00-24:00
                     The excursion starts at 19:00 directly from the pier
                     "Jannowitzbruecke" in front of the BerlinerCongress-
                     Center. In case of bad weather, the excursion will
                     be shifted to Thursday.

            Thursday, June 11, 1992

            Session 5: 9:00-10:20

            Chair: Pankaj Agarwal, Duke University

              9:00   Diameter,  width,  closest  line  pair,  and  paramet-
                     ric searching, Bernard Chazelle, Princeton Univer-
                     sity, Herbert Edelsbrunner, University of Illinois at
                     Urbana-Champaign, Leonidas Guibas, DEC Systems
                     Research Center, Palo Alto and Stanford University,
                     Micha  Sharir, Tel  Aviv  University  and  New  York
                     University
              9:20   Incidence  and  nearest-neighbor  problems  for  lines
                     in 3-space, Marco Pellegrini, International Computer
                     Science Institute, Berkeley and King's College, London
              9:40   Computing  and  verifying  depth  orders,  Mark de
                     Berg,  Mark Overmars,  Utrecht University,  Otfried
                     Schwarzkopf, Freie  Universitaet  Berlin  and Utrecht
                     University
             10:00   Castles in air revisited, Boris Aronov, Polytechnic
                     University, New York, Micha Sharir, Tel Aviv Univer-
                     sity and New York University

            Coffee Break 10:20-10:40


            Session 6: 10:40-12:00

            Chair: William Steiger, Rutgers University

            10:40    Piercing convex sets, Noga Alon, Tel Aviv University
                     and Bellcore, Daniel J. Kleitman, MIT
            11:00    Computing the volume, counting integral points and
                     exponential sums, Alexander I. Barvinok, Academy
                     of Sciences, St. Petersburg
            11:20    There  is  a  universal topological  plane, Jacob  E.
                     Goodman,  City University  of  New  York, Richard
                     Pollack,  New  York  University,  Rephael  Wenger,
                     Ohio State University, Tudor Zamfirescu, Universitaet
                     Dortmund
            11:40    A linear time algorithm for testing the inscribability
                     of trivalent polyhedra, Michael B. Dillencourt, Uni-
                     versity of California, Irvine, Warren D. Smith, NEC
                     Research Institute, Princeton

            Lunch Break 12:00-14:00

            Session 7: 14:00-15:40

            Chair: David Avis, McGill University

            14:00    Invited   Lecture:    Computational  convexity:
                     Progress  and  problems  in  high-dimensional  com-
                     putational convexity, Peter Gritzmann, Universitaet
                     Trier, Victor Klee, University of Washington
            15:00    On Euclidean spanner graphs with small degree, Jef-
                     frey S. Salowe, University of Virginia
            15:20    New sparseness results on graph spanners, Barun
                     Chandra, University of Chicago, Gautam Das, Giri
                     Narasimhan, Memphis State University, Jose Soares,
                     University of Chicago

            Coffee Break 15:40-16:00

            Session 8: 16:00-17:00

            Chair: William Steiger, Rutgers University

            16:00    Coping  with  inconsistencies:   A new  approach  to
                     produce quality triangulations of polygonal domains
                     with holes, Elefterios A. Melissaratos, Diane L. Sou-
                     vaine, Rutgers University
            16:20    Quality mesh generation in three dimensions, Scott
                     A. Mitchell, Stephen A. Vavasis, Cornell University
            16:40    Triangulating  polygons  without  large  angles,  M.
                     Bern, Xerox PARC, Palo Alto,  D. Dobkin,  Prince-
                     ton University, D. Eppstein, University of California,
                     Irvine

            Business Meeting 17:20-19:00


            Friday, June 12, 1992

            Session 9: 9:00-10:20

            Chair: Pankaj Agarwal, Duke University

              9:00   Optical computational geometry, Y.B. Karasik, Tel
                     Aviv University, Micha Sharir, Tel Aviv University and
                     New York University
              9:20   Stable placements of spider robots, Jean-Daniel Bois-
                     sonnat,  INRIA Valbonne,  Olivier Devillers,  INRIA
                     Valbonne,  Leonbattista Donati,  INRIA  Valbonne,
                     Franco P. Preparata, Brown University
              9:40   A rational  rotation  method  for  robust  geometric
                     algorithms,  John Canny,  University  of  California
                     at  Berkeley,  Bruce  Donald, Gene  Ressler,  Cornell
                     University
             10:00   A framework  for  dynamic  graph  drawing,  Robert
                     F. Cohen, Brown University, Giuseppe Di Battista,
                     Universita  "La  Sapienza",  Roma,  Roberto  Tamas-
                     sia, Brown University, Ioannis G. Tollis, University of
                     Texas at Dallas, Paola Bertolazzi, IASI - CNR, Roma

            Coffee Break 10:20-10:40

            Session 10: 10:40-12:00

            Chair: Janos Pach, Hungarian Academy of Sciences

            10:40    How hard is halfspace range searching? Herve Bron-
                     nimann, Bernard Chazelle, Princeton University
            11:00    Range searching with efficient hierarchical cuttings,
                     Jiri Matousek, Charles University, Prague and Freie
                     Universitaet Berlin
            11:20    Ray shooting in convex polytopes, Otfried Schwarz-
                     kopf, Freie Universitaet Berlin and Utrecht University

            11:40    Minimum dissection of rectilinear region with arbi-
                     trary holes into rectangles,  Valeriu Soltan,  Alexei
                     Gorpinevich, Mathematical Institute, Academy of Sci-
                     ences of Moldova

            Lunch Break 12:00-14:00

            Session 11: 14:00-15:20

            Chair: Takeshi Tokuyama, IBM Japan

            14:00    Intersection  detection  and  separators  for  simple
                     polygons, David M. Mount, University of Maryland
                     at College Park
            14:20    Manhattonian proximity in a simple polygon, Rolf
                     Klein, Fernuniversitaet Hagen, Andrzej Lingas, Lund
                     University
            14:40    Finding k farthest pairs and k closest pairs/Farthest
                     bichromatic pairs for points in the plane, NaokiKa-
                     toh,  Kobe  University  of  Commerce,  Kazuo  Iwano,
                     IBM Japan
            15:00    An optimal algorithm for on-line closest-pair prob-
                     lem, Christian Schwarz, Michiel Smid, Max-Planck-
                     Institut fur Informatik, Saarbruecken, Jack Snoeyink,
                     University of British Columbia

            Coffee Break 15:20-15:40

            Session 12: 15:40-17:00

            Chair: Raimund Seidel, University of California at Berkeley

            15:40    On-line Steiner trees in the Euclidean plane, Noga
                     Alon, Tel Aviv University and Bellcore, Yossi Azar,
                     DEC Systems Research Center, Palo Alto
            16:00    A priori inequalities for the Euclidean Traveling
                     Salesman, Timothy Law Snyder, Georgetown Uni-
                     versity, J. Michael Steele, University of Pennsylvania
            16:20    Minkowski-type  theorems  and  least-squares  par-
                     titioning,  Franz Aurenhammer,  Freie  Universitaet
                     Berlin,  Friedrich  Hoffmann,  Technische Universit{t
                     Muenchen, Boris Aronov, Polytechnic University, New
                     York
            16:40    Determining contractibility of curves, Haijo Schip-
                     per, Groningen University



 _________________________________________________________________



                          Symposium information desk

           The information desk will be open:
            Tuesday                   18:00-20:00
            Wednesday to Friday        8:00-17:00
Newsgroups: news.announce.conferences