Content-type: text/html
This program divides a set of points on the unit sphere into subsets. The purpose of the program is either to divide the pointsets into subsets that are equally spread over the sphere, or to find a single subset containing points that are optimally spread over the sphere.
Unless the -singlesubset option is specified, each point in the input point set is assigned to a subset. The program searches for a division where the sets of points in each subset are equally spread over the sphere. Specifically, each point is modelled as the axis of a pair of identically charged particles on the sphere, and the program searches for a configuration that minimizes the electrostatic energy of pairs in the same subset. See Jansons and Alexander, Inverse Problems 19:1030-1046 (2003).
The purpose of this is to provide subsets that are equally spread over the sphere, while not overlapping. If the input point set is isotropic (for example, one of the sets PointSets/Elec???.txt) then the union of the subsets is also isotropic.
The program works best with evenly-sized subsets. The optimization does not take account of the size of each subset, so a division of 60 points into one subset of 50 and one subset of 10 would be biased, because the larger subset has more charges and hence higher energy. Also, changes in the configuration are proposed at random and hence a subset containing relatively few points will be modified less often, because it is less likely that one of its points will be chosen as part of a candidate state change.
To search for a single subset, with the rest of the points in undefined order, see the -singlesubset option. When this is specified, the program searches for a subset of specified size, such that the electrostatic energy of the points in the subset is minimal.
The program uses simulated-annealing optimization to search for the best configuration. By default, the annealing schedule is calibrated automatically, though each of the annealing parameters may be changed at run time. The calibration of the temperature is done by finding a local minimum from a random initial configuration, and then calculating the mean increase in energy of subsequent random configuration changes. The temperature is set such that a configuration that increases the energy by the mean amount has a 70% chance of being accepted.
Each candidate configuration change involves swapping two points that are in different subsets. The change is accepted or rejected depending on the difference in energy of the new configuration E_1 and the old configuration E_0 and the temperature T. We generate a random number alpha from the uniform distribution U[0,1]. The probability of accepting the configuration change is then
p = max { 1.0, exp[-(E_1 - E_0) / T)] }
After n = 1000 attempted configuration changes, the temperature T is lowered to T(1-e), where e = 10^{-7}. Custom values of the temperature T, the cooling factor e and the number of trials n may be specified on the command line. The defaults have been chosen to give consistently good results over a range of different problems. To speed up an optimization, setting e = 1E-6 is the recommended option.
For more details of the algorithm see Cook et al, Proc ISMRM 2005, p. 1305.
The output is the input point set ordered according to the subsets. If there are S subsets each containing P points, then the first P points in the output are the first subset, the second P points are the next subset, and so on. Because the optimization takes a long time, the program saves its state approximately every hour to two files. The root file name is specified by the option -savestate. The file root.state contains the current state of the system, the file root.lowestEnergy contains the lowest energy state found so far.
The first line of the output contains information about the state of the system. The format is: <number of points> <number of subsets> <points in each subset> <temperature when file was written> <total energy> <energy of each subset>.
A run may be resumed from a saved state by using the -resume option. See OPTIONS.
Find three equally-sized subsets from an electrostatically-minimized point set of 60 directions. When using the -numsubsets option, the number of points must divide equally into the subsets.
subsetpoints -numpoints 60 -numsubsets 3 -savestate ./elec60_3 > elec60_3.points
Alternatively, we can specify the number of subsets and their size explicitly. This is necessary if the number of points cannot be equally divided.
subsetpoints -numpoints 61 -pointspersubset 16 15 15 15 -savestate ./elec061_4 > elec060_4.points
Resume a previous run of the above optimization.
subsetpoints -resume elec061_4.lowestEnergy -savestate elec061_4_resume > elec061_4
Resume but set the temperature manually
subsetpoints -resume elec061_4.lowestEnergy -savestate elec061_4_resume -temperature 0.1 > elec061_4
Start an optimization with a point set defined in a file. Point sets in files must be in one of the formats readable by pointset2scheme (see pointset2scheme(1)).
cat mypoints.txt | subsetpoints -numsubsets 4 -savestate ./mypoints > mypoints60.subsets
Search for the best 10 out of 52 directions, where the remaining 50 directions are in an undefined order.
subsetpoints -numpoints 52 -singlesubset 10 -savestate ./elec52_best10 > elec52_best10.points
hence this option searches for the lowest-energy P out of N points. If this is
specified, the -numbsubsets option and -pointspersubset option should not be
specified.