TLDR: In $n$-dimensional space, $n+1$ points do not work in general to solve the unit-agnostic triangulation problem. $n+2$ points work, but only if they do not all lie in the same hypersphere nor the same hyperplane.
Note that $n+1$ points does not work.
In two dimensions: Consider triangulation points $A = (0,0)$, $B = (1,0)$, and $C = (0,1)$ with distances of $d(A,P) = \sqrt{5}k$, $d(B,P) = 2k$, $d(C,P) = \sqrt{2}k$.
This is satisfied by $P = (1,2)$ and $k=1$ as well as $P' = (3/5,4/5)$ and $k' = \frac{1}{\sqrt{5}}$.
In fact, through quite a bit of symbolic manipulation (which I can provide if requested), one can show that "unit-agnostic triangulation" with $n+1$ points, like regular triangulation with only $n$ points, will give at most 2 solutions.
Now, $n+2$ points doesn't always works to specify a unique point.
In regular triangulation, going from $n$ to $n+1$ is easier because $n$ points specify a hyperplane and the two candidate points will be reflections of each other in that plan. The $n+1$st point outside that plane will be closer to one than the other, and thus that last distance will specify which of the required points is to be selected.
However, in the case of unit-agnostic triangulation, the situation is far from simple. In the example I give above, let $D = (1,1)$. Then $d(D,P) = 1 = k$ and $d(D,P') = \sqrt{.2^2+.4^2} = \frac{1}{\sqrt{5}} = k'$. So in this case, four points are not enough to distinguish between $P$ and $P'$.
The issue is that $D$ is on a circle with $A,B,C$. In general, in $n$ dimensions, $n+1$ (non-coplanar) points uniquely determine a hypersphere. In fact, I make the following claim:
CLAIM: Consider the space $\mathbb{R}^n$ and suppose we have $n+2$ points $x_1,\dots,x_{n+2}$. Suppose not all of them are in the same hyperplane or hypersphere. Then for any given and known constants $c_i>0$, there is at most one point $y$ satisfying $||y - x_i|| = kc_i$ for an unknown scale factor $k$.
(I will be using subscripts to denote points within a sequence and superscripts to denote coordinates of a point. So $x_2^1$ is the first coordinate of the point $x_2$.)
Since not all of them are in the same hyperplane, pick $n+1$ of them which satisfy this property, and reorder as necessary to make them the first $n+1$.
As mentioned above, using just these $n+1$ points will give us exactly two solutions $(y,k)$ and $(y',k')$ with $k \neq k' \neq 0$.
Now consider the locus of all points $z$ such $\frac{||z-y||}{||z-y'||} = \frac{k}{k'}$. Rearranging and squaring, we have $$\sum_{j=1}^n (z^j-y^j)^2 = \left(\frac{k}{k'}\right)^2 \sum_{j=1}^n (z^j-y'^j)^2$$
Putting everything on the same side, we get a quadratic equation of the form $$\left(1 - \frac{k^2}{k'^2}\right)\sum_{j=1}^n (z^j)^2 + (\text{linear stuff}) = 0$$ which, as $1 - \frac{k^2}{k'^2}$ is a nonzero constant, is the equation of a hypersphere.
This hypersphere contains all of the points $x_1,\dots,x_{n+1}$ because, by our construction of the two candidate solutions $y$ and $y'$, we have $||x_i-y|| = kc_i$ and $||x_i-y'|| = k'c_i$, so $\frac{||x_i-y||}{||x_i-y'||} = \frac{k}{k'}$.
So if, as per hypothesis, $x_{n+2}$ is outside said hypersphere and so $\frac{||x_{n+2}-y||}{||x_{n+2}-y'||} \neq \frac{k}{k'}$. This means that $\frac{||x_{n+2}-y||}{k} \neq \frac{||x_{n+2}-y'||}{k'}$, so $c_{n+2}$ cannot take on both of these distinct values, therefore distinguishing between $(y,k)$ and $(y',k')$ as solutions.
I've thought of this problem before in a slightly different, but equivalent context -- suppose we have a point energy source (i.e. light, sound) of unknown intensity and position, whose output attenuates according to the inverse square law -- i.e. the intensity at point $x$ is $\frac{I_0}{||x-x_0||^2}$ where $I_0$ is the absolute output and $x_0$ the location of the source.
How many detectors, each of which measures the intensity of the output at a given point, is necessary to determine $x_0$ and $I_0$? The answer is $n+2$ detectors, not in a hypersphere or hyperplane.
The nitty-gritty math: (Subscripts $i$ will range from $1$ to $n+1$ denoting reference points. Superscripts $j$ will range from $1$ to $n$ denoting coordinates.)
We have a system of equations
$$\sum_{j=1}^n \left(y^j - x_i^j\right)^2 = k^2c_i^2$$
Taking the equation for $i=n+1$ and subtracting it from the others, we get
$$\sum_{j=1}^n \left(-2y^jx_i^j + (x_i^j)^2 + 2y^jx_{n+1}^j - (x_{n+1}^j)^2\right) = k^2(c_i^2-c_{n+1}^2)$$
Simplifying,
$$\sum_{j=1}^n (x_{n+1}^j-x_i^j)y_j + \frac{c_{n+1}^2-c_i^2}{2}k^2 = \frac{1}{2}\left( - ||x_i||^2 + ||x_{n+1}||^2\right)$$
This is a system of linear equations in $n+1$ variables, namely $y^1,\dots,y^n$ and $k^2$ (Yes, I'm treating $k^2$ as an independent variable. Since $k>0$ necessarily, this is fine.)
Now this is a matrix equation which we will write using block matrices as $\begin{pmatrix}D & c\end{pmatrix}\begin{pmatrix} y \\ k^2\end{pmatrix} = b$ where:
- The rows of $D$ are vectors of the form $x_{n+1}-x_i$
- $c$ is a column vector consisting of entries $\frac{1}{2}(c_{n+1}^2-c_i^2)$
- $y$ is the point in question and $k^2$ the scale factor
- $b$ is a column vector consisting of entries $\frac{1}{2}(||x_{n+1}||^2 - ||x_i||^2)$
If there were a linear dependence among the rows of $D$, it would mean that the points $x_1,\dots,x_{n+1}$ sit in a hyperplane, which contradicts our hypothesis. So these rows are all linearly independent, and $D$ is invertible.
So we can perform row reduction on $D$ to reduce it to the identity. Doing these same row reductions on our system gives:
$$\begin{pmatrix}I_n & c'\end{pmatrix}\begin{pmatrix} y \\ k^2\end{pmatrix} = b'$$ which has the parametrized solution $y^j = -c'^jk^2 + b'^j$ for each coordinate $1 \leq j \leq n$.
Now we still have one more equation to use - the original condition for $x_{n+1}$, which is $$\sum_{j=1}^n \left(y^j - x_{n+1}^j\right)^2 = k^2c_{n+1}$$ Substituting for $y^j$, we get $$\sum_{j=1}^n \left(-c'^jk^2 + b'^j - x_{n+1}^j\right)^2 = k^2c_{n+1}$$ which is a quadratic equation in $k^2$, having at most two solutions. Solving for $k^2$ and plugging back into our parametrized solution gives at most two pairs $(y,k)$ and $(y',k')$ which could solve the unit-agnostic triangulation problem.
