Divide and Conquer Algorithm for 1-Median Problem

Question

Let $P_1$ and $P_2$ be two disjoint point sets in $\mathbb{R}^d$ and $n = \vert P_1\vert = \vert P_2\vert$ and $P = P_1\cup P_2$. Let $c^\star$ be the optimal 1-median for $P$ and $opt^\star$ is the cost of assigning all points of $P$ to $c^\star$(the sum of the distances of all points of $P$ to $c^\star$).

For $j\in \{1,2\}$, let $c_j^\star$ is the optimal 1-median of $P_j^\star$ and and let $\hat{c}$ is the optimal 1-median of the 2-point set $\{c_1^\star,c_2^\star\}$. Let $\hat{opt}$ be the cost of assigning all point of $P$ to $\hat{c}$.

My question is that

1. Does the ratio $\frac{\hat{opt}}{opt^\star}$ is bounded from above by some quantity or there exists "bad" instances (perhaps low dimensional) where it is lower bounded? (My guess is that the latter is true)
2. What is the situation for finite metric spaces?
3. What about the "means" or the centroid?

The obvious motivation for the question is that if the "divide and conquer" strategy works for the problem : Given a finite point set, partition it and compute the medians for each partion and the output the median of medians.

Answer 1

Let $opt^{*}(P_{1})$, $opt^{*}(P_{2})$, and $opt^{*}(P)$ denote the optimal $1$-median costs of $P_{1}$, $P_{2}$, and $P$, repsectively.

We show that $\hat{opt} \leq 3 \cdot opt^{*}(P)$ using the following sequence of inequalities:

\begin{align} \hat{opt} &\leq opt^{*}(P_{1}) + opt^{*}(P_{2}) + n \cdot d(c_{1}^{*},\hat{c}) + n \cdot d(c_{2}^{*},\hat{c}) , \quad \textrm{(using triangle inequality)}\\ &\leq opt^{*}(P) + n \cdot d(c_{1}^{*},\hat{c}) + n \cdot d(c_{2}^{*},\hat{c}) \\ &\leq opt^{*}(P) + n \cdot (d(c_{1}^{*},c^{*}) + d(c_{2}^{*},c^{*})) \quad \textrm{$\because \hat{c}$ is optimal $1$-median for $c_{1}^{*}$ and $c_{2}^{*}$}\\ &\leq opt^{*}(P) + \sum_{x \in P_{1}} (d(x,c_{1}^{*}) + d(x,c^{*})) + \sum_{x \in P_{2}} (d(x,c_{2}^{*}) + d(x,c^{*})), \\ & \quad \quad \textrm{(using triangle inequality)}\\ &= opt^{*}(P) + opt^{*}(P_{1}) + opt^{*}(P_{2}) + opt^{*}(P) \\ &\leq 3 \cdot opt^{*}(P) \end{align}

The above result also holds for the finite metric spaces. Furthermore, for the $1$-means cost function in general metric spaces, you can use the approximate triangle inequality: $d^{2}(a,b) \leq 2 \cdot (d^{2}(a,c) + d^{2}(c,b))$. This will give $\hat{opt} \leq 10 \cdot opt^{*}(P)$