Pach, János and Tardos, Gábor (2002) Untangling a Polygon. [Conference Paper]
Full text not available from this repository.
Abstract
The following problem was raised by M. Watanabe. Let $P$ be a self-intersecting closed polygon with $n$ vertices in general position. How manys steps does it take to untangle $P$, i.e., to turn it into a simple polygon, if in each step we can arbitrarily relocate one of its vertices. It is shown that in some cases one has to move all but at most $O((n\log n)^{2/3})$ vertices. On the other hand, every polygon $P$ can be untangled in at most $n-\Omega(\sqrt{n})$ steps. Some related questions are also considered.
| Item Type: | Conference Paper |
|---|---|
| Classifications: | Z Theory > Z.250 Geometry G Algorithms and Complexity > G.560 Geometry |
| ID Code: | 508 |
| Deposited By: | Arnopolina, Galina |
| Deposited On: | 21 Dec 2004 |
| Last Modified: | 18 Sep 2008 13:08 |
| Alternative Locations: | http://www.springerlink.com/openurl.asp?genre=article&issn=0302-9743&volume=2265&spage=154 |
Repository Staff Only: item control page
