7
$\begingroup$

This is a geographic problem, where we have several connected graphs embedded on the plane, where none of them have overlapping edges/nodes.

How can we divide the plane using line segments in such a way that each subdivision contains exactly one connected component?

I was thinking of generating a voronoi diagram using the endpoints, but this presents some issues:

  1. Long edges are not guaranteed to be in the correct partition.
  2. The border becomes very complex (There is a separate line segment for most points)

Is there an algorithm that creates less complex borders?

The input would be a planar graph with multiple connected components, where each node has coordinates associated to it.

The output would be a subdivision for the bounding box given by the graph, which divides the plane using line segments.

Example solution using red lines Example, where the red lines are a possible solution I'm looking to minimize the amount of line segments required, but optimality is not required.

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ Thanks for the helpful edits! It sounds like your problem can be reduced to: given two sets of points $A,B$, find a path with the minimum number of line segments that puts all of $A$ on one side and all of $B$ on the other side. If you can solve that, you can use that to solve your problem, by applying it $n-1$ times, where $n$ is the number of connected components. $\endgroup$
    – D.W. ♦
    Mar 15, 2019 at 23:18
  • $\begingroup$ I think that's a good approach. Do you know of a specific algorithm? $\endgroup$
    – b9s
    Mar 16, 2019 at 12:40

3 Answers 3

Reset to default
1
$\begingroup$

This is not a full answer to your question, but at least you'll have something working.

Step 1. Calculate minimal bounding axis-aligned boxes for each connected component, and also a minimal "outer" bounding box for all the components.

Step 2. Try to split the outer bounding box by horizontal or vertical segment in such a way that this segment doesn't intersect with any bounding boxes for components - this can be done by analyzing coordinates of bounding boxes only. If that is not possible then split the outer box in halves horizontally or vertically. After splitting recalculate bounding boxes for components which were split as well.

Step 3. Repeat the Step 2 recursively for each box, which contains more than one component.

Step 4. After the Step 3 you'll have a partition of the original outer box into rectangles, each of which contain only one connected component (or part of it). Remove all the edges in this partition, for which both adjacent rectangles contain the same component. After this step you'll have a partition of the outer box, but it won't be a optimal one, and it'll consist of axis-aligned segments only.

Step 5. Amend the partition, replacing axis-aligned segments by arbitrary segments, trying to minimize the total number of segments - I don't know how to do that regularly for now.

Improve this answer
$\endgroup$
0
$\begingroup$

What about taking the convex hull of every connected component?

The two operations you can do after this is :

  1. There are 2 convex hulls but these components can be divided by a single line
  2. The convex hulls of 2 separate connected components intersect

For (1), we can take the centre of both of the convex hulls, draw a line joining them (call it AB). A line that passes the midpoint of AB should be able to separate them.

For (2), Say line AB and CD intersect at X. AB is the line in hull 1, CD is the line in hull 2.

Now there are a couple of scenarios here: 1. AB and CD crosses such that the point B is inside hull 2 and point D is inside hull 1 (imagine 2 rhombuses (diamonds?) coming together from the corners to form a tinier rhombus). In this case, add B to hull 2 and add A to hull 1. Note that now the hulls will no longer remain convex. 2. AB and CD crosses such that the point B remains inside hull2 but neither C nor D is inside hull 1 (imagine a line cutting off a corner). Again in this case, just add point B to hull2 (thereby making hull2 lose its convex property)

And repeat for all line segments until it converges.

Or something of this sort..

Improve this answer
$\endgroup$
1
  • $\begingroup$ Seems like an interesting approach. Welcome to the site! $\endgroup$
    – Caleb Stanford
    Apr 17, 2020 at 13:52
-2
$\begingroup$

I'm not sure what "connected" here mean?

-If it means fully connected then that's finding cliques (a problem widely known to used in GIS applications)

-If it's just connected somehow (not indep vertices), then what D.W. clearly implying in his comment is the min-cut problem (ur lines r all zero cuts no edges passing through them) enter image description here *** added 17/4/2020 This Q is dated to Mar 2019, Who brought it into top after one year. I don't like this, I feel deceived and questioning credibility. –

Improve this answer
$\endgroup$
6
  • $\begingroup$ In a connected graph there exists a path between any two nodes in that graph. Maybe you're thinking of a complete graph? In my case, connected graph may not have been the correct word, as my graph consists of many connected components. Because my graph is a planar graph, there should be a way to partition the plane such that each partition contains exactly one connected component. The question is, how can we efficiently compute such a partitioning? $\endgroup$
    – b9s
    Apr 16, 2020 at 8:22
  • $\begingroup$ Then follow the 2nd if (the same as D.W. comment) of repeatedly finding a Min-cut in each resulting partition until its value exceeds zero $\endgroup$
    – ShAr
    Apr 16, 2020 at 12:26
  • $\begingroup$ I assume u know/can find algorithms for it (Edmond Karp maximal flow algorithm is an example) check this lecture for a detailed explanation youtu.be/uM06jHdIC70 $\endgroup$
    – ShAr
    Apr 16, 2020 at 12:37
  • $\begingroup$ I don't see how this can be represented as a min-cut problem without edges between the components. I could add edges between them, but I would already know that the cut will be there. $\endgroup$
    – b9s
    Apr 16, 2020 at 13:02
  • $\begingroup$ See the pic I added?as mentioned in the lecture they used it in WW2 to define min cost cut of supplies of the enemy, in ur pic u want the lines with zero edges passing thru them... Zero is the minimal possible value.You will start between most left & right nodes then repeat in each partition. I hope it is clear now $\endgroup$
    – ShAr
    Apr 16, 2020 at 15:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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