Thursday, July 10, 2008

No three in a line

Place N points within a disc to maximize the distance between any point and an edge connecting two other points. The distance between a point and an edge is the minimum distance between the point and any point on the edge (but NOT the edge's extension into an infinite line). Informally, we are trying to avoid "three points on a line (segment)" as much as possible.

For even N>=12, it is better to place one point at the center of the disc and N-1 equally spaced on the edge, than it is to place all N points on the edge. This is probably not the optimal arrangement, though.

If, instead of a disc, we formulate the same problem on the surface of a sphere, with the shorter segment of the geodesic connecting points, then the problem is reminiscent of sphere-packing or placing maximally spaced points on the surface of a sphere.

One might consider other "norms", such as electrostatic repulsion.

One might consider not-complete graphs; that is, points only need to avoid some given edges, as opposed to every possible edge connecting two other points.

No comments :