Transforming the Challenge of Constructing Low-Discrepancy Point Sets into a Permutation Selection Problem Article Swipe

PDF

François Clément , Carola Doerr , Kathrin Klamroth , Luís Paquete ·

YOU? · · 2024 · Open Access · · DOI: https://doi.org/10.48550/arxiv.2407.11533

Low discrepancy point sets have been widely used as a tool to approximate continuous objects by discrete ones in numerical processes, for example in numerical integration. Following a century of research on the topic, it is still unclear how low the discrepancy of point sets can go; in other words, how regularly distributed can points be in a given space. Recent insights using optimization and machine learning techniques have led to substantial improvements in the construction of low-discrepancy point sets, resulting in configurations of much lower discrepancy values than previously known. Building on the optimal constructions, we present a simple way to obtain $L_{\infty}$-optimized placement of points that follow the same relative order as an (arbitrary) input set. Applying this approach to point sets in dimensions 2 and 3 for up to 400 and 50 points, respectively, we obtain point sets whose $L_{\infty}$ star discrepancies are up to 25% smaller than those of the current-best sets, and around 50% better than classical constructions such as the Fibonacci set.

Related Topics

Combinatorics

Computer Science

Mathematics

Artificial Intelligence

Physics

Geometry

Acoustics

Concepts

Selection (genetic algorithm) Permutation (music) Point (geometry) Combinatorics Computer science Mathematics Artificial intelligence Physics Geometry Acoustics

Metadata

Type: preprint
Language: en
Landing Page: http://arxiv.org/abs/2407.11533
PDF: https://arxiv.org/pdf/2407.11533
OA Status: green
Related Works: 10
OpenAlex ID: https://openalex.org/W4403754521

All OpenAlex metadata

Raw OpenAlex JSON

OpenAlex ID: https://openalex.org/W4403754521

Canonical identifier for this work in OpenAlex
DOI: https://doi.org/10.48550/arxiv.2407.11533

Digital Object Identifier
Title: Transforming the Challenge of Constructing Low-Discrepancy Point Sets into a Permutation Selection Problem

Work title
Type: preprint

OpenAlex work type
Language: en

Primary language
Publication year: 2024

Year of publication
Publication date: 2024-07-16

Full publication date if available
Authors: François Clément, Carola Doerr, Kathrin Klamroth, Luís Paquete

List of authors in order
Landing page: https://arxiv.org/abs/2407.11533

Publisher landing page
PDF URL: https://arxiv.org/pdf/2407.11533

Direct link to full text PDF
Open access: Yes

Whether a free full text is available
OA status: green

Open access status per OpenAlex
OA URL: https://arxiv.org/pdf/2407.11533

Direct OA link when available
Concepts: Selection (genetic algorithm), Permutation (music), Point (geometry), Combinatorics, Computer science, Mathematics, Artificial intelligence, Physics, Geometry, Acoustics

Top concepts (fields/topics) attached by OpenAlex
Cited by: 0

Total citation count in OpenAlex
Related works (count): 10

Other works algorithmically related by OpenAlex

Full payload

id	https://openalex.org/W4403754521
doi	https://doi.org/10.48550/arxiv.2407.11533
ids.doi	https://doi.org/10.48550/arxiv.2407.11533
ids.openalex	https://openalex.org/W4403754521
fwci
type	preprint
title	Transforming the Challenge of Constructing Low-Discrepancy Point Sets into a Permutation Selection Problem
biblio.issue
biblio.volume
biblio.last_page
biblio.first_page
topics[0].id	https://openalex.org/T12404
topics[0].field.id	https://openalex.org/fields/26
topics[0].field.display_name	Mathematics
topics[0].score	0.9526000022888184
topics[0].domain.id	https://openalex.org/domains/3
topics[0].domain.display_name	Physical Sciences
topics[0].subfield.id	https://openalex.org/subfields/2612
topics[0].subfield.display_name	Numerical Analysis
topics[0].display_name	Mathematical Approximation and Integration
is_xpac	False
apc_list
apc_paid
concepts[0].id	https://openalex.org/C81917197
concepts[0].level	2
concepts[0].score	0.6854507923126221
concepts[0].wikidata	https://www.wikidata.org/wiki/Q628760
concepts[0].display_name	Selection (genetic algorithm)
concepts[1].id	https://openalex.org/C21308566
concepts[1].level	2
concepts[1].score	0.6722303628921509
concepts[1].wikidata	https://www.wikidata.org/wiki/Q7169365
concepts[1].display_name	Permutation (music)
concepts[2].id	https://openalex.org/C28719098
concepts[2].level	2
concepts[2].score	0.6075044274330139
concepts[2].wikidata	https://www.wikidata.org/wiki/Q44946
concepts[2].display_name	Point (geometry)
concepts[3].id	https://openalex.org/C114614502
concepts[3].level	1
concepts[3].score	0.4330011010169983
concepts[3].wikidata	https://www.wikidata.org/wiki/Q76592
concepts[3].display_name	Combinatorics
concepts[4].id	https://openalex.org/C41008148
concepts[4].level	0
concepts[4].score	0.41489097476005554
concepts[4].wikidata	https://www.wikidata.org/wiki/Q21198
concepts[4].display_name	Computer science
concepts[5].id	https://openalex.org/C33923547
concepts[5].level	0
concepts[5].score	0.40036168694496155
concepts[5].wikidata	https://www.wikidata.org/wiki/Q395
concepts[5].display_name	Mathematics
concepts[6].id	https://openalex.org/C154945302
concepts[6].level	1
concepts[6].score	0.2339693009853363
concepts[6].wikidata	https://www.wikidata.org/wiki/Q11660
concepts[6].display_name	Artificial intelligence
concepts[7].id	https://openalex.org/C121332964
concepts[7].level	0
concepts[7].score	0.12409135699272156
concepts[7].wikidata	https://www.wikidata.org/wiki/Q413
concepts[7].display_name	Physics
concepts[8].id	https://openalex.org/C2524010
concepts[8].level	1
concepts[8].score	0.09173348546028137
concepts[8].wikidata	https://www.wikidata.org/wiki/Q8087
concepts[8].display_name	Geometry
concepts[9].id	https://openalex.org/C24890656
concepts[9].level	1
concepts[9].score	0.0
concepts[9].wikidata	https://www.wikidata.org/wiki/Q82811
concepts[9].display_name	Acoustics
keywords[0].id	https://openalex.org/keywords/selection
keywords[0].score	0.6854507923126221
keywords[0].display_name	Selection (genetic algorithm)
keywords[1].id	https://openalex.org/keywords/permutation
keywords[1].score	0.6722303628921509
keywords[1].display_name	Permutation (music)
keywords[2].id	https://openalex.org/keywords/point
keywords[2].score	0.6075044274330139
keywords[2].display_name	Point (geometry)
keywords[3].id	https://openalex.org/keywords/combinatorics
keywords[3].score	0.4330011010169983
keywords[3].display_name	Combinatorics
keywords[4].id	https://openalex.org/keywords/computer-science
keywords[4].score	0.41489097476005554
keywords[4].display_name	Computer science
keywords[5].id	https://openalex.org/keywords/mathematics
keywords[5].score	0.40036168694496155
keywords[5].display_name	Mathematics
keywords[6].id	https://openalex.org/keywords/artificial-intelligence
keywords[6].score	0.2339693009853363
keywords[6].display_name	Artificial intelligence
keywords[7].id	https://openalex.org/keywords/physics
keywords[7].score	0.12409135699272156
keywords[7].display_name	Physics
keywords[8].id	https://openalex.org/keywords/geometry
keywords[8].score	0.09173348546028137
keywords[8].display_name	Geometry
language	en
locations[0].id	pmh:oai:arXiv.org:2407.11533
locations[0].is_oa	True
locations[0].source.id	https://openalex.org/S4306400194
locations[0].source.issn
locations[0].source.type	repository
locations[0].source.is_oa	True
locations[0].source.issn_l
locations[0].source.is_core	False
locations[0].source.is_in_doaj	False
locations[0].source.display_name	arXiv (Cornell University)
locations[0].source.host_organization	https://openalex.org/I205783295
locations[0].source.host_organization_name	Cornell University
locations[0].source.host_organization_lineage	https://openalex.org/I205783295
locations[0].license
locations[0].pdf_url	https://arxiv.org/pdf/2407.11533
locations[0].version	submittedVersion
locations[0].raw_type	text
locations[0].license_id
locations[0].is_accepted	False
locations[0].is_published	False
locations[0].raw_source_name
locations[0].landing_page_url	http://arxiv.org/abs/2407.11533
locations[1].id	doi:10.48550/arxiv.2407.11533
locations[1].is_oa	True
locations[1].source.id	https://openalex.org/S4306400194
locations[1].source.issn
locations[1].source.type	repository
locations[1].source.is_oa	True
locations[1].source.issn_l
locations[1].source.is_core	False
locations[1].source.is_in_doaj	False
locations[1].source.display_name	arXiv (Cornell University)
locations[1].source.host_organization	https://openalex.org/I205783295
locations[1].source.host_organization_name	Cornell University
locations[1].source.host_organization_lineage	https://openalex.org/I205783295
locations[1].license
locations[1].pdf_url
locations[1].version
locations[1].raw_type	article
locations[1].license_id
locations[1].is_accepted	False
locations[1].is_published
locations[1].raw_source_name
locations[1].landing_page_url	https://doi.org/10.48550/arxiv.2407.11533
indexed_in	arxiv, datacite
authorships[0].author.id	https://openalex.org/A5101458757
authorships[0].author.orcid	https://orcid.org/0000-0001-9206-3698
authorships[0].author.display_name	François Clément
authorships[0].author_position	first
authorships[0].raw_author_name	Clément, François
authorships[0].is_corresponding	False
authorships[1].author.id	https://openalex.org/A5040561209
authorships[1].author.orcid	https://orcid.org/0000-0002-4981-3227
authorships[1].author.display_name	Carola Doerr
authorships[1].author_position	middle
authorships[1].raw_author_name	Doerr, Carola
authorships[1].is_corresponding	False
authorships[2].author.id	https://openalex.org/A5056075291
authorships[2].author.orcid	https://orcid.org/0000-0001-9119-0732
authorships[2].author.display_name	Kathrin Klamroth
authorships[2].author_position	middle
authorships[2].raw_author_name	Klamroth, Kathrin
authorships[2].is_corresponding	False
authorships[3].author.id	https://openalex.org/A5055996291
authorships[3].author.orcid	https://orcid.org/0000-0001-7525-8901
authorships[3].author.display_name	Luís Paquete
authorships[3].author_position	last
authorships[3].raw_author_name	Paquete, Luís
authorships[3].is_corresponding	False
has_content.pdf	False
has_content.grobid_xml	False
is_paratext	False
open_access.is_oa	True
open_access.oa_url	https://arxiv.org/pdf/2407.11533
open_access.oa_status	green
open_access.any_repository_has_fulltext	False
created_date	2024-10-26T00:00:00
display_name	Transforming the Challenge of Constructing Low-Discrepancy Point Sets into a Permutation Selection Problem
has_fulltext	False
is_retracted	False
updated_date	2025-11-06T06:51:31.235846
primary_topic.id	https://openalex.org/T12404
primary_topic.field.id	https://openalex.org/fields/26
primary_topic.field.display_name	Mathematics
primary_topic.score	0.9526000022888184
primary_topic.domain.id	https://openalex.org/domains/3
primary_topic.domain.display_name	Physical Sciences
primary_topic.subfield.id	https://openalex.org/subfields/2612
primary_topic.subfield.display_name	Numerical Analysis
primary_topic.display_name	Mathematical Approximation and Integration
related_works	https://openalex.org/W4391375266, https://openalex.org/W1979597421, https://openalex.org/W2007980826, https://openalex.org/W2061531152, https://openalex.org/W3002753104, https://openalex.org/W2077600819, https://openalex.org/W2142036596, https://openalex.org/W2072657027, https://openalex.org/W2600246793, https://openalex.org/W4238204885
cited_by_count	0
locations_count	2
best_oa_location.id	pmh:oai:arXiv.org:2407.11533
best_oa_location.is_oa	True
best_oa_location.source.id	https://openalex.org/S4306400194
best_oa_location.source.issn
best_oa_location.source.type	repository
best_oa_location.source.is_oa	True
best_oa_location.source.issn_l
best_oa_location.source.is_core	False
best_oa_location.source.is_in_doaj	False
best_oa_location.source.display_name	arXiv (Cornell University)
best_oa_location.source.host_organization	https://openalex.org/I205783295
best_oa_location.source.host_organization_name	Cornell University
best_oa_location.source.host_organization_lineage	https://openalex.org/I205783295
best_oa_location.license
best_oa_location.pdf_url	https://arxiv.org/pdf/2407.11533
best_oa_location.version	submittedVersion
best_oa_location.raw_type	text
best_oa_location.license_id
best_oa_location.is_accepted	False
best_oa_location.is_published	False
best_oa_location.raw_source_name
best_oa_location.landing_page_url	http://arxiv.org/abs/2407.11533
primary_location.id	pmh:oai:arXiv.org:2407.11533
primary_location.is_oa	True
primary_location.source.id	https://openalex.org/S4306400194
primary_location.source.issn
primary_location.source.type	repository
primary_location.source.is_oa	True
primary_location.source.issn_l
primary_location.source.is_core	False
primary_location.source.is_in_doaj	False
primary_location.source.display_name	arXiv (Cornell University)
primary_location.source.host_organization	https://openalex.org/I205783295
primary_location.source.host_organization_name	Cornell University
primary_location.source.host_organization_lineage	https://openalex.org/I205783295
primary_location.license
primary_location.pdf_url	https://arxiv.org/pdf/2407.11533
primary_location.version	submittedVersion
primary_location.raw_type	text
primary_location.license_id
primary_location.is_accepted	False
primary_location.is_published	False
primary_location.raw_source_name
primary_location.landing_page_url	http://arxiv.org/abs/2407.11533
publication_date	2024-07-16
publication_year	2024
referenced_works_count	0
abstract_inverted_index.2	126
abstract_inverted_index.3	128
abstract_inverted_index.a	9, 27, 57, 98
abstract_inverted_index.50	134
abstract_inverted_index.an	114
abstract_inverted_index.as	8, 113, 164
abstract_inverted_index.be	55
abstract_inverted_index.by	15
abstract_inverted_index.in	18, 23, 47, 56, 73, 81, 124
abstract_inverted_index.is	35
abstract_inverted_index.it	34
abstract_inverted_index.of	29, 42, 76, 83, 105, 152
abstract_inverted_index.on	31, 92
abstract_inverted_index.to	11, 70, 101, 121, 131, 147
abstract_inverted_index.up	130, 146
abstract_inverted_index.we	96, 137
abstract_inverted_index.25%	148
abstract_inverted_index.400	132
abstract_inverted_index.50%	158
abstract_inverted_index.Low	0
abstract_inverted_index.and	64, 127, 133, 156
abstract_inverted_index.are	145
abstract_inverted_index.can	45, 53
abstract_inverted_index.for	21, 129
abstract_inverted_index.go;	46
abstract_inverted_index.how	38, 50
abstract_inverted_index.led	69
abstract_inverted_index.low	39
abstract_inverted_index.the	32, 40, 74, 93, 109, 153, 165
abstract_inverted_index.way	100
abstract_inverted_index.been	5
abstract_inverted_index.have	4, 68
abstract_inverted_index.much	84
abstract_inverted_index.ones	17
abstract_inverted_index.same	110
abstract_inverted_index.set.	117, 167
abstract_inverted_index.sets	3, 44, 123, 140
abstract_inverted_index.star	143
abstract_inverted_index.such	163
abstract_inverted_index.than	88, 150, 160
abstract_inverted_index.that	107
abstract_inverted_index.this	119
abstract_inverted_index.tool	10
abstract_inverted_index.used	7
abstract_inverted_index.given	58
abstract_inverted_index.input	116
abstract_inverted_index.lower	85
abstract_inverted_index.order	112
abstract_inverted_index.other	48
abstract_inverted_index.point	2, 43, 78, 122, 139
abstract_inverted_index.sets,	79, 155
abstract_inverted_index.still	36
abstract_inverted_index.those	151
abstract_inverted_index.using	62
abstract_inverted_index.whose	141
abstract_inverted_index.Recent	60
abstract_inverted_index.around	157
abstract_inverted_index.better	159
abstract_inverted_index.follow	108
abstract_inverted_index.known.	90
abstract_inverted_index.obtain	102, 138
abstract_inverted_index.points	54, 106
abstract_inverted_index.simple	99
abstract_inverted_index.space.	59
abstract_inverted_index.topic,	33
abstract_inverted_index.values	87
abstract_inverted_index.widely	6
abstract_inverted_index.words,	49
abstract_inverted_index.century	28
abstract_inverted_index.example	22
abstract_inverted_index.machine	65
abstract_inverted_index.objects	14
abstract_inverted_index.optimal	94
abstract_inverted_index.points,	135
abstract_inverted_index.present	97
abstract_inverted_index.smaller	149
abstract_inverted_index.unclear	37
abstract_inverted_index.Applying	118
abstract_inverted_index.Building	91
abstract_inverted_index.approach	120
abstract_inverted_index.discrete	16
abstract_inverted_index.insights	61
abstract_inverted_index.learning	66
abstract_inverted_index.relative	111
abstract_inverted_index.research	30
abstract_inverted_index.Fibonacci	166
abstract_inverted_index.Following	26
abstract_inverted_index.classical	161
abstract_inverted_index.numerical	19, 24
abstract_inverted_index.placement	104
abstract_inverted_index.regularly	51
abstract_inverted_index.resulting	80
abstract_inverted_index.continuous	13
abstract_inverted_index.dimensions	125
abstract_inverted_index.previously	89
abstract_inverted_index.processes,	20
abstract_inverted_index.techniques	67
abstract_inverted_index.(arbitrary)	115
abstract_inverted_index.approximate	12
abstract_inverted_index.discrepancy	1, 41, 86
abstract_inverted_index.distributed	52
abstract_inverted_index.substantial	71
abstract_inverted_index.$L_{\infty}$	142
abstract_inverted_index.construction	75
abstract_inverted_index.current-best	154
abstract_inverted_index.improvements	72
abstract_inverted_index.integration.	25
abstract_inverted_index.optimization	63
abstract_inverted_index.constructions	162
abstract_inverted_index.discrepancies	144
abstract_inverted_index.respectively,	136
abstract_inverted_index.configurations	82
abstract_inverted_index.constructions,	95
abstract_inverted_index.low-discrepancy	77
abstract_inverted_index.$L_{\infty}$-optimized	103
cited_by_percentile_year
countries_distinct_count	0
institutions_distinct_count	4
citation_normalized_percentile