Finding a solution to a simple geometric set of equalities

Question

Let $p_1,\dots,p_n$ be a collection of points in the plane $\mathbb{R}^2$ and let $a$ be a positive number such that $a<1$. Is there a good numerical algorithm to find points $x_1,\dots,x_n$ in the plane such that $$\|x_i - x_{i+1}\| = a(\|x_i - p_i\|+\|p_i-x_{i+1}\|)$$ for all $i$, where we use $n+1\equiv 1$ to simplify notation? A picture for $a=1/3$ is attached, in which the black dots indicate the $p_i$'s, the blue segments indicate the segments from $x_i$ to $x_{i+1}$, and the red segments indicate the $\|x_i - p_i\|+\|p_i-x_{i+1}\|$.

Answer 1

It is easy to find solutions with additional symmetries. Precisely: If $a\neq\cos(\pi m/n)$ there exists exactly one solution such that $|x_k-p_k|=|x_{k+1}-p_k|$ for all $k\in \mathbb{Z} $ (here we denote the sequence $(p_k)$ as an $n$-periodic sequence indicized on $ \mathbb{Z} $).

Indeed, let $u:=e^{i\theta}$ with $\theta=2\arccos a$. By the assumption, $u^n\neq 1$. Starting with $x_0:=x\in\mathbb{C}$, define inductively $x_{k+1}=(x_k-p_k)u+p_k$. The periodicity condition $x_n=x_0$ corresponds then to a non-singular linear equation on $x$ (very easy to write down, which pleasure I won't spoil).

The same procedure produces, more generally, for any $a$ and for any model triangle, with vertices $(0,1 ,u)$ such that $|1-u|=a(1+|u|)$ and $u^n\neq1$, a unique solution such that the triangles with ordered vertices $(p_k,x_k,x_{k+1} )$ are all similar to the fixed triangle with ordered vertices $(0,1,u)$.

Answer 2

Here is an idea for an answer.

For two points p, a solution is given by an ellipse whose eccentricity is a simple function of a (so we know the shape of it) with foci the x's and p's lying on the ellipse. There should be a one parameter family of solutions in this case.

For three points p, a partial solution is given by two ellipses sharing a focal point (x_1 say) of the same shape and p_1 lying on one ellipse and p_3 lying on the second ellipse, which can be extended to a complete solution if the other focal points x_2 and x_3 are themselves focal points of a "good" ellipse ( of the right shape and containing point p_2). You want to find the intersection between the space (partly parameterized by x_1) of x_2 and x_3's and the space of (pairs of foci of) good ellipses. Hopefully this results in a nice (or computationally workable) set of relations between a chosen guess x_1 and the other two points.

Now to the point. In adding a fourth (then fifth , sixth, etc.) p, instead of finding a good ellipse, you want to find a pair of good ellipses which share a focal point, and have previously computed x_2 or x_3 as the other points. Unfortunately, you may not be able to do that. However, you can use your previous work to compute (starting with p_3 and p_4) the space of good foci x'_2 and x'_3, and intersect that with the space you have. Now iterate with the hope (or proof, if you are up to it) perturbations to the later x's don't affect the earlier x's.

Gerhard "Do One Edge Each Time" Paseman, 2016.12.20.

Answer 3

Here is a second idea for an answer. This may blow up computationally if the points are far from the (ordered in clockwise fashion of the) vertices of a convex polygon, but might work if most of them lie on the convex hull.

Compute the convex hull of the given points, and set up trial points which are the vertices of a large scale version of the hull. (Choose extra points near the trial vertices as needed.) Compute the ellipses, and make sure the given points p lie well within the interior. Now move one trial vertex toward its two associated points p_i until the ellipse edges are near or on the p_i. Repeat with each trial vertex until all the ellipses are on or near their respective points. Depending on how good an approximation you want, make several approach passes until you are ready to commit to a final tweak of the trial vertices.

Gerhard "Pretend You Are Playing Horseshoes" Paseman, 2016.12.20.