Optimisation problem: connectors

42 Views Asked by At

Suppose there are $n$ distinct points in the $\mathbb{R}^3$ space, namely $P_1,P_2,\ldots,P_n$.

Define the distance matrix $M:=(d_{ij})_{n\times n}$, where $d_{ij}$ denotes the distance of line segment $P_iP_j$.

Define a $\textit{connector}$, $C$, as a ordered set of line segments, where the next element in the set should share a common vertex with the previous one. For example, $\{P_1P_2,P_2P_4,P_4P_7\}$ is a connector, while $\{P_1P_2,P_2P_3,P_4P_5,P_5P_3\}$is not.

Define the $\textit{content}$ of the connector, $\|C\|$, as the set of points which the connector includes. For example, $\|\{P_1P_2,P_2P_4,P_4P_7\}\|=\{P_1,P_2,P_4,P_7\}$.

Define the $\textit{magnitude}$ of the connector, $m(C)$ to be the length of the longest single segment in the connector.

Define the connector to be a $\textit{proper}$ connector if the longest single segment is the first or the last segment in the connector.

A set of points are said to be $\textit{connected}$ if the union of contents of the connectors over the points is the set of points.

The problem is:

Given that $k$ proper connectors($k\leq n$) of the $\textbf{same magnitude}$ $m$ are allowed to connect the $n$ points, find $\min\{m\}$ to achieve this task.

What should the gist of the algorithm be? I have no idea where to start.