Balancing a graph

I'm curious: Is the graph planar?

If you want to place n point so that all the mutual separations are equal, you'll need n-1 dimensions to work with:

The configuration on three points is, obviously, an equilateral triangle.
To extend the system by one point, you need to turn the triangle into a regular tetrahedron.

This example forms the basis for an induction, proving that for each new point you need another degree of freedom, hence your task is impossible.
...Maybe I misunderstood the problem.

Regards
Admiral

Quote:

Original post by NotAYakk I'm curious: Is the graph planar?

Actual it's for a uniform uv-mapping. So I think you could cal it a mapping from a polygonal surface in 3 dimensions to a quadratic surface in 2 dimensions.

Quote:

Original post by TheAdmiral If you want to place n point so that all the mutual separations are equal, you'll need n-1 dimensions to work with: The configuration on three points is, obviously, an equilateral triangle. To extend the system by one point, you need to turn the triangle into a regular tetrahedron. This example forms the basis for an induction, proving that for each new point you need another degree of freedom, hence your task is impossible. ...Maybe I misunderstood the problem.

You are probably right; I think I can approximate it though, with some kind of iteration. I can do it brute force but maybe there is some speed up strategies.

There are things called "self organizing graphs" and networks.
Maybe that is something along the lines of what you want? It looks brute-force
but there are likely asumptions made that make it faster than straigt brute force.

Quote:

Original post by Xmon You are probably right; I think I can approximate it though, with some kind of iteration. I can do it brute force but maybe there is some speed up strategies.

I don't mean to disappoint you, but I don't think even the best approximate solution will be good enough.

The first iterative algorithm that comes to mind is the brute-force one you describe; take the node with the highest variance and place it so as to minimise this variance. However, there's no point in trying to speed this algorithm up: All it does is repeatedly take the 'furthest out' node and put it in the middle of the cluster (or at least nearer the middle, to get any benefit). After enough passes, your nodes will all end up more or less on top of one another.

All similar solutions suffer from the same issue. The only way to stop your points converging to a singularity (or diverging to infinity) is to put them in equilibrium, i.e. some symmetric structure such as a regular polygon (so that there is no best or worst candidate for relocation). However, I imagine this formation isn't what you were hoping for.

Perhaps if you explain the nature of the problem, we can help to propose an alternative.

Regards
Admiral

Quote:

Original post by TheAdmiral Quote: Original post by Xmon You are probably right; I think I can approximate it though, with some kind of iteration. I can do it brute force but maybe there is some speed up strategies. I don't mean to disappoint you, but I don't think even the best approximate solution will be good enough. The first iterative algorithm that comes to mind is the brute-force one you describe; take the node with the highest variance and place it so as to minimise this variance. However, there's no point in trying to speed this algorithm up: All it does is repeatedly take the 'furthest out' node and put it in the middle of the cluster (or at least nearer the middle, to get any benefit). After enough passes, your nodes will all end up more or less on top of one another. All similar solutions suffer from the same issue. The only way to stop your points converging to a singularity (or diverging to infinity) is to put them in equilibrium, i.e. some symmetric structure such as a regular polygon (so that there is no best or worst candidate for relocation). However, I imagine this formation isn't what you were hoping for. Perhaps if you explain the nature of the problem, we can help to propose an alternative. Regards Admiral

As I sad earlier this algorithm is for uniform uv-mapping, you could cal it a conversion from a polygonal surface in 3 dimensions to a quadratic surface in 2 dimensions. I have worked out a procedure to stitch a subset of the nodes(vertex) to the boarder of the frame(texture) I'm working in, this will prevent the nodes to conform in the middle. With my algorithm I can uv-map three kinds of meshes, 0-edged(sphere for example), 1-edged(surface) and 2-edged(cylinder). The number of edges has influence of the constraints on the nodes on the boarder. On 0-edged and 2-edged the vertex can just move on its own cardinal line. On 1-edged it can move freely on the whole border. Initially I distribute the nodes on the frame so they get near there final position. But then I stand empty handed, the best thing I can do is begin with the most distorted node, compared to it's neighbours, and place it in a local equilibrium, then do the next and the next... I’m looking for speed up strategies or maybe a whole new algorithm.

/ Simon

What exactly are you trying to do?

I've scene "auto-pelting" implementations that have the user define a cut (so the mesh can be unwrapped to 2d), then treat the mesh as a mass-spring and let it find its equilibirum that way. Works quite well.

Quote:

Original post by playmesumch00ns What exactly are you trying to do?

I'm gonna do a uniform uv-mapping of an arbitrary mesh, so the difference between the texture coordinates are proportional to the distance between vertexes. I ain’t gonna use the uv-coordinates for texturing but for writhing to position and normal textures. It's important to hold track of the boarders so I know how to tile across the edges when calculating on values that accounts on several immediate textels. It's also important for the rest of the algorithm that the sides of texture are quadratic and power-of-2.

Quote:

Original post by playmesumch00ns I've scene "auto-pelting" implementations that have the user define a cut (so the mesh can be unwrapped to 2d), then treat the mesh as a mass-spring and let it find its equilibirum that way. Works quite well.

Interesting, do you have any links?

So you want the distance separation between each node and its neighbours to be roughly uniform? My bad; disregard everything I have said [rolleyes].

A divide-and-conquer approach may be suitable in that case. Is your boundary necessarily rectangular (or triangular)? If so, perhaps you could recursively divide the plane into congurent pieces and shift all the nodes contained so that their mean is central within the plane sector.

Regards
Admiral