<?xml version="1.0" encoding="utf-8"?>
<!DOCTYPE article PUBLIC "-//NLM//DTD JATS (Z39.96) Journal Publishing DTD v1.0 20120330//EN" "JATS-journalpublishing1.dtd">
<article xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink" article-type="research-article">
<front>
<journal-meta>
<journal-id journal-id-type="publisher-id">INFORMATICA</journal-id>
<journal-title-group><journal-title>Informatica</journal-title></journal-title-group>
<issn pub-type="epub">0868-4952</issn><issn pub-type="ppub">0868-4952</issn>
<publisher>
<publisher-name>VU</publisher-name>
</publisher>
</journal-meta>
<article-meta>
<article-id pub-id-type="publisher-id">INFO1099</article-id><article-id pub-id-type="doi">10.15388/Informatica.2016.88</article-id>
<article-categories><subj-group subj-group-type="heading">
<subject>Research Article</subject></subj-group></article-categories>
<title-group>
<article-title>Linear Time Estimators for Assessing Uniformity of Point Samples in Hypercubes</article-title>
</title-group>
<contrib-group>
<contrib contrib-type="Author">
<name><surname>Rudolph</surname><given-names>Günter</given-names></name><email xlink:href="mailto:guenter.rudolph@tu-dortmund.de">guenter.rudolph@tu-dortmund.de</email><xref ref-type="aff" rid="j_INFORMATICA_aff_000"/><xref ref-type="corresp" rid="cor1">*</xref>
</contrib>
<contrib contrib-type="Author">
<name><surname>Wessing</surname><given-names>Simon</given-names></name><email xlink:href="mailto:simon.wessing@tu-dortmund.de">simon.wessing@tu-dortmund.de</email><xref ref-type="aff" rid="j_INFORMATICA_aff_000"/>
</contrib>
<aff id="j_INFORMATICA_aff_000">Fakultät für Informatik, Technische Universität Dortmund, Otto-Hahn-Str. 14, 44227 Dortmund, Germany</aff>
</contrib-group>
<author-notes>
<corresp id="cor1"><label>*</label>Corresponding author.</corresp>
</author-notes>
<pub-date pub-type="epub"><day>01</day><month>01</month><year>2016</year></pub-date><volume>27</volume><issue>2</issue><fpage>335</fpage><lpage>349</lpage><history><date date-type="received"><day>01</day><month>02</month> <year>2016</year></date><date date-type="accepted"><day>01</day><month>05</month> <year>2016</year></date></history>
<permissions><copyright-statement>Vilnius University</copyright-statement><copyright-year>2016</copyright-year></permissions>
<abstract>
<p>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.</p>
</abstract>
<kwd-group>
<label>Keywords</label>
<kwd>uniformity</kwd>
<kwd>measure</kwd>
<kwd>linear time</kwd>
<kwd>hypercube</kwd>
</kwd-group>
</article-meta>
</front>
</article>
