Tell me more ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.
up vote 1 down vote favorite

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.

share|improve this question
What is the input to your problem ? A collection of lines ? – Suresh Venkat♦ Jan 15 at 3:51
3  
Also, if you have three lines that aren't parallel or concurrent, there will always be one closed region. – Suresh Venkat♦ Jan 15 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. – bddicken Jan 15 at 4:08
2  
By default, graphs don't have coordinates, and their edges are formally pairs of vertices, not line segments. What is your input really? – JɛffE Jan 15 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. – bddicken Jan 15 at 5:26

1 Answer

up vote 2 down vote

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.

share|improve this answer
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 Jan 15 at 16:45
Also, your statement is not necessarily true... it all depends on how the graph is drawn. – bddicken Jan 15 at 17:58
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\} \:$. $\;\;$ – Ricky Demer Jan 16 at 4:49
1  
@bddicken: if the segments change, the intersection graph also changes. – someone Jan 16 at 7:49
1  
@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. en.wikipedia.org/wiki/Intersection_graph – Yoshio Okamoto Jan 17 at 12:44
show 1 more comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.