0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ What is the actual definition of "discrepancy"? Or is that the question? $\endgroup$ – Igor Rivin Jan 5 '15 at 17:19
  • $\begingroup$ @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. $\endgroup$ – Manfred Weis Jan 5 '15 at 18:01
  • $\begingroup$ Have you checked to see whether there is anything in Kuipers and Niederreiter's book on uniform distribution? $\endgroup$ – Gerry Myerson Jan 6 '15 at 2:32
  • $\begingroup$ @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. $\endgroup$ – Manfred Weis Jan 6 '15 at 12:26
1
$\begingroup$

I think the most reasonable thing to do is to contact Johann Brauchart (who wrote the paper you cited above) and ask him how he computes his discrepancies. He is a very nice guy (I know him quite well), and I'm sure that he is happy to help. Actually he might also be interested in your research, so contacting him is a good idea in any case.

$\endgroup$
  • $\begingroup$ maybe that's the best thing to do; but I will be on vacation with no internet access till March. $\endgroup$ – Manfred Weis Jan 27 '15 at 4:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.