\documentclass[10pt]{article}
\usepackage{latexsym}
%\setlength{\pageheight}{22.8cm}
%\setlength{\pagewidth}{10.3cm}
\setlength{\textheight}{21.2cm}
\setlength{\textwidth}{8.7cm}
\setlength{\footskip}{0cm}
\setlength{\topmargin}{1cm}
\setlength{\headheight}{0cm}
\setlength{\headsep}{0cm}
\setlength{\oddsidemargin}{0cm}
\setlength{\evensidemargin}{0cm}
\pagestyle{empty}
\setlength{\parskip}{0.2cm}
\parindent = 0cm
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% Begin: Stuff needed for formatting the technical program
%%% Courtesy previous STOCs/FOCs
\def\day#1{
\vspace{\baselineskip}
{\noindent\large \bf #1}
}
\newcommand{\talk}[2]{\boldmath \item[\bf #1]{\bf #2:}}
\newcommand{\talknotitle}[1]{\item[\bf #1]}
\newcommand{\talknocolon}[2]{\boldmath \item[\bf #1]{\bf #2}}
%\newcommand{\by}[2]{#1, {\it #2\/}}
% Use the following definition of \by instead if you don't have affiliations.
\newcommand{\byby}[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)\/}}
\def\Chaired#1#2{{#1, #2}}
\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{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 following lines are intended to be used as templates
%%%%%%%% for formatting dates and social events.
%{\centerline{\normalsize\bf SATURDAY, MAY 3, 1997}}
%
%\begin{social}{Reception: 7 pm\,--\,10 pm}\end{social}
%
%\vspace{3mm}
%{\centerline{\normalsize\bf SUNDAY, MAY 4, 1997}}
%
%\begin{social}{Coffee break: 10:00 am\,--\,10:30 am}\end{social}
%
%\begin{social}{Lunch: 12:30 pm\,--\,2:00 pm}\end{social}
%
%\begin{social}{Banquet: 6:30 pm} The banquet will consist of bad food served
%on an interminable boat trip at night, when you can't see the beautiful
%countryside we're going through.
%The boat leaves from Pier 42 at 7:00 pm. Buses leave the hotel at 6:30 pm.
%\end{social}
%
%%% End: Stuff needed for formatting the technical program
%%% Courtesy previous STOCs/FOCs
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}
% \small
\begin{center}
{
\Large \bf
14th Annual ACM Symposium on }
\vspace{0.6cm}
{ \huge \bf
COMPUTATIONAL
GEOMETRY}
\vspace{0.2cm}
\setlength{\unitlength}{0.50cm}
\
\begin{picture}(14.5,12)(-7.25,-6)
\thicklines
\multiput(-5.5,-1.45)(0,1.75){2}{\framebox(11,1.15){}}
\multiput(-1.45,-5.5)(1.75,0){2}{\framebox(1.15,11){}}
\multiput(-3.75,-2.35)(6.35,0){2}{\framebox(1.15,4.7){}}
\multiput(-2.35,-3.75)(0,6.35){2}{\framebox(4.7,1.15){}}
\multiput(-2.9,0)(2.9,-2.9){2}{\line(1,1){2.9}}
\multiput(-2.9,0)(2.9,2.9){2}{\line(1,-1){2.9}}
\end{picture}
\vspace{0.2cm}
{ \Large \bf
June 7--10, 1998
Minneapolis, Minnesota
{\tt http://www.cs.umn.edu/scg98}
}
\vspace{0.4cm}
%\vspace{2.7cm}
%\begin{picture}( 2.7, 2.7)
%\put(0,0){\special{psfile="/u/alioth/0/prisme/yvinec/ACMscg97/acmlogo.ps"}}
%\end{picture}
\unitlength 1.2cm
\input{acmlogolatex.ltex}
\vspace{0.4cm}
\rm
\normalsize
Sponsors: ACM Special Interest Groups on \\
Graphics (SIGGRAPH) and \\
Algorithms and Computation Theory (SIGACT)
With support from: \\
\hspace*{-3.25cm} The Geometry Center at the
\special{psfile=uofmwordmark.eps hscale = 50 vscale =50
hoffset=0 voffset=-37}\\
and Lucent Technologies
\end{center}
\newpage
\begin{center}
\large
\bfseries
14th Annual ACM Symposium on \\
Computational Geometry
Registration Form
\end{center}
Please fill out and send this form by {\em priority mail}
to the following address. (If paying by credit card, you
may also fax your registration.)
\begin{center}
2198 Registrar\\
45 Wesbrook Hall\\
77 Pleasant Street S.E.,\\
University of Minnesota\\
Minneapolis, MN 55455--0216\\
U.S.A.\\
Phone: +1 (612) 625-3850\\
Fax: +1 (612) 625-1511
\end{center}
\textbf{Important} : Registration can only be accepted if payment
instructions are duly followed. In particular, don't forget
to give your card number, expiration date, and signature if
paying by credit card.
Advance registration can only be accepted if received
by {\bf May 18, 1998}.
\vspace{0.2cm}
First Name \dotfill
Last Name \dotfill
Affiliation : \dotfill
Street Address : \dotfill
\hspace*{1cm} \dotfill
City ............................. ZIP Code \dotfill
State ............................. Country \dotfill
Phone \dotfill
Fax \dotfill
Email \dotfill
\vspace{0.25cm}
I agree to be listed on the registrant list for distribution
to conference participants \qquad
{\large$\Box$} Yes \hspace{.5cm} {\large$\Box$} No
\vspace{0.25cm}
Date of arrival \dotfill
Date of departure \dotfill
\vspace{0.25cm}
Special needs (e.g., Vegetarian/Kosher): \dotfill
Preferred video standard \\
{\large$\Box$} NTSC \hspace{2cm} {\large$\Box$} Pal \hspace{2cm}
{\large$\Box$} Secam
\newpage
{ Please register me as follows}:
\vspace{-0.3cm}
\begin{tabbing}
{\large$\Box$} \= \hspace{3.5cm} \= {\large$\Box$} US\$315 \hspace{0.7cm} \= \kill
\> \>{\bf Advance} \> {\bf Late} \\
\> \> by May 18 \> after May 18 \\
\> ACM Members \> {\large$\Box$} US\$315 \> {\large$\Box$} US\$355 \\
\> Non-ACM Members \> {\large$\Box$} US\$355 \> {\large$\Box$} US\$405 \\
\> Students \> {\large$\Box$} US\$165 \> {\large$\Box$} US\$195
\end{tabbing}
ACM Membership Number, if applicable: \dotfill
The registration fee (both regular and student)
includes all technical sessions, the proceedings, video, four
lunches, coffee breaks, reception, and banquet.
Extra copies of the proceedings or video, and extra
banquet tickets may be purchased on-site at the following rates: \\
Proceedings US\$37,
Video US\$10,
Banquet US\$35
\vspace{0.2cm}
{\bf Payment}\\
Payment can be made in one of two ways, and must accompany
your registration form:
{$\bullet$ Credit card}\\
{\large$\Box$} Visa
\hspace{0.2cm} {\large$\Box$} Mastercard
\hspace{0.2cm} {\large$\Box$} AmEx
\hspace{0.2cm} {\large$\Box$} Discover
Card Number : \dotfill
Expiration Date : ............. Signature : \dotfill
{$\bullet$ Check/Bank draft}\\
This must be in US\$ and drawn on a US Bank. Make
checks/bank draft payable to ``{\bf UM/ACM SCG 98}''.
\vspace{0.2cm}
{\bf Refunds} \\
Registration fee may be refunded in full if a written request is received
by {\bf May 26, 1998}.
\newpage
{\bf
Hotel Reservation}\\
The Symposium will be at the Radisson Hotel Metrodome,
615 Washington Avenue S.E., Minneapolis, MN 55414.
A block of rooms has been reserved at the hotel, at the
rates given on the attached Hotel Reservation form.
Rates are valid for the period
June~4--12, 1998. {\bf Please make your reservations as soon as
possible. The HOTEL RESERVATION DEADLINE is MAY 9, 1998.}
After this date, accommodations and prices cannot be guaranteed.
You can make your hotel reservation by calling the
hotel at +1 (800)--822--6757 or +1 (612)--379--8888. Remember
to mention that you are
attending the ``ACM Symposium on Computational Geometry''.
Alternatively, you can fill out the attached form and mail/fax it
to the hotel.
All-day parking is available to hotel guests at the rate of
\$6.50 per day (rate subject to change). Hotel guests also
enjoy complimentary access to the Univ.\ of Minnesota's
\$30 million state-of-the-art Recreation Center, located
next to the hotel. The Center features an Olympic-size
swimming pool, a variety of fitness equipment, as well
as basketball, volleyball, racquetball, and badminton courts.
{\bf Note:} Do not confuse the Symposium hotel with the
many other Radisson hotels located in the Twin Cities of
Minneapolis and St.~Paul. The
Symposium hotel is the Radisson Metrodome. It is located
adjacent to the East Bank Campus of the Univ.\ of Minnesota, two
blocks from the Geometry Center and the Computer Science
\& Engineering Department, and close to many campus
attractions.
\vspace{.5cm}
{\bf Important dates}\\
Cut-off for hotel reservation: {\bf May 9, 1998}.\\
Cut-off for advance registration: {\bf May 18, 1998}.\\
Cut-off for receiving written request\\ for refund of
registration fee: {\bf May 26, 1998}.\\
Symposium: {\bf June 7--10, 1998}.
\newpage
\begin{center}
\large
\bfseries
Hotel Reservation Form
14th Annual ACM Symposium on \\
Computational Geometry
June 7--10, 1998, Minneapolis, MN
\end{center}
\begin{center}
Send to:\\
Radisson Hotel Metrodome \\
Reservation Desk \\
615 Washington Avenue S.E.\\
Minneapolis, MN 55414, U.S.A. \\
Phone: +1 (800) 822--6757 or +1 (612) 379--8888\\
Fax: +1 (612) 379--8682
\end{center}
\vspace{0.2cm}
First Name \dotfill
Last Name \dotfill
Affiliation : \dotfill
Street Address : \dotfill
\hspace*{1cm} \dotfill
City ............................. ZIP Code \dotfill
State ............................. Country \dotfill
Phone \dotfill
Fax \dotfill
Email \dotfill
\vspace{0.5cm}
Date of arrival \dotfill
Date of departure \dotfill
\vspace{0.5cm}
{\bf Type of room}:
{\large$\Box$} Single --- \$90/night plus 12\% tax \\
{\large$\Box$} Double --- \$100/night plus 12\% tax
\vspace{0.2cm}
If sharing a room, please list roommate's name below:\\
\dotfill
\vspace{0.2cm}
Please provide a major credit card to guarantee your room
in case of late arrival (after 6 pm):
{\large$\Box$} Visa
\hspace{0.2cm} {\large$\Box$} Mastercard
\hspace{0.2cm} {\large$\Box$} AmEx
\hspace{0.2cm} {\large$\Box$} Discover
Card Number : \dotfill
Expiration Date : .............
\newpage
{\bf Travel Information}\\
Minneapolis--St.~Paul International Airport is served by most major
airlines. Northwest Airlines, the Preferred Airline for the
Symposium, is pleased to offer discounted airfares. To take
advantage of these savings, please call Northwest World
Meetings and Incentives Reservations at 1-800-328-1111,
between 7:30 AM and 7:30 PM Central Time, Monday--Friday.
Please refer to WorldFile Number NEE66 to receive the
discount, which ranges from 5--10\% off published fares,
for travel to the Symposium from within the U.S. and Canada.
{\bf Ground transportation} \\
The Symposium hotel is located about 15 miles from the
airport, near the University of Minnesota campus and close
to downtown Minneapolis. Taxi fare from the airport
is about US\$15--20. Another
option is to take the Airport Express shuttle service
(1-800-333-1532), which
costs US\$10 one-way and US\$16.50 round-trip, and departs
the airport every twenty minutes. A third
option is to rent a car. Note that the shuttle
counter as well as all major automobile rental agencies are
located one level below the baggage claim area at
the airport.
{\bf Driving directions from:}\\
{\em (A) The airport:} Take I~494
West to I~35W North. Follow I~35W North just past downtown
Minneapolis, take Exit~17C (Minn. Hwy.~122),
and then follow the signs for ``U of M East Bank''. After crossing
the bridge over the Mississippi, you will
be on Washington Avenue SE.
Go to the third stoplight (Harvard Street), turn left, and
then make an immediate right into the hotel.
{\em (B) Points south of the Twin Cities:} Take I~35
North to
I~35W North (I~35 forks into I~35W and I~35E south of the Twin
Cities) and follow the directions in (A) above.
{\em (C) Points west of the Twin Cities:} Take I~94
East to I~35W North and follow the directions in (A) above.
{\em (D) Points north of the Twin Cities:} Take I~35
South to I~35W South, to Exit~18 (University Ave./4th Street
SE). Turn left on University Ave., then right on Oak Street,
and then right on Washington Avenue. The hotel is one block down,
on the right.
{\em (E) Points east of the Twin Cities (and from
St.~Paul):} Take I~94 West to Exit~235B (U of M) to
Huron Blvd. Follow Huron to Washington Avenue and turn left.
The hotel is three blocks down, on the right.
{\em (F) Downtown Minneapolis:} Take 4th Street SE
(one-way eastbound), which becomes Washington Ave. SE, and
then follow the directions in (A) above.
\newpage
{\bf Things to see/do}\\
The Minneapolis--St.~Paul (Twin Cities) metropolitan area
is a vibrant and dynamic one,
and provides opportunities for a variety of activities, both
outdoor and indoor. Outdoor activities include
walking/hiking/biking along numerous park trails in the
Cities and along the shorelines of the many lakes that
dot the metro area, the Valleyfair Family Amusement Park,
the Minnesota and Como Zoos, and historic Fort Snelling. A bit
further out (about 45 minutes by car) is
the scenic St.~Croix River Valley. Up north (about three to
five hours away) are the spectacular North Shore of Lake Superior,
the Voyageurs National Park, and the Boundary Waters Canoe
Area. Among indoor activities, a must-see is the Mall of
America, the largest enclosed shopping and entertainment
complex in the U.S. It covers over 4 million square feet,
and includes more than 500 shops, numerous fine restaurants, a
theme park (Camp Snoopy), and an underwater aquarium (Underwater World)
featuring exotic marine life. (Plan on spending all day at the Mall.)
The Twin Cities also offer a diverse collection of theaters,
museums, and art galleries including: the Walker Art Center,
the Minneapolis Institute of Arts, the Sculpture Garden, and
the Orpheum and Guthrie Theaters, all in Minneapolis; the Ordway
Music Theater, the Landmark Center, the Science Museum and
Omnitheater, the Children's Museum, and the State Capitol,
all in St.~Paul; the Weisman Art Museum and the Bell Museum
of Natural History on the U of M campus; and the Chanhassen
Dinner Theaters in the West metro. Both downtowns
also feature excellent restaurants, offering a variety of
dining experiences. If baseball catches your fancy, then
you can watch the Minnesota Twins (in possibly their last season
here) in the nearby Metrodome. Please see the Symposium web-page
for more information.
Getting around town: The Metropolitan Transit
Commission (612--349--7000) provides bus service to both downtowns
and to surrounding suburbs.
{\bf Climate} \\
The weather in the Twin Cities in June is pleasant. Daytime
temperatures are generally in the low-$70^\circ F$
($21^\circ$ C) range,
with plenty of sunshine. However, it would be prudent to
bring along a sweater or light jacket and an umbrella. (This
is Minnesota, after all!)
\vspace{0.2cm}
{\bf Symposium web-page}\\
Updated information about the Symposium will be posted,
as needed, at {\tt http://www.cs.umn.edu/scg98}\ . Please
check this from time to time.
\newpage
\begin{center}
\large
\bfseries
Program
\end{center}
In addition to forty-four contributed
talks and a video review, this year's Symposium
also features six invited
talks, a panel discussion, and a problem session. {\sl The
invited talks and panel discussion, as well as the Saturday
reception, are supported by the Geometry Center---a National
Science Foundation Science and Technology Center at the
University of Minnesota.} All Symposium activities
will be at the Radisson.
\vspace{.25cm}
\day{Saturday, June 6}
\begin{session}{}
\talk{19:00--22:00\ }{Reception and Registration at the \\ Radisson}
\byby{Hosted by the Geometry Center}{}
\end{session}
\day{Sunday, June 7}
\begin{session}{}
\talknocolon{09:00\ }{Registration re-opens}
\end{session}
\begin{session}{}
\talk{10:30\ }{Welcoming Remarks}
\by{Ken Clarkson}{Bell Labs};
\by{Jarek Rossignac}{GVU/Georgia Tech}
\end{session}
\begin{chairedsession}{Session 1: Applied Track}{\Chaired{Jarek Rossignac}{GVU/Georgia Tech}}
\talk{10:40\ }{Rotational Polygon Containment and Minimum Enclosure}
\by{Victor~J. Milenkovic}{Univ. of Miami}
\talk{11:00\ }{A General Framework for Assembly Planning: The Motion Space Approach}
\by{Dan Hal\-perin}{Tel Aviv Univ.};
\by{Jean-Claude Latombe, Randall~H. Wilson}{Stanford Univ.}
\talk{11:20\ }{Multi-criteria Geometric Optimization Problems in Layered Manufacturing}
\by{Jayanth Majhi, Ravi Janardan}{Univ. of Minnesota};
\by{Michiel Smid, J\"org Schwerdt}{Univ. of Magdeburg}
\talk{11:40\ }{Design and Analysis of Planar Shape Deformation}
\by{Siu-Wing Cheng}{Hong Kong Univ. of Science and Technology};
\by{Herbert Edelsbrunner}{Univ. of Illinois at Urbana-Champaign and Raindrop Geomagic};
\by{Ping Fu}{Raindrop Geomagic, Inc. and NCSA, Univ. of Illinois};
\by{Ka-Po Lam}{Hong Kong Univ. of Science and Technology}
\end{chairedsession}
\begin{session}{}
\talk{12:00--13:30\ }{Lunch}
\byby{Radisson}{}
\end{session}
\vspace{.15cm}
\fbox{
\begin{minipage}{3.20in}
\begin{session}{Invited Talk 1}
\talk{13:30--14:30\ }{Shape Space from Deformation}
\by{Herbert Edelsbrunner}{Univ. of Illinois at
Urbana-Champaign and Raindrop Geomagic}
\end{session}
\end{minipage}
}
\vspace{.15cm}
\begin{chairedsession}{Session 2: Theoretical Track}{\Chaired{Michiel Smid}{Univ.\ Magdeburg}}
\talk{14:40\ }{Surface Reconstruction by Voronoi Filtering}
\by{Nina Amenta}{Univ. of Texas, Austin};
\by{Marshall Bern}{Xerox PARC}
\talk{15:00\ }{Cross Ratios and Angles Determine a Polygon}
\by{Jack Snoeyink}{INRIA \& Univ. of British Columbia}
\talk{15:20\ }{Raising Roofs, Crashing Cycles, and Playing Pool: Applications of a Data Structure for Finding Pairwise Interactions}
\by{David Eppstein}{Univ. of California, Irvine};
\by{Jeff Erickson}{Duke Univ.}
\talk{15:40\ }{Construction of Contour Trees in 3D in \\ $O(n \log n)$ steps}
\by{Sergey~P. Tarasov, Michael~N. Vyalyi}{Russian Academy of Science, Computing Center}
\end{chairedsession}
\begin{session}{}
\talknocolon{16:00--16:30\ }{Coffee Break}
\end{session}
\vspace{.15cm}
\fbox{
\begin{minipage}{3.20in}
\begin{session}{Invited Talk 2}
\talk{16:30--17:30\ }{Computational Geometry Issues of
Statistical Depth}
\by{Peter Rousseeuw}{Univ. of Antwerp}
\end{session}
\end{minipage}
}
\vspace{.15cm}
\begin{session}{}
\talk{20:30--22:30\ }{Business Meeting}
\byby{Radisson}{}
\end{session}
\day{Monday, June 8}
\begin{chairedsession}{Session 3: Applied and Theoretical Track}{\Chaired{Steve Fortune}{Bell Labs}}
\talk{08:50\ }{A Condition Guaranteeing the Existence of Higher-Dimensional Constrained Delaunay Triangulations}
\by{Jonathan~Richard Shewchuk} {Car\-negie Mellon Univ.}
\talk{09:10\ }{Tetrahedral Mesh Generation by Delaunay Refinement}
\by{Jonathan~Richard Shewchuk}{Car\-negie Mellon Univ.}
\talk{09:30\ }{Implementations of the LMT Heuristic for Minimum Weight Triangulation}
\by{Ron Beirouti}{Univ. of British Columbia};
\by{Jack Snoeyink}{INRIA \& Univ. of British Columbia}
\talk{09:50\ }{Improved Incremental Randomized Delaunay Triangulation}
\by{Olivier Devillers}{INRIA \\ Sophia-Antipolis}
\end{chairedsession}
\begin{session}{}
\talknocolon{10:10--10:40\ }{Coffee Break}
\end{session}
\begin{chairedsession}{Session 4: Theoretical Track}{\Chaired{Ken Clarkson}{Bell Labs}}
\talk{10:40\ }{Vertex-Rounding a Three-dimensional Polyhedral Subdivision}
\by{Steven Fortune}{Bell Laboratories, Lucent Technologies}
\talk{11:00\ }{Exact Algorithms for Circles on the Sphere}
\by{Marcus Vin\'{i}cius~A. Andrade}{Univ. of Vi\c{c}osa};
\by{Jorge Stolfi}{Univ. of Campinas}
\talk{11:20\ }{Cutting Cycles of Rods in Space}
\by{Alexandra Solan}{Tel-Aviv Univ.}
\talk{11:40\ }{Fly Cheaply: On the Minimum Fuel-Con\-sumption Problem}
\by{Alon Efrat, Sariel Har-Peled}{Tel-Aviv Univ.}
\end{chairedsession}
\begin{session}{}
\talk{12:00--13:30\ }{Lunch}
\byby{Radisson}{}
\end{session}
\vspace{.15cm}
\fbox{
\begin{minipage}{3.20in}
\begin{session}{Invited Talk 3}
\talk{13:30--14:30\ }{Title to be announced}
\by{James Sethian}{Univ. of California, Berkeley}
\end{session}
\end{minipage}
}
\vspace{.15cm}
\begin{chairedsession}{Session 5: Applied Track}{\Chaired{Leonidas Guibas}{Stanford Univ.}}
\talk{14:40\ }{Designing a Data Structure for Polyhedral Surfaces}
\by{Lutz Kettner}{ETH Z\"urich}
\talk{15:00\ }{Improved Algorithms for Robust Point Pattern Matching and Applications to Image Registration}
\by{David~M. Mount}{Univ. of Maryland};
\by{Nathan~S. Netanyahu}{Univ. of Maryland and NASA Goddard Space Flight Center};
\by{Jacqueline LeMoigne}{Universities Space Research Association}
\talk{15:20\ }{Interval Arithmetic Yields Efficient Dynamic Filters for Computational Geometry}
\by{Herv\'e Br\"onnimann}{INRIA Sophia-Antipolis};
\by{Christoph Burnikel}{Max-Planck-Institut f\"ur Informatik};
\by{Sylvain Pion}{INRIA Sophia-Antipolis}
\talk{15:40\ }{Exact Arithmetic using Cascaded Computation}
\by{Christoph Burnikel, Stefan Funke, Michael Seel}{Max-Planck-Institut f\"ur Informatik}
\end{chairedsession}
\begin{session}{}
\talknocolon{16:00--16:30\ }{Coffee Break}
\end{session}
\newpage
\begin{chairedsession}{Session 6: Theoretical Track}{\Chaired{Micha Sharir}{Tel Aviv Univ.}}
\talk{16:30\ }{Geometric Graphs with Few Disjoint Edges}
\by{G\'eza T\'oth}{Courant Institute, NYU and DIMACS Center, Rutgers Univ.};
\by{Pavel Valtr}{Charles Univ., Prague and DIMACS Center, Rutgers Univ.}
\talk{16:50\ }{Results on $k$-sets and $j$-facets via Continuous Motions}
\by{Artur Andrzejak}{ETH Z\"urich};
\by{Boris Aronov}{Polytechnic Univ., Brooklyn};
\by{Sariel Har-Peled}{Tel-Aviv Univ.};
\by{Raimund Seidel}{Univ. des Saarlandes};
\by{Emo Welzl}{ETH Z\"urich}
\talk{17:10\ }{Point Sets with few $k$-sets}
\by{Helmut Alt, Stefan Felsner}{Freie Universit\"at Berlin};
\by{Ferran Hurtado, Marc Noy}{Departament de Matem\'atica Aplicada II}
\talk{17:30\ }{On the Union of $\kappa$-Curved Objects}
\by{Alon Efrat}{Tel-Aviv Univ.};
\by{Matthew~J. Katz}{Ben-Gurion Univ.}
\end{chairedsession}
\begin{session}{}
\talk{19:00--21:30\ }{Conference Dinner and After-Dinner Talk}
\byby{Radisson}{}
\end{session}
\vspace{.15cm}
\fbox{
\begin{minipage}{3.20in}
\begin{session}{Invited Talk 4}
\talk{20:30--21:30\ }{The Art and Mathematics of Geometric
Dissections}
\by{Greg Frederickson}{Purdue Univ.}
\end{session}
\end{minipage}
}
\vspace{.15cm}
\day{Tuesday, June 9}
\begin{chairedsession}{Session 7: Applied Track}{\Chaired{Fred
Bookstein}{Univ. of Michigan}}
\talk{08:50\ }{Features of Deformation Grids: An Appr\-oach via Singularity Theory}
\by{Fred~L. Bookstein}{Univ. of Michigan}
\talk{09:10\ }{Effective Nearest Neighbors Searching on the Hyper-Cube, with Applications to Molecular Clustering}
\by{Frederic Cazals}{INRIA}
\talk{09:30\ }{Matching 2D Patterns of Protein Spots}
\by{Frank Hoffmann, Klaus Kriegel, Carola Wenk}{Freie Universit\"at Berlin}
\talk{09:50\ }{Multiresolution Banded Refinement to Accelerate Surface Reconstruction from Polygons}
\by{James~D. Fix, Richard~E. Ladner}{Univ. of Washington}
\end{chairedsession}
\begin{session}{}
\talknocolon{10:10--10:40\ }{Coffee Break}
\end{session}
\newpage
\begin{chairedsession}{Session 8: Theoretical Track}{\Chaired{Mariette Yvinec}{CNRS, I3S}}
\talk{10:40\ }{Degenerate Convex Hulls On-line in any Fix\-ed Dimension}
\by{Herv\'e Br\"onnimann}{INRIA Sophia-Antipolis}
\talk{11:00\ }{Randomized External-Memory Algorithms for some Geometric Problems}
\by{A. Crauser, P. Ferragina, K. Mehlhorn, U. Meyer, E. Ramos}{Max-Planck-Institut f\"ur Informatik}
\talk{11:20\ }{Geometric Applications of a Randomized
Optimization Technique}
\by{Timothy~M. Chan}{Univ. of Miami}
\talk{11:40\ }{On Enumerating and Selecting Distances}
\by{Timothy~M. Chan}{Univ. of Miami}
\end{chairedsession}
\begin{session}{}
\talk{12:00--13:30\ }{Lunch}
\byby{Radisson}{}
\end{session}
\vspace{.15cm}
\fbox{
\begin{minipage}{3.20in}
\begin{session}{Invited Talk 5}
\talk{13:30--14:30\ }{Progressive Representations for Geometry}
\by{Hugues Hoppe}{Microsoft}
\end{session}
\end{minipage}
}
\vspace{.15cm}
\begin{chairedsession}{Session 9: Theoretical Track}{\Chaired{John Hershberger}{Mentor Graphics}}
\talk{14:40\ }{Drawing Planar Partitions I: LL-Drawings and LH-Drawings}
\by{Therese~C. Biedl}{McGill Univ.}
\talk{15:00\ }{Approximation Algorithms for Multiple-\\ Tool Milling}
\by{Sunil Arya}{Hong Kong Univ. of Science \& Technology};
\by{Siu-Wing Cheng}{Hong Kong Univ. of Science and Technology};
\by{David~M. Mount}{Univ. of Maryland}
\talk{15:20\ }{Resource-Constrained Geometric Network Optimization}
\by{Esther~M. Arkin, Joseph~S.~B. Mitchell}{State Univ. of New York, Stony Brook};
\by{Giri Narasimhan}{Univ. of Memphis}
\talk{15:40\ }{Efficiently Approximating Polygonal Paths in Three and Higher Dimensions}
\by{Gill Barequet}{Johns Hopkins Univ.};
\by{Danny~Z. Chen, Ovidiu Daescu}{Univ. of Notre Dame};
\by{Michael~T. Goodrich}{Johns Hopkins Univ.};
\by{Jack Snoeyink}{INRIA \& Univ. of British Columbia}
\end{chairedsession}
\begin{session}{}
\talknocolon{16:00--16:30\ }{Coffee Break}
\end{session}
\begin{session}{Panel Discussion}
\talknocolon{16:30--17:50\ }{The Theory/Application Interface}\\
\end{session}
\newpage
\begin{session}{Problem Session}
\talknocolon{20:30--22:30\ }{}
\by{Coordinator: Pankaj Agarwal}{Duke Univ.}
\end{session}
\day{Wednesday, June 10}
\vspace{.15cm}
\fbox{
\begin{minipage}{3.20in}
\begin{session}{Invited Talk 6}
\talk{09:10--10:10\ }{Algorithms in Real Algebraic Geometry}
\by{Richard Pollack}{Courant Institute, New York Univ.}
\end{session}
\end{minipage}
}
\vspace{.15cm}
\begin{session}{}
\talknocolon{10:10--10:40\ }{Coffee Break}
\end{session}
\begin{chairedsession}{Session 10: Applied Track}{\Chaired{Tamal
Dey}{I.I.T. Kharagpur}}
\talk{10:40\ }{Constructing Cuttings in Theory and Practice}
\by{Sariel Har-Peled}{Tel-Aviv Univ.}
\talk{11:00\ }{Point Set Labeling with Sliding Labels}
\by{Marc van Kreveld, Tycho Strijk}{Utrecht Univ.};
\by{Alexander Wolff}{Freie Universit\"at Berlin}
\talk{11:20\ }{A Unified Approach to Labeling Graphical Features}
\by{Konstantinos~G. Kakoulis, Ioannis~G. Tollis}{The Univ. of Texas at Dallas}
\talk{11:40\ }{An Output Sensitive Algorithm for Discrete Convex Hulls}
\by{Sariel Har-Peled}{Tel-Aviv Univ.}
\end{chairedsession}
\begin{session}{}
\talk{12:00--13:30\ }{Lunch}
\byby{Radisson}{}
\end{session}
\begin{chairedsession}{Session 11: Theoretical Track}{\Chaired{Mark Overmars}{Utrecht Univ.}}
\talk{13:30\ }{Asymmetric Rendezvous on the Plane}
\by{Edward~J. Anderson}{Univ. of New South Wales};
\by{S\'andor~P. Fekete}{Universit\"at zu K\"oln}
\talk{13:50\ }{Motion Planning for Multiple Robots}
\by{Boris Aronov}{Polytechnic Univ., Brooklyn};
\by{Mark~de Berg, Frank~van~der Stappen}{Utrecht Univ.};
\by{Peter \v{S}vestka}{CWI};
\by{Jules Vleugels}{Utrecht Univ.}
\talk{14:10\ }{Constructing Approximate Shortest Path \\
Maps in Three Dimensions}
\by{Sariel Har-Peled}{Tel-Aviv Univ.}
\talk{14:30\ }{Curvature-Constrained Shortest Paths in a Convex Polygon}
\by{Pankaj Agarwal}{Duke Univ.};
\by{Therese~C. Biedl, Sylvain Lazard, Steve Robbins}{McGill Univ.};
\by{Subhash Suri}{Washington Univ.};
\by{Sue Whitesides}{McGill Univ.}
\end{chairedsession}
\begin{session}{}
\talknocolon{14:50\ }{Adjourn}
\end{session}
\newpage
\begin{chairedsession}{Video Review}{\Chaired{Dan Halperin}{Tel Aviv Univ.}}
\talk{$\bullet$}{Voronoi Diagram by Divergences with Additive Weights}
\by{K. Sadakane, H. Imai, K. Onishi, M. Inaba, F. Takeuchi}{Univ. of Tokyo};
\by{K. Imai}{Chuo Univ.}
\talk{$\bullet$}{GASP-II -- A Geometric Algorithm Animation System for an Electronic Classroom}
\by{Maria Shneerson}{The Weizmann Institute of Science};
\by{Ayellet Tal}{Technion -- Israel Institute of Technology}
\talk{$\bullet$}{Visualization of Color Image Quantization using Pairwise Clustering}
\by{Luiz Velho, Jonas Gomes}{IMPA - Instituto de Matem\'atica Pura e Aplicada};
\by{Marcos~V.~R. Sobreiro}{PUC-Rio}
\talk{$\bullet$}{Optimal Floodlight Illumination of Stages}
\by{Felipe Contreras}{Univ. of Ottawa};
\by{Jurek Czyzowicz}{Universit\'e du Quebec \`a Hull};
\by{Eduardo Rivera-Campo}{Univ. Auton\'oma Metropolitana-I};
\by{Jorge Urrutia}{Univ. of Ottawa}
\talk{$\bullet$}{Gawain: Visualizing Geometric Algorithms with Web-based Animation}
\by{Alejo Hausner, David~P. Dobkin}{Princeton Univ.}
\talk{$\bullet$}{Viewspace Partitioning of Densely Occluded Scenes}
\by{Yiorgos Chrysanthou}{Univ. College London};
\by{Daniel Cohen-Or, Eyal Zadicario}{Tel-Aviv Univ.}
\talk{$\bullet$}{A Path Router for Graph Drawing}
\by{David~P. Dobkin}{Princeton Univ.};
\by{Emden~R. Gansner, \\ Eleftherios Koutsofios, Stephen~C. North}{AT\&T Laboratories}
\end{chairedsession}
\end{document}