Untangling a PolygonPach, János and Tardos, Gábor (2002) Untangling a Polygon. In: Graph Drawing 9th International Symposium, GD 2001, September 2326, 2001 , pp. 154161(Official URL: http://dx.doi.org/10.1007/3540458484_13). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/3540458484_13
AbstractThe following problem was raised by M. Watanabe. Let P be a selfintersecting 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 − Ω(√n) steps. Some related questions are also considered.
Actions (login required)
