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
steps. Some related questions are also considered.
Article PDF
Similar content being viewed by others
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Pach, Tardos Untangling a Polygon. Discrete Comput Geom 28, 585–592 (2002). https://doi.org/10.1007/s00454-002-2889-y
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00454-002-2889-y