% LaTeX source to produce the STOC'94 programme (with registration
% and hotel registration forms), in camera-ready format suitable
% for printing on 4 x 9 inch panels.
%
% Conceived from scratch, to resemble previous year programme
% formats, most notably FOCS'92 and STOC'92.
%
%                           Danielle and Pierre McKenzie
%                           Gilles Brassard
%                           Mike Goodrich
%
%                           February 22, 1994
%
%

% Stolen by Larry Larmore to produce the STOC'95 program.
% Used again by Luc Longpre to produce the STOC'97 program.
% Modified by Lance Fortnow and Peter Shor so that the resulting
% program prints on A4 (European) size paper as well.

% Modified further by Peter Shor to be compatible with the
% automatic generation of the program.  There are more comments 
% right before the program macros.

\input epsf

\documentstyle[twocolumn]{article}
\clubpenalty 10000
\widowpenalty 10000
\topmargin -1.2cm
\oddsidemargin -1.2cm
\textheight 8.625in
\textwidth 7.26in
\columnseprule .2mm
\columnsep .5in
\parindent=0pt
\sloppy

\pagestyle{empty}

\begin{document}

\begin{center}
\begin{LARGE}
\vspace*{.5in}
\newfont{\bigman}{cmss17 scaled\magstep5}
{\bigman SoCG\,'99}\\
[.5in]\vfill

\centerline{\vbox to 2.5in {\vfil
\epsfysize=2.5in \epsfbox{gooddogs.ps} } }

\vspace*{.5in}

%
The 15$^{\mbox {\rm th}}$ Annual\\
ACM Symposium on\\
Computational Geometry\\ \vfill

Miami Beach, Florida\\
June 13\,--\,16, 1999\\ \vfill
{\large http://www.cs.miami.edu/events/SCG99}\\ \vfill
\end{LARGE}

{\large Sponsored by ACM SIGACT and SIGGRAPH\\[1mm] }
\vspace*{1.2cm}
\end{center}


\newpage

 %%%%%%%%%%%Actual programme begins%%%%%%%%%%%%%%%%%
 % The next few lines define commands to format the
 % list of talks, authors and affiliations.
 % While make_ci.perl only uses chairedsession, there
 % are also session environments (without chairs) and
 % plenary envirmnments available.  If you don't like 
 % format for the affiliations, you can get alternate 
 % ones by replacing the \by macro with the alternatives
 % below.
 %

 \newcommand{\talk}[2]{\boldmath \item[\bf #1]{\bf #2:}}
 \newcommand{\talknotitle}[1]{\item[\bf #1]}

 \newcommand{\by}[2]{#1, {\it #2\/}}

 % Use the following definition of \by instead if you don't have affiliations.
 % \newcommand{\by}[2]{#1}

 % Use the following definition of \by instead if you like parentheses around
 % your affiliations (also change $sep_affili from ; to , in make_ci.perl)
 % \newcommand{\by}[2]{#1 {\it (#2)\/}}

 % day is already a LaTeX command, so I'm using confday here
 \newcommand{\confday}[1]{\vspace{2mm}\centerline{\large\sc #1}\vspace{1mm}}

 \newenvironment{chairedsession}[2]{
    \vspace{2mm}
    {\centerline{\bf #1}}
    {\centerline{Chair: #2}}
    \begin{list}{$\circ$}
    {    \setlength{\parsep}{0mm}
         \setlength{\itemsep}{.2mm}
         \setlength{\leftmargin}{1cm}
         \setlength{\labelwidth}{1cm}
         \setlength{\parskip}{0mm}
         \setlength{\topsep}{0mm}
         \setlength{\labelsep}{2mm}
    }}{\end{list}}
 \newenvironment{plenary}[3]{
    \vspace{4mm}
    {\centerline{\bf #1}}
    {\centerline{Chair: #3}}
    {\centerline{\bf #2}}
    \begin{list}{$\circ$}
    {    \setlength{\parsep}{0mm}
         \setlength{\itemsep}{.2mm}
         \setlength{\leftmargin}{1cm}
         \setlength{\labelwidth}{1cm}
         \setlength{\parskip}{0mm}
         \setlength{\topsep}{0mm}
         \setlength{\labelsep}{2mm}
    }}{\end{list}\vspace{4mm}}
 \newenvironment{nochairplenary}[2]{
    \vspace{4mm}
    {\centerline{\bf #1}}
    {\centerline{\bf #2}}
    \begin{list}{$\circ$}
    {    \setlength{\parsep}{0mm}
         \setlength{\itemsep}{.2mm}
         \setlength{\leftmargin}{1cm}
         \setlength{\labelwidth}{1cm}
         \setlength{\parskip}{0mm}
         \setlength{\topsep}{0mm}
         \setlength{\labelsep}{2mm}
    }}{\end{list}\vspace{4mm}}
 \newenvironment{session}[1]{
    \vspace{2mm}
    {\centerline{\bf #1}}
    \begin{list}{$\circ$}
    {    \setlength{\parsep}{0mm}
         \setlength{\itemsep}{.2mm}
         \setlength{\leftmargin}{1cm}
         \setlength{\labelwidth}{1cm}
         \setlength{\parskip}{0mm}
         \setlength{\topsep}{0mm}
         \setlength{\labelsep}{1mm}
    }}{\end{list}}

 \newenvironment{social}[1]{
   \vspace{1mm}
    \begin{center}
    {\bf #1}
    \end{center}}{
   %\vspace{1mm}
    }
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%     The programme itself!   Semi-automatically generated.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\confday{Saturday, June 12}

\begin{social}{Cocktail Hour: 6:00 pm\,--\,8:00 pm}\end{social}

\confday{Sunday, June 13}

\begin{social}{Coffee: 10:30 am\,--\,11 am}\end{social}

\begin{session}{Session 1, Theoretical Track }{}

  \talk{11:00}{Sliver Exudation}
    \by{Siu-Wing Cheng}{Hong Kong U.\ of Science and Technology};
    \by{Tamal~K. Dey}{IIT Kharagpur};
    \by{Herbert Edelsbrunner}{UI Urbana-Champaign and Raindrop Geomagic};
    \by{Michael~A. Facello}{Raindrop Geomagic};
    \by{Shang-Hua Teng}{UI Urbana-Champaign}

  \talk{11:20}{The Path of a Triangulation}
    \by{Oswin Aichholzer}{Graz U. of Technology}

  \talk{11:40}{Edgewise Subdivision of a Simplex}
    \by{Herbert Edelsbrunner}{UI Urbana-Champaign and Raindrop Geomagic};
    \by{Daniel~R. Grayson}{UI Urbana-Champaign}

  \talk{12:00}{Efficient Algorithms for Maximum Regression Depth}
    \by{Marc van Kreveld}{Utrecht};
    \by{Joseph~S.B. Mitchell}{SUNY Stony Brook};
    \by{Peter Rousseeuw}{U. Instelling Antwerpen};
    \by{Micha Sharir}{Tel Aviv};
    \by{Jack Snoeyink, Bettina Speckmann}{U. British Columbia}

  \talk{12:20}{Spanning Trees Crossing Few Barriers}
    \by{Tetsuo Asano}{Japan Adv.\ Inst.\ of Science and Technology};
    \by{Mark de Berg}{Utrecht};
    \by{Otfried Cheong}{Hong Kong U.\ of Science and Technology};
    \by{Leonidas~J. Guibas}{Stanford};
    \by{Jack Snoeyink}{U. British Columbia};
    \by{Hisao Tamaki}{Meiji U.}

  \talk{12:40}{Generalizing Ham Sandwich Cuts to Equitable Subdivisions}
    \by{Sergei Bespamyatnikh, David Kirkpatrick, Jack Snoeyink}{U. British Columbia}

\end{session}

\begin{social}{Lunch: 1:00 pm\,--\,2:30 pm}\end{social}

\begin{nochairplenary}{Invited Talk}{}
  \talk{2:30}{The Complexity of Some Topological Algorithms}\by{ Joel Hass}{UC Davis} 
\end{nochairplenary}

\begin{social}{Coffee: 3:30 pm\,--\,4:00 pm}\end{social}

\newpage
\begin{session}{Session 2, Applied Track }{}

  \talk{4:00}{Topological Beam Tracing}
    \by{Steven Fortune}{Bell Laboratories}

  \talk{4:20}{A Geometric Approach to Computing Higher Order Form Factors}
    \by{Marco Pellegrini}{Istituto di Matematica Computazionale del CNR}

  \talk{4:40}{Geometric Pattern Matching: A Performance Study}
    \by{Martin Gavrilov, Piotr Indyk, Rajeev Motwani, Suresh Venkatasubramanian}{Stanford}

  \talk{5:00}{Empirical Design of Geometric Algorithms}
    \by{Karsten Weihe, Ulrik Brandes, Annegret Liebers}{U. Konstanz};
    \by{Matthias M\"uller-Hannemann}{TU-Berlin};
    \by{Dorothea Wagner, Thomas Willhalm}{U. Konstanz}

\end{session}

\begin{session}{Session 3, Theoretical Track }{}

  \talk{5:40}{Geometric Algorithms for Trap Design}
    \by{Robert-Paul Berretty}{Utrecht};
    \by{Ken Goldberg}{UC Berkeley};
    \by{Mark~H. Overmars, A.~Frank van der Stappen}{Utrecht}

  \talk{6:00}{Folding Flat Silhouettes and Wrapping Polyhedral Packages: New Results in Computational Origami}
    \by{Erik~D. Demaine, Martin~L. Demaine}{Waterloo};
    \by{Joseph~S.B. Mitchell}{SUNY Stony Brook}

  \talk{6:20}{The Table Layout Problem}
    \by{Richard~J. Anderson, Sumeet Sobti}{U. Washington}

\end{session}

\begin{social}{Business Meeting: 10:00 pm\,--\, midnight}\end{social}

\confday{Monday, June 14}

\begin{nochairplenary}{Invited Talk}{}
  \talk{10:00}{Geometry Meets Physics}\by{ Demetri Terzopoulos}
{U.\ Toronto}
\end{nochairplenary}

\begin{social}{Coffee: 11:00 am\,--\,11:20 am}\end{social}


\begin{session}{Session 4, Theoretical Track}{}

  \talk{11:20}{New Bounds on Crossing Numbers}
    \by{J\'anos Pach, Joel Spencer}{Courant NYU};
    \by{G\'eza T\'oth}{MIT and Hungarian Academy of Sciences}

  \talk{11:40}{The Complexity of the Union of $(\alpha, \beta)$-Covered Objects}
    \by{Alon Efrat}{Stanford}

  \talk{12:00}{Pipes, Cigars, and Kreplach: The Union of Minkowski Sums in Three Dimensions}
    \by{Pankaj~K. Agarwal}{Duke};
    \by{Micha Sharir}{Tel Aviv}

  \talk{12:20}{Polytopes in Arrangements}
    \by{Boris Aronov}{Polytechnic U.};
    \by{Tamal~K. Dey}{IIT Kharagpur}

\end{session}

\begin{social}{Lunch: 12:40 pm\,--\,2:30 pm}\end{social}

\begin{nochairplenary}{Invited Talk}{}
  \talk{2:30}{Crystal Symmetry}\by{ John Conway}
{Princeton}
\end{nochairplenary}

\begin{social}{Coffee: 3:30 pm\,--\,4:00 pm}\end{social}

\begin{session}{Session 5, Applied Track}{}

  \talk{4:00}{Controlled Perturbation for Arrangements of Polyhedral Surfaces with Application to Swept Volumes}
    \by{Sigal Raab}{Bar Ilan U.}

  \talk{4:20}{Motion Planning for a Rigid Body Using Random Networks on the Medial Axis of the Free Space}
    \by{Steven~A. Wilmarth, Nancy~M. Amato, Peter~F. Stiller}{Texas A\&M}

  \talk{4:40}{On Deletion in Delaunay Triangulations}
    \by{Olivier Devillers}{INRIA Sophia-Antipolis}

  \talk{5:00}{Crust and Anti-Crust: A One-Step Boundary and Skeleton Extraction Algorithm}
    \by{Christopher Gold}{Laval U.}

\end{session}

\vspace*{\fill}

\begin{session}{Session 6, Theoretical Track}{}

  \talk{5:30}{Curve Reconstruction: Connecting Dots with Good Reason}
    \by{Tamal~K. Dey}{IIT Kharagpur};
    \by{Kurt Mehlhorn, Edgar~A. Ramos}{MPI Saarbr\"ucken}

  \talk{5:50}{Curve Reconstruction, the Traveling Salesman Problem, and Menger's Theorem on Length}
    \by{Joachim Giesen}{ETH Z\"urich}

  \talk{6:10}{On Minimum Stars, Minimum Steiner Stars, and Maximum Matchings}
    \by{S\'andor~P. Fekete}{U.\ K\"oln};
    \by{Henk Meijer}{Queen's U.}

\end{session}

%%%%%%%% The following lines are intended to be used as templates
%%%%%%%% for social events.

\vspace*{\fill}

\begin{social}{Excursion} {\bf 7:00 pm}  
Buses leave
the hotel at 7:00pm, 8:00pm, and 9:00pm and leave Coconut Grove at 9:30pm,
10:30pm, and 11:30pm.
\end{social}

\newpage
\confday{Tuesday, June 15}

\begin{social}{Coffee: 10:30 am\,--\,11 am}\end{social}

\begin{session}{Session 7, Theoretical and Applied Tracks }{}

  \talk{11:00}{Hierarchical Vertical Decompositions, Ray Shooting, and Circular Arc Queries in Simple Polygons}
    \by{Siu-Wing Cheng, Otfried Cheong}{Hong Kong U.\ of Science and Technology};
    \by{Hazel Everett}{U. Qu\'ebec Montr\'eal};
    \by{Ren\'e van Oostrum}{Utrecht}

  \talk{11:20}{Kinetic Connectivity of Rectangles}
    \by{John Hershberger}{Mentor Graphics};
    \by{Subhash Suri}{Washington U.}

  \talk{11:40}{Lower Bounds for Kinetic Planar Subdivisions}
    \by{Pankaj~K. Agarwal, Julien Basch}{Duke};
    \by{Mark de Berg}{Utrecht};
    \by{Leonidas~J. Guibas}{Stanford};
    \by{John Hershberger}{Mentor Graphics}

  \talk{12:00}{Interval Methods for Kinetic Simulations}
    \by{Leonidas~J. Guibas, Menelaos~I. Karavelas}{Stanford}

  \talk{12:20}{H-Walk: Hierarchical Distance Computation for Moving Convex Bodies}
    \by{Leonidas~J. Guibas, David Hsu, Li Zhang}{Stanford}

\end{session}

\begin{social}{Lunch: 12:40 pm\,--\,2:30 pm}\end{social}

\begin{nochairplenary}{Invited Talk}{}
  \talk{2:30}{Computer Vision Methods in Surgery and Medicine}\by{ Eric Grimson}
{MIT}
\end{nochairplenary}

\begin{social}{Coffee: 3:30 pm\,--\,4:00 pm}\end{social}

\begin{session}{Session 8, Theoretical Track }{}

  \talk{4:00}{Stretchability of Star-like Pseudo-Visibility Graphs}
    \by{Ileana Streinu}{Smith College}

  \talk{4:20}{Visibility-Based Pursuit-Evasion in a Polygonal Room with a Door}
    \by{Jae-Ha Lee, Sung~Yong Shin, Kyung-Yong Chwa}{Korea Adv.\ Inst.\ of Science and Technology}

  \talk{4:40}{On Bisectors for Different Distance Functions}
    \by{Christian Icking, Rolf Klein, Lihong Ma}{FernUniversit\"at Hagen};
    \by{Stefan Nickel, Ansgar Wei{\ss}ler}{Universit\"at Kaiserslautern}

  \talk{5:00}{Small Distortion and Volume Preserving Embeddings for Planar and Euclidean Metrics}
    \by{Satish Rao}{NEC Research}

\end{session}

\begin{session}{Session 9, Applied Track}{}

  \talk{5:30}{Computing Roundness is Easy if the Set is Almost Round}
    \by{Pedro~A. Ramos}{Universidad Alcal\'a}

  \talk{5:50}{Smooth Paths in a Polygonal Channel}
    \by{David Lutterkort}{Purdue};
    \by{J\"org Peters}{U. Florida}

  \talk{6:10}{Determining an Optimal Penetration\\ among Weighted Regions in Two and Three Dimensions}
    \by{Danny~Z. Chen, Ovidiu Daescu, Xiaobo Hu, Xiaodong Wu, Jinhui Xu}{Notre Dame}

\end{session}

\vspace*{\fill}

\confday{Wednesday, June 16}

\begin{session}{Session 10, Applied Track }{}

  \talk{10:00}{Error-Bounded Regular Algebraic Spline Curves}
    \by{Chandrajit Bajaj}{U. Texas};
    \by{Guoliang Xu}{Chinese Academy of Sciences}

  \talk{10:20}{Efficient Exact Geometric Computation Made Easy}
    \by{C. Burnikel, R. Fleischer, K. Mehlhorn, S. Schirra}{MPI Saarbr\"ucken}

  \talk{10:40}{A Core Library for Robust Numeric and Geometric Computation}
    \by{V. Karamcheti, C. Li, I. Pechtchanski}{Courant NYU};
    \by{C. Yap}{NYU}

  \talk{11:00}{MAPC: A Library for Efficient and Exact Manipulation of Algebraic Points and Curves}
    \by{John Keyser, Tim Culver, Dinesh Manocha}{U. North Carolina};
    \by{Shankar Krishnan}{AT\&T Research Labs}

\end{session}

\begin{social}{Coffee: 11:20 am\,--\,11:40 am}\end{social}

\begin{session}{Session 11, Theoretical Track}{}

  \talk{11:40}{Efficient Algorithms for Line and Curve Segment Intersection Using Restricted Predicates}
    \by{Jean-Daniel Boissonat}{INRIA Sophia-Antipolis};
    \by{Jack Snoeyink}{U. British Columbia}

  \talk{12:00}{Approximation and Exact Algorithms for Minimum-Width Annuli and Shells}
    \by{Pankaj~K. Agarwal}{Duke};
    \by{Boris Aronov}{Polytechnic U.};
    \by{Sariel Har-Peled, Micha Sharir}{Tel Aviv}

  \talk{12:20}{On Range Reporting, Ray Shooting, and $k$-Level Construction}
    \by{Edgar~A. Ramos}{MPI Saarbr\"ucken}

  \talk{12:40}{Sharp Bounds on Geometric Permutations of Pairwise Disjoint Balls}
    \by{Shakhar Smorodinsky}{Tel Aviv};
    \by{Joseph~S.B. Mitchell}{SUNY Stony Brook};
    \by{Micha Sharir}{Tel Aviv}

\end{session}
%%%%%%%%%%%%%%%%%%%%%End of actual programme%%%%%%%%%%%%%%%%%%%%%

 \vspace{.5cm}

 \newcommand{\titre}[1]{\vfill\vspace{1mm}{\bf #1:}\par\nopagebreak}

\newpage
 {\centerline{\Large\bf General Information}}
 \vspace{2mm}
\titre{Location}

All conference events will take place at the Radisson Deauville Resort
on the island city of Miami Beach, Florida.  Miami Beach is about 15
minutes east of Miami International Airport (MIA) and the city of
Miami, and it is about 45 minutes south of Fort Lauderdale
International Airport (FLL).

\titre{Conference Registration}
The registration desk in the hotel lobby will the open Saturday, June
12 from 6:00pm to 8:00pm and during the conference meeting times.
Extra proceedings will be available at the registration desk for \$40
each.  Advanced registration is available until May 10.  If possible,
please use the registration/payment forms at the conference web page:
http://www.cs.miami.edu/events/SCG99.

\vspace{.2cm}

\begin{tabular}{lcc}
& {\bf Before May 10} & {\bf After May 10} \\
{\bf ACM Members} &  \$300 & \$375 \\
{\bf Non-members} &  \$375 & \$450 \\
{\bf ACM Members} &  \$165 & \$195
\end{tabular}

\vspace{.2cm}

If you do not have web access, please send the registration
fee along with 1)~name, 2)~institution,
3)~address, 4)~email address or telephone number, 5)~number of
excursion tickets (see below) at \$5/each (not included in
registration fee), 6)~ACM Membership number (if member) or declaration
of student status, and 7)~special needs (if any) to

\vspace{.2cm}

\begin{quote}
Victor J. Milenkovic\\
SCG'99 Local Arrangements Chair\\
University of Miami\\
Department of Math \& CS\\
P.O.~Box~249085\\
Coral Gables, FL~33124\\ 
\end{quote}

\vspace{.2cm}

Payment may be 
by check/money order, Master Card, Visa, or American Express.  
To pay by credit card, include amount of payment, credit card number,
expiration date, and signature.  Credit card payment can also be sent
by FAX to (305)~284-2848.  Call the Math \& CS office at
(305)~284-2575 to confirm receipt of FAX.

\newpage

\titre{Hotel Information}

\begin{quote}
Radisson Deauville Resort\\
6701 Collins Avenue\\
Miami Beach, FL 33141\\
Toll free: (800)~327-6656\\
Local: (305)~865-8511\\
FAX: (305)~865-8154\\
\end{quote}

A block of rooms will be held until May 10: \$98 single or double, \$113
triple or quad (plus 12.5\% tax).  Inform the hotel that
you are attending the Symposium on Computation Geometry,
June 13-16, abbreviation ``SCG'99''.  

The Airport Supershuttle from Miami International Airport
to the hotel is \$12 each way, and a taxi is about twice as much.

At the Radisson Deauville Resort, guests will enjoy everything that is
Miami Beach. Bask in the sun or stroll endless stretches of golden
beaches. Refresh your senses in the sparkling olympic sized swimming
pool rimmed with a hundred dancing fountains. Relax those tired
muscles in the rejuvenating Jacuzzi whirlpool spa. Enjoy the myriad of
exciting attractions the area has to offer.

Each of the Radisson Deauville Resort's 550 spacious guest rooms and
suites have been redecorated and refurbished. The decor is tropically
casual with oversized beds, walk-in closets, color television and
individual climate controlled air conditioning.  Each room has a
computer data-port and a refrigerator.  Oceanfront rooms have private
balconies. In addition to 700 feet of private beach, there are three
all weather tennis courts, a well equipped exercise room, solarium and
paddle boats on the beach.

\titre{Excursion}
South Beach is a blast, but it is not all South Florida has to offer.
On Monday night, buses will be provided to take conferees to and from
Coconut Grove, another popular night-spot for restaurants, bars,
shopping, and sight-seeing.

\titre{Other Services}
For child care, the concierge can refer you to a bonded baby sitting
service.  Walgreens across the street is open 24 hours, offering
sundries, a full service pharmacy, and an ATM.

\titre{Official Airline}
ACM is still in negotiation for airline discounts.
Please check the Web site (URL on front cover)
for the latest information.

\titre{Climate}
The Average Daily Temperature in Miami Beach for June is
75-88 F (24-31 C).  Pack short-sleeved shirts, shorts, and of course,
a swimming suit.

\titre{Things to Do}
{\bf South Beach} is a short bus or taxi ride away down Collins Avenue.  It
is famed for its pedestrian mall, restaurants, and nightlife, and its
restored vintage Art Deco hotels.

{\bf Vizcaya Museum and Gardens.} The 70-room house and gardens
overlook Biscayne Bay on a 30-acre tract that includes a native
hammock and more than 10 acres of formal gardens and fountains. In the
house, 34 rooms of paintings, sculpture, antique furniture, and other
decorative arts, are open to the public. 3251 S. Miami Ave.
(305) 250-9133.

\titre{Conference Chairs}
Victor Milenkovic (Local Arrangements)\\ 
{\tt vjm@cs.miami.edu}
\vspace{.2cm}


Marshall Bern (Theoretical Track)\\ 
{\tt bern@parc.xerox.com}
\vspace{.2cm}


John Canny (Applied Track)\\
{\tt jfc@cs.berkeley.edu}

\vspace{2.8in}

\vfill

%\titre{Local Committee}
%\titre{Conference Organization} 
%\titre{Publicity}
%\titre{Site Coordinator}
\end{document}



