7
$\begingroup$

Let n points in the plane be given whose coordinates we don't know. Assume, however, that for any triple of the points we know the angle.

Question: Can we decide whether the n points are realizable in the plane, i.e. can we determine whether there is an assignment of coordinates to the points such that the angular constraints are satisfied?

$\endgroup$
7
$\begingroup$

I assume that the angles are nonzero and we know which angle corresponds to each triplet. If there are zero angles (collinear points) or the lists of angles and points are unrelated, the problem is harder.

With these assumptions there is a method. First, take any three points. They can be realized in the plane if and only if the three angles add up to $\pi$. Now place these three points in the plane so that the condition is satisfied. (You can do it in any way; different possibilities only differ by scaling, rotation, translation and reflection.)

Then take a fourth point and consider the triplet of the first two and the fourth point. If the three angles of this triplet don't add up to $\pi$, the angles are not realizable. If they do, there are two possible choices for the fourth point since the first two ones are fixed. For both of these options, check whether the angles involving the third point are what they should be. If neither option works, the angles are not realizable. It can never happen that both options work. If one of the options works, it is the only possible way (up to the aforementioned symmetries) to place those four points in the plane with the given angles).

Keep adding points one by one this way. If the angles are realizable, you get the unique (up to the symmetries) realization. If not, you will notice at some point.

An easy first thing to check is to make sure that every triplet can be realized as a triangle. This condition is necessary but not sufficient. I don't know if there is a way to make the check without simultaneously constructing the realization.

$\endgroup$
  • $\begingroup$ I'm glad I could be of help, @Jae! $\endgroup$ – Joonas Ilmavirta Oct 29 '14 at 13:35
4
$\begingroup$

To answer Joonas's comment in the last paragraph: yes, it is possible to check the realizability without constructing the whole realization. It is sufficient to test whether every 5-tuple of points is realizable. (For simplicity, I am also assuming general position, that is, no three points on a line.)

To see this, note that when a new point is being added in Joonas's algorithm, its location is determined by an arbitrary triple of points already drawn. The new point can be drawn if all the triples agree on the same location. If two triples disagree, then there are also two triples sharing two points that disagree. Together with the new point, this makes a 5-tuple that is not realizable.

By some finite case analysis of all 5-tuples, it can be probably shown that testing 4-tuples is also sufficient.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.