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:


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.

  • $\begingroup$ What is the input to your problem ? A collection of lines ? $\endgroup$ Jan 15, 2013 at 3:51
  • 3
    $\begingroup$ Also, if you have three lines that aren't parallel or concurrent, there will always be one closed region. $\endgroup$ Jan 15, 2013 at 3:53
  • $\begingroup$ 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. $\endgroup$
    – bddicken
    Jan 15, 2013 at 4:08
  • 2
    $\begingroup$ By default, graphs don't have coordinates, and their edges are formally pairs of vertices, not line segments. What is your input really? $\endgroup$
    – Jeffε
    Jan 15, 2013 at 5:21
  • $\begingroup$ 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. $\endgroup$
    – bddicken
    Jan 15, 2013 at 5:26

1 Answer 1


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.

  • $\begingroup$ 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. $\endgroup$
    – bddicken
    Jan 15, 2013 at 16:45
  • $\begingroup$ Also, your statement is not necessarily true... it all depends on how the graph is drawn. $\endgroup$
    – bddicken
    Jan 15, 2013 at 17:58
  • $\begingroup$ 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\} \:$. $\;\;$ $\endgroup$
    – user6973
    Jan 16, 2013 at 4:49
  • 1
    $\begingroup$ @bddicken: if the segments change, the intersection graph also changes. $\endgroup$
    – someone
    Jan 16, 2013 at 7:49
  • 1
    $\begingroup$ @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 $\endgroup$ Jan 17, 2013 at 12:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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