Untangling Two Systems of Noncrossing CurvesMatoušek, Jiří and Sedgwick, Eric and Tancer, Martin and Wagner, Uli (2013) Untangling Two Systems of Noncrossing Curves. In: 21st International Symposium, GD 2013, September 2325, 2013 , pp. 472483(Official URL: http://dx.doi.org/10.1007/9783319038414_41). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/9783319038414_41
AbstractWe consider two systems (α 1,…,α m ) and (β 1,…,β n ) of curves drawn on a compact twodimensional surface with boundary. Each α i and each β j is either an arc meeting the boundary of at its two endpoints, or a closed curve. The α i are pairwise disjoint except for possibly sharing endpoints, and similarly for the β j . We want to “untangle” the β j from the α i by a selfhomeomorphism of ; more precisely, we seek an homeomorphism φ→ fixing the boundary of pointwise such that the total number of crossings of the α i with the ϕ(β j ) is as small as possible. This problem is motivated by an application in the algorithmic theory of embeddings and 3manifolds. We prove that if is planar, i.e., a sphere with h ≥ 0 boundary components (“holes”), then O(mn) crossings can be achieved (independently of h), which is asymptotically tight, as an easy lower bound shows. In general, for an arbitrary (orientable or nonorientable) surface with h holes and of (orientable or nonorientable) genus g ≥ 0, we obtain an O((m + n)4) upper bound, again independent of h and g.
Actions (login required)
