<p>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. </p>

CC BY-SA 3.0
2013-01-15T16:45:59.870Z
Yes.  However After drawing the graph edges on a plane, I will be removing some of the line segments (and segments of the segments).  That is why I didn't initially ask the question in terms on graph drawing, because after drawing the graph edges as segments, I will be altering the segments length, or removing them altogether. Thus "A set of straight-line segments bounds a region if and only if the intersection graph of the segments has a cycle" may not still hold after alteration.
bddicken
CC BY-SA 3.0
2013-01-15T17:58:49.470Z
Also, your statement is not necessarily true... it all depends on how the graph is drawn.
bddicken
CC BY-SA 3.0
2013-01-16T07:41:07.867Z
I was assuming that segments do not overlap, which perhaps may be assuming too much. I will edit it to make it clear.
someone
CC BY-SA 3.0
2013-01-16T07:49:50.483Z
@bddicken: if the segments change, the intersection graph also changes.
someone
CC BY-SA 3.0
2013-01-17T12:44:55.453Z
@bddicken: I think you need to know what is an intersection graph.  An intersection graph is combinatorial, so the existence of a cycle doesn't depend on how it's drawn. http://en.wikipedia.org/wiki/Intersection_graph
Yoshio Okamoto
CC BY-SA 3.0
2013-01-15T08:06:52.573Z
2013-01-16T07:48:17.677Z
2013-01-16T07:48:17.677Z
someone
<p>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.</p>

<p>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:</p>

<p>benjamindicken.com/closed_region.png</p>

<p>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.</p>

<p>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.</p>

<p>Thanks for your help.</p>

CC BY-SA 3.0
2013-01-15T03:51:38.503Z
What is the input to your problem ? A collection of lines ?
Suresh Venkat
CC BY-SA 3.0
2013-01-15T03:53:07.887Z
Also, if you have three lines that aren't parallel or concurrent, there will always be one closed region.
Suresh Venkat
CC BY-SA 3.0
2013-01-15T04:08:48.817Z
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.
bddicken
CC BY-SA 3.0
2013-01-15T05:21:28.107Z
By default, graphs don't have coordinates, and their edges are formally pairs of vertices, not line segments.  What is your input _really_?
Jeffε
CC BY-SA 3.0
2013-01-15T05:26:53.973Z
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.
bddicken
<ds.algorithms><cg.comp-geom>
Algorithm for detecting closed region on a plane
bddicken
# Algorithm for detecting closed region on a plane

(Asked by: username_0 on 2013-01-15)

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.

Thanks for your help.

**Tags:** ds.algorithms, cg.comp-geom
> **Comments:**
> **username_1**: What is the input to your problem ? A collection of lines ?  
> **username_1**: Also, if you have three lines that aren't parallel or concurrent, there will always be one closed region.  
> **username_0**: 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.  
> **username_2**: By default, graphs don't have coordinates, and their edges are formally pairs of vertices, not line segments.  What is your input _really_?  
> **username_0**: 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.  

---

## 1 answers

### Answer by username_3 on 2013-01-15. Score: 2

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.

> **Comments:**
> **username_0**: Yes.  However After drawing the graph edges on a plane, I will be removing some of the line segments (and segments of the segments).  That is why I didn't initially ask the question in terms on graph drawing, because after drawing the graph edges as segments, I will be altering the segments length, or removing them altogether. Thus "A set of straight-line segments bounds a region if and only if the intersection graph of the segments has a cycle" may not still hold after alteration.  
> **username_0**: Also, your statement is not necessarily true... it all depends on how the graph is drawn.  
> **username_3**: I was assuming that segments do not overlap, which perhaps may be assuming too much. I will edit it to make it clear.  
> **username_3**: @bddicken: if the segments change, the intersection graph also changes.  
> **username_4**: @bddicken: I think you need to know what is an intersection graph.  An intersection graph is combinatorial, so the existence of a cycle doesn't depend on how it's drawn. http://en.wikipedia.org/wiki/Intersection_graph  

---

