Polygon Chain - Conversion to non-crossing while preserving shape? - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-20T05:01:41Z http://mathoverflow.net/feeds/question/27008 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/27008/polygon-chain-conversion-to-non-crossing-while-preserving-shape Polygon Chain - Conversion to non-crossing while preserving shape? Monte 2010-06-04T04:20:58Z 2010-06-04T07:15:59Z <p>I have polygon chains similar to the following...</p> <p><a href="http://upload.wikimedia.org/wikipedia/commons/thumb/6/62/Self_crossed_polygonal_chain.svg/220px-Self_crossed_polygonal_chain.svg.png" rel="nofollow">http://upload.wikimedia.org/wikipedia/commons/thumb/6/62/Self_crossed_polygonal_chain.svg/220px-Self_crossed_polygonal_chain.svg.png</a></p> <p>...given the chain in the image, how would I go about calculating a chain that defines <em>the same shape</em> but <em>without</em> crossing paths?</p> <p>Specifically, in the case of the image, the result I want looks like this:</p> <p>A1,<br> A2,<br> Intersect between A2 and A3,<br> Intersect between A3 and A4,<br> A4,<br> A5,<br> Intersect between A3 and A4,<br> A3,<br> Intersect between A3 and A2,<br> A6</p> <p>I'm looking for an algorithm to accomplish this for any chain, but I'm not sure what I'm trying to do is even called, which makes searching for a solution tricky. </p> <p>If there's a name for what I'm trying to do it would be of great help to know it. </p> <p>Thank you for any assistance!</p> http://mathoverflow.net/questions/27008/polygon-chain-conversion-to-non-crossing-while-preserving-shape/27013#27013 Answer by Jason Dyer for Polygon Chain - Conversion to non-crossing while preserving shape? Jason Dyer 2010-06-04T05:22:04Z 2010-06-04T05:22:04Z <p>While I've never heard of your exact algorithm being done before, the sweep line algorithm can be used to detect all the intersections quickly. (As mentioned <a href="http://compgeom.cs.uiuc.edu/~jeffe/teaching/algorithms/notes/xo-sweepline.pdf" rel="nofollow">here</a>, for instance.)</p> http://mathoverflow.net/questions/27008/polygon-chain-conversion-to-non-crossing-while-preserving-shape/27024#27024 Answer by David Eppstein for Polygon Chain - Conversion to non-crossing while preserving shape? David Eppstein 2010-06-04T07:15:59Z 2010-06-04T07:15:59Z <p>There is a fair amount of research on algorithms for this problem in the computational geometry, under the name "arrangement of line segments" (the line segments are the ones in the polygonal chain, and the arrangement is the planar graph you get when you place vertices at all the endpoints and crossing points).</p> <p>In practice, Jason Dyer's suggestion of using a sweep line algorithm is a good one. In theory, there are better algorithms: for \$n\$ line segments with \$k\$ crossing points, the sweep line gives you time \$O((n + k)\log n)\$, and some other methods lead to \$O(n\log n+k)\$ running times; see e.g. <a href="http://dx.doi.org/10.1007/BF02187740" rel="nofollow">Clarkson and Shor, Discrete Comput. Geom. 1989</a>.</p> <p>When the line segments themselves form a connected nonplanar graph (as in your case, where they form a path graph) even faster algorithms are possible (at most an iterated log factor away from linear time, and linear whenever \$k\$ is not too close to \$n\$): see my paper <a href="http://arxiv.org/abs/0812.0893" rel="nofollow">"Linear-time algorithms for geometric graphs with sublinearly many crossings"</a> and its references. But I think these methods are too complicated to be practically useful.</p>