Embedded Files
Thomson problem
Thomson problem
A 100 -year-old problem asking how to distribute N points on a sphere such that the electrostatic energy is minimized. The closer points are to each other, the higher the energy. Known solutions exist for special situations such as regular polygons, but like the Traveling Salesperson Problem, the general case is NP-hard. So progress has only been possible using computational heuristic techniques, e.g., simulated annealing.
As with any non-convex problem, the trick is not settling into a local solution when a better solution lies over the horizon. Perhaps allowing things to get worse before they improve. Many different ML approaches have been applied to this problem, with similar results. However, the combinatorics (graph) provide an unexplored opportunity (see below).
Energy points on a sphere.
A circle packing can always be generated from the triangulation. Locally, the energy is minimized, but a combinatorial opportunity to improve can be recognized.
The graph can be iteratively manipulated finding a new circle packing each time.
Until the points of higher energy are brought together, creating a graph which provides a lower energy distribution.
Previous research has shown that the circle packings reasonably approximate the energy; see here. What we would like to do now, is write code to put these ideas into action. Highly developed open-source code for computing and viewing circle packings is available for use and manipulation; see circlepack. This is all new so any progress would be well received.
Sphere packing in 2.5 dimensions
Sphere packing in 2.5 dimensions
Ken Stephenson has proposed the following question: Attach unit (three-dimensional) spheres to the outside of a cylinder of radius R. What is the maximal density in the region they occupy between the cylinder of radius R and that of radius R+1? Stephenson, asks the question for two different situations, neither for which we have a good guess on the maximal density. Finding evidence to point us in the right direction is the first step. So this is a great opportunity for experimentation with machine learning.
Brooks Quad Packings
Brooks Quad Packings
Patterns, introduced by Robert Brooks, start with a quadrilateral interstice and allow you to make choices about how to place new circles inside. The white 'plug' circle is merely a placeholder so that the combinatorics (graph at any stage will appear to be simply connected and hence will pack correctly.
Page updated
Report abuse