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.

  • 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 '19 at 23:18
  • $\begingroup$ I think that's a good approach. Do you know of a specific algorithm? $\endgroup$ – b9s Mar 16 '19 at 12:40

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.


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.