So I'm currently working on a geometric optimization problem and came upon a graph-problem where I am struggling to find a solution.
Edit:
So let $\{x_i\} \subset \mathbb{R}^2$ and $\{y_j\} \subset \mathbb{R}^2$ such that $i = 1,..., n$ and $j = 1,...,m$. Furthermore for each pair of points $(a, b) \in (\{x_i\}_i\cup \{y_j\}_j) \times (\{x_i\}_i\cup \{y_j\}_j)$ the distance $d(a, b)$ is known. The distance $d$ might be unequal to the euclidean distance. Now I would like to find the minimal path or network of paths such that each $x_i$ is connected to at least one $y_j$ or to be more precise, the problem is:
Find the (undirected, not necessarily connected) graph (V, E) such that $V = \{x_i\}_i \cup \{y_j\}_j$ and following conditions hold:
- Each connected component contains at least one $y_j$.
- For each $y_j$ exists at least one $x_i$ connected to it.
- The total sum of edge-length gets minimized, i.e. $\sum_{k=1}^l length(E_k) \rightarrow min$ with $E = {E_1,..., E_l}$ where the the length of a edge $E_k$ is the distance $d(a, b)$ between its respective nodes $a, b$.
There may be obstacles in the way between some pairs $(x_i, x_j)$ so not all possible edges have the same length, i.e. are weighted.
To give some motivation for this problem: Imagine the $x_i$ are entries to houses which are all inside some domain $G$ and on the boundary of the domain $\partial G$ lie the possible entries $y_j$ to the domain. Now I want to construct a admissible street network such that each house is connected to the boundary, i.e. every person living in some house in this domain can actually leave the domain on a street.
I'm currently a bit lost here. One could try to compute by brute force the correct graph but this sounds like madness, especially as this is part of a bigger computation called more than once.
Any help would be greatly appreciated! Best regards, PlumBum
Edit 2: This is a sort of minimum spanning tree problem, somewhat similar to this What is the best way to connect some street corners with electricity cables using graph theory?. But in this case I allow for several connected-components if certain constraints are fulfilled (to be precise when the boundary is connected to the inside).