Date: Fri, 7 Nov 97 14:31:53 EST
From: Ricky Pollack <pollack@geometry.cims.nyu.edu>
To: geometry@cims.nyu.edu
Subject: 29th Computational Geometry Day, Dec. 12, 1997
New York University
Courant Institute of Mathematical Sciences
TWENTY NINTH COMPUTATIONAL GEOMETRY DAY
Friday, December 12, 1997
Room 109, Warren Weaver Hall
251 Mercer St., New York, NY 10012
10.00--10.30 Coffee (Warren Weaver Hall Lobby)}
10:30--11:15 Jeff Erickson, Duke University
Raising roofs, crashing cycles, and playing pool:
Applications of a data structure for finding pairwise interactions
11:30--12:15 Jeff Lagarias, AT\&T Labs-Research
Loose Ends in Knot Theory: The Complexity of Unknotting
12:30--2:00 Lunch
2:00--3:00 Open Problem Session
3:00--3:45 Estie Arkin, SUNY Stony Brook
Approximation Algorithms for Variants of the TSP
4:00--5:00 {\em Wine and Cheese Reception (13th floor lounge)
For more information contact: Richard Pollack (212) 998-3167
pollack@geometry.nyu.edu
*************************abstracts***************************************
Raising roofs, crashing cycles, and playing pool:
Applications of a data structure for finding pairwise interactions
Jeff Erickson
Duke University
The straight skeleton of a polygon is a variant of the medial axis,
introduced by Aichholzer et al., defined by a shrinking process in
which each edge of the polygon moves inward at a fixed rate. We
construct the straight skeleton of an $n$-gon with $r$ reflex vertices
in time $O(n^{1+\e} + n^{8/11+\e}r^{9/11+\e})$, for any fixed $\e>0$,
improving the previous best upper bound of $O(nr\log n)$. Practical
variants of our algorithm run in time $O(n\log n + nr)$ using space
$O(n + r^2)$ and in time $O(n\log n + nr + r^2\log n)$ using only
linear space.
Our algorithm simulates the sequence of interactions between edges and
vertices during the shrinking process, using a technique of Eppstein
for maintaining extrema of binary functions to reduce the problem of
finding successive interactions to two dynamic range query problems:
(1) maintain a changing set of triangles in $\Real^3$ and answer
queries asking which triangle would be first hit by a query ray, and
(2) maintain a changing set of rays in $\Real^3$ and answer queries
asking for the lowest intersection of any ray with a query triangle.
We also exploit a novel characterization of the straight skeleton as a
lower envelope of triangles in $\Real^3$.
The same time bounds apply to constructing non-self-intersecting
offset curves with mitered or beveled corners, and similar methods
extend to other problems of simulating pairwise interactions among
sets of moving objects.
This is joint work with David Eppstein. Our paper is available at
"http://www.cs.duke.edu/~jeffe/pubs/cycles.html
Loose Ends in Knot Theory: The Complexity of Unknotting
Jeff Lagarias
A T & T Labs-Research
The problem of distinguishing knotted curves from unknotted
ones has a tangled history, starting from Max Dehn's work in
1910. However only in 1961 did Wolfgang Haken give an explicit
decision procedure to recognize unknottedness, based
on normal surface theory. This talk reviews the history of
problems in computational topology and knot theory. It
then describes explicit complexity bounds for the unknotting
problem. Recognizing if a knot diagram with $n$ crossings is
unknotted is in the complexity class NP. If a knot diagram is
unknotted, then there is an explicit unknotting that takes
at most $O(2^cn)$ Reidemeister moves, with $c=10^12.$
(These results are joint work with Joel Hass(U. Calif.-Davis)
and Nick Pippenger(U. British Columbia)).
Algorithms for Variants of the TSP
Estie Arkin
SUNY Stony Brook
We discuss some variants of TSP tour and path optimization problems:
The Scatter Traveling Salesman Problem
We study the problem of computing a Hamilton tour or path on a set of
points in order to maximize the minimum edge length. We give
complexity results, approximation algorithms and exact algorithms for
some special cases. We also consider a generalization in which the
points on the tour should be far not only from their immediate
predecessor and successor, but also from other neighbours on the tour.
The motivating applications are in manufacturing (sequencing of rivet
operations) and medical imaging.
The Rooted Orienteering Problem
We study the problem of computing a circuit visiting as many points as
possible from a given a set of points, including a designated root,
such that the total (Euclidean) distance traveled is bounded by a given
number $B$. We give the first constant factor approximation for this problem.
Work on some of these problems is joint with Yi-Jen Chiang,
Joe Mitchell, Giri Narasimhan, Steve Skiena and Tae-Cheon Yang.