Informatica Logo

International Journal

Main Page
Editorial Board
Instructions to Authors
Subscription Information

Author Index
Papers in Production

INFORMATICA, 2016, Vol. 27, No. 2, 335-349
© Institute of Mathematics and Informatics,

ISSN 0868-4952

Linear Time Estimators for Assessing Uniformity of Point Samples in Hypercubes


Fakultät für Informatik, Technische Universität Dortmund Otto-Hahn-Str. 14, 44227 Dortmund, Germany E-mail:,


We investigate the problem of detecting a point set's deviation from uniformity in the unit hypercube. High uniformity is for example desirable in Monte Carlo methods for numerical integration, but also for obtaining a good worst-case bound in global optimization. In high dimensions, many points are required to get reliable results, so the point sets are preferably generated by fast methods such as quasirandom sequences. Unfortunately, assessing their uniformity often requires quadratic time. So, we present several numerical summary characteristics of point sets that can be computed in linear time. They do not measure uniformity directly, but by comparing them to reference values for the uniform distribution, deviations from uniformity can be quickly detected. The necessary reference values are also derived here, if possible exactly, else approximately.


uniformity, measure, linear time, hypercube

1Corresponding author.
To preview Lithuanian abstract see full article text

PDFTo preview full article text in PDF format click here

Get Free ReaderYou could obtain free Acrobat Reader from Adobe

TopTop Copyright © INFORMATICA, Vilnius University Institute of Mathematics and Informatics, 2010