Algorithm for detecting closed region on a plane

First off, I just want to say that I am not well versed in computational geometry, so if this question has some obvious answer, I apologize. I tried googling it but I could not find anything.

My question: Given an input of a plane with 1 or more line segments, is there an efficient algorithm for determining if there exists a closed region on this plane? For example, see the following picture:

benjamindicken.com/closed_region.png

On this plane, there exists one closed region. I would like the algorithm to return true if a closed region exists, and false if one does not.

At the moment, I only need this algorithm to determine if a closed region exists or not, but I could foresee needing this to return the number of closed regions as well.

• What is the input to your problem ? A collection of lines ? Jan 15, 2013 at 3:51
• Also, if you have three lines that aren't parallel or concurrent, there will always be one closed region. Jan 15, 2013 at 3:53
• Yes, the input would be a collection of lines. However, I am trying to apply this to edges on a graph (treating each line edge as a line on a plane). Thus, they are really a collection of line SEGMENTS, not full lines. Sorry, I should have made that more clear. Jan 15, 2013 at 4:08
• By default, graphs don't have coordinates, and their edges are formally pairs of vertices, not line segments. What is your input really? Jan 15, 2013 at 5:21
• Yes, I know this. This algorithm will be applied not to graphs, but to a graph drawing/layout in order to test for various properties. I am laying out the edges of the graph at particular (x,y) coordinates on a plane, and then representing each edge as a straight line segment between the two points. I do this for all edges. After doing this, I remove certain segments (or parts of segments) a little at a time. At various intervals, I would like to check if the graph contains a closed region on a plane. Jan 15, 2013 at 5:26

Let $S$ be a set of segments with the property that no two segments have an intersection with positive length. The set $S$ bounds a region if and only if the intersection graph of the segments in $S$ has a cycle.
• For example, one could have the set of segments $\: \left\{\left[\langle 0,0\rangle,\langle 1,0\rangle\right],\left[\langle 0,0\rangle,\langle 2,0\rangle\right],\left[\langle 1,0\rangle,\langle 2,0\rangle\right]\right\} \:$. $\;\;$