Date:Fri, 7 Nov 97 14:31:53 ESTFrom:Ricky Pollack <pollack@geometry.cims.nyu.edu>To:geometry@cims.nyu.eduSubject: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.