0th pass version of solver? #11

New Issue

glen · 2024-01-22T22:37:23Z

glen commented

2024-01-22 22:37:23 +00:00

Per discussion with @Vectornaut today:

A potential specification for an initial toy solver is one that would allow specifications like "A is a point," "B is a plane", and "C and D are incident", where two points would be identical if incident, and perhaps the same for planes, or perhaps incident planes are simply non-parallel ones -- unclear. (A point and plane are incident if one contains the other.) Then the solver would return (presumably rational) coordinates for each object that satisfy the constraints.

However, the difficulty is that if all we have are such constraints, then there is always a trivial solution of making all points be the origin and all planes be the xy plane. So to make this a non-trivial exercise, perhaps we need in addition one or more of the following:

To return some sort of description of all solutions
To return the solution closest in some sense to specified coordinates for all of the points (and perhaps also the planes)
Add constraints of the form "A and B are not incident" (or at least that two points are distinct)
Add constraints of the form "The coordinates of A are such-and-such rational numbers."

There may be other reasonable changes to get beyond the trivial solver.

Per discussion with @Vectornaut today: A potential specification for an initial toy solver is one that would allow specifications like "A is a point," "B is a plane", and "C and D are incident", where two points would be identical if incident, and perhaps the same for planes, or perhaps incident planes are simply non-parallel ones -- unclear. (A point and plane are incident if one contains the other.) Then the solver would return (presumably rational) coordinates for each object that satisfy the constraints. However, the difficulty is that if all we have are such constraints, then there is always a trivial solution of making all points be the origin and all planes be the xy plane. So to make this a non-trivial exercise, perhaps we need in addition one or more of the following: * To return some sort of description of all solutions * To return the solution closest in some sense to specified coordinates for all of the points (and perhaps also the planes) * Add constraints of the form "A and B are not incident" (or at least that two points are distinct) * Add constraints of the form "The coordinates of A are such-and-such rational numbers." There may be other reasonable changes to get beyond the trivial solver.

glen commented

2024-10-23 05:47:56 +00:00

@Vectornaut: The engine prototype you are currently working on (as discussed, please file an associated issue) certainly allows constraints that are not satisfied by the trivial arrangement of all points being the origin and all planes being the xy plane; for example, one can specify that two planes are perpendicular. Would you say therefore that this issue is now moot? Shall we close it?

@Vectornaut: The engine prototype you are currently working on (as discussed, please file an associated issue) certainly allows constraints that are not satisfied by the trivial arrangement of all points being the origin and all planes being the $xy$ plane; for example, one can specify that two planes are perpendicular. Would you say therefore that this issue is now moot? Shall we close it?

Vectornaut commented

2024-10-23 16:36:11 +00:00

Yes, I agree that we can close this issue, because we can now use frozen-component constraints to keep points from being at infinity.

I should mention that you can have degeneracy issues even when not every generalized sphere is the xy plane. If every point is in the same place, making every generalized sphere pass through that place is enough to trivially satisfy all point-on-generalized-sphere constraints. In all the examples I can think of right now, this is mostly ruled out by angle constraints between the generalized spheres, but more complicated ones than just fixing a single angle. For example, if three generalized spheres are mutually tangent with opposing orientations, no point can lie on all three of them, unless one of them collapses to zero radius.

I think our "sphere in tetrahedron" test problem takes advantage of a similar phenomenon: because of the constraints that set the dihedral angles between the side planes and keep the side planes tangent to the inscribed sphere, no point can lie on all four side planes unless the inscribed sphere collapses to zero radius.

Yes, I agree that we can close this issue, because we can now use frozen-component constraints to keep points from being at infinity. I should mention that you can have degeneracy issues even when not every generalized sphere is the $xy$ plane. If every point is in the same place, making every generalized sphere pass through that place is enough to trivially satisfy all point-on-generalized-sphere constraints. In all the examples I can think of right now, this is mostly ruled out by angle constraints between the generalized spheres, but more complicated ones than just fixing a single angle. For example, if three generalized spheres are mutually tangent with opposing orientations, no point can lie on all three of them, unless one of them collapses to zero radius. I think our "sphere in tetrahedron" test problem takes advantage of a similar phenomenon: because of the constraints that set the dihedral angles between the side planes and keep the side planes tangent to the inscribed sphere, no point can lie on all four side planes unless the inscribed sphere collapses to zero radius.

glen commented

2024-10-23 16:44:57 +00:00

no point can lie on all four side planes unless the inscribed sphere collapses to zero radius.

Right, which can't literally happen because we have no coordinates for a "zero-radius sphere". And moreover, as far as I can see, there's no reason for the optimization to be attracted to ever-smaller radii of the central sphere, since it can satisfy the constraints for any sphere radius, and because of the dihedrals, it doesn't get any easier (e.g., the dimension of the solution set doesn't increase) in case the radius of the central sphere could go to zero.

Closing this issue.

> no point can lie on all four side planes unless the inscribed sphere collapses to zero radius. Right, which can't literally happen because we have no coordinates for a "zero-radius sphere". And moreover, as far as I can see, there's no reason for the optimization to be attracted to ever-smaller radii of the central sphere, since it can satisfy the constraints for any sphere radius, and because of the dihedrals, it doesn't get any easier (e.g., the dimension of the solution set doesn't increase) in case the radius of the central sphere could go to zero. Closing this issue.

glen closed this issue

2024-10-23 16:44:57 +00:00

Sign in to join this conversation.