Polygon Chain - Conversion to non-crossing while preserving shape? - MathOverflow

Polygon Chain - Conversion to non-crossing while preserving shape?

2010-06-04T04:20:58Z

I have polygon chains similar to the following...

http://upload.wikimedia.org/wikipedia/commons/thumb/6/62/Self_crossed_polygonal_chain.svg/220px-Self_crossed_polygonal_chain.svg.png

...given the chain in the image, how would I go about calculating a chain that defines the same shape but without crossing paths?

Specifically, in the case of the image, the result I want looks like this:

A1,
A2,
Intersect between A2 and A3,
Intersect between A3 and A4,
A4,
A5,
Intersect between A3 and A4,
A3,
Intersect between A3 and A2,
A6

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.

If there's a name for what I'm trying to do it would be of great help to know it.

Thank you for any assistance!

Answer by Jason Dyer for Polygon Chain - Conversion to non-crossing while preserving shape?

2010-06-04T05:22:04Z

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 here, for instance.)

Answer by David Eppstein for Polygon Chain - Conversion to non-crossing while preserving shape?

2010-06-04T07:15:59Z

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).

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. Clarkson and Shor, Discrete Comput. Geom. 1989.

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 "Linear-time algorithms for geometric graphs with sublinearly many crossings" and its references. But I think these methods are too complicated to be practically useful.