# Practical Algorithm for Comparing the Discrepancy of Point Sets (on Unit Hyper Spheres)

I have devised a simple geometric algorithm for generating a sequence of points on unit hyper spheres; that algorithm depends on a single real parameter, which I would like to optimize in order to get the most dispersed sequence of points.

I have in mind to do the optimization on basis of the generated point sets by utilizing techniques of computational geometry; specifically via nearest neighbor distances, after having removed "outliers".

What I think should work, is to sort the nearest neighbor distances in descending order and deem the lexically smaller to be the better one; the parameter that yields the "best" sequence could then be approximated iteratively via some one dimensional minimization algorithm, e.g. golden section search.
"Outliers" could be defined on basis of a Delaunay triangulation: a point shall be called a boundary point if it is a boundary point of the union of adjacent Delaunay triangle (or, simplices); a point shall be called an "outlier" if it is either boundary point or adjacent to a boundary point in the DT graph.

Question:
would outlined method be a practical way of finding the parameter, that yields the point set with the least discrepancy or, what alternatives exist to optimize the parameter w.r.t. low discrepancy of the generated point set?

Just for clarification:
I don't want to learn how to generate Low Discrepancy point sets on (hyper) spheres; that is already satisfactorily explained here http://www.mcqmc2012.unsw.edu.au/slides/MCQMC2012_Brauchart.pdf, but I have different method, whose quality I want to optimize and judge empirically.

• What is the actual definition of "discrepancy"? Or is that the question? – Igor Rivin Jan 5 '15 at 17:19
• @IgorRivin the definition is not the problem; an overview can be found here: en.wikipedia.org/wiki/Discrepancy_of_a_sequence; for the special case of spheres, it is described here: arxiv.org/abs/1408.4609. – Manfred Weis Jan 5 '15 at 18:01
• Have you checked to see whether there is anything in Kuipers and Niederreiter's book on uniform distribution? – Gerry Myerson Jan 6 '15 at 2:32
• @GerryMyerson I haven't read that book and I also don't have access to it; but, as none of the articles related to low discrepancy mention parameter-dependent distribution of points, I would be surprised to find my problem addressed in that book. – Manfred Weis Jan 6 '15 at 12:26