Date: Fri, 7 Nov 97 14:31:04 EST From: pollack@geometry.cims.nyu.edu (Ricky Pollack) To: compgeom-announce@research.bell-labs.com Subject: 29th Computational Geometry Day, Dec. 12
- 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
- Wine and Cheese Reception (13th floor lounge)
For more information contact: Richard Pollack (212) 998-3167 pollack@geometry.nyu.edu
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".
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)).
We discuss some variants of TSP tour and path optimization problems:
Work on some of these problems is joint with Yi-Jen Chiang, Joe Mitchell, Giri Narasimhan, Steve Skiena and Tae-Cheon Yang.