Delone set

<h2 id="definitions">Definitions</h2>
If (M, d) is a metric space, and X is a subset of M, then the packing radius, r, of X is half of the smallest distance between distinct members of X. <a href="/facts/Ball_(mathematics)/f9vpMVMp">Open balls</a> of radius r centered at the points of X will all be disjoint from each other. The covering radius, R, of X is the smallest distance such that every point of M is within distance R of at least one point in X; that is, R is the smallest radius such that <a href="/facts/Ball_(mathematics)/f9vpMVMp">closed balls</a> of that radius centered at the points of X have all of M as their union. 
An ε-packing is a set X of packing radius r ≥ ⁠ε/2⁠ (equivalently, minimum distance ≥ ε), an ε-covering is a set X of covering radius R ≤ ε, and an ε-net is a set that is both an ε-packing and an ε-covering (⁠ε/2⁠ ≤ r ≤ R ≤ ε). 
A set is uniformly discrete if it has a nonzero packing radius (0 < r), and relatively dense if it has a finite covering radius (R < ∞). 
A Delone set is a set that is both uniformly discrete and relatively dense (0 < r ≤ R < ∞). Thus every ε-net is Delone, but not vice versa.<a class="footnote-ref" id="fnref:1" href="#fn:1">1</a><a class="footnote-ref" id="fnref:2" href="#fn:2">2</a>

<h2 id="construction-of--nets">Construction of ε-nets</h2>
As the most restrictive of the definitions above, ε-nets are at least as difficult to construct as ε-packings, ε-coverings, and Delone sets. However, whenever the points of M have a <a href="/facts/Well-ordering/GrWEBWlW">well-ordering</a>, <a href="/facts/Transfinite_induction/XlolgTDl">transfinite induction</a> shows that it is possible to construct an ε-net N, by including in N every point for which the infimum of distances to the set of earlier points in the ordering is at least ε. For finite sets of points in a Euclidean space of bounded dimension, each point may be tested in constant time by mapping it to a grid of cells of diameter ε, and using a <a href="/facts/Hash_table/Ht4ptDPF">hash table</a> to test which nearby cells already contain points of N; thus, in this case, an ε-net can be constructed in <a href="/facts/Linear_time/77T62gmf">linear time</a>.<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a><a class="footnote-ref" id="fnref:4" href="#fn:4">4</a>
For more general finite or <a href="/facts/Compact_space/d0cgXJH7">compact</a> metric spaces, an alternative algorithm of <a href="/facts/Teofilo_F._Gonzalez/kQUG6d9T">Teo Gonzalez</a> based on the <a href="/facts/Farthest-first_traversal/UBE7kErV">farthest-first traversal</a> can be used to construct a finite ε-net. This algorithm initializes the net N to be empty, and then repeatedly adds to N the farthest point in M from N, breaking ties arbitrarily and stopping when all points of M are within distance  ε of N.<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a> In <a href="/facts/Doubling_space/8y92hNdN">spaces of bounded doubling dimension</a>, Gonzalez' algorithm can be implemented in O(n log n) time for point sets with a polynomial ratio between their farthest and closest distances, and approximated in the same time bound for arbitrary point sets.<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a>

<h2 id="applications">Applications</h2>
<h3>Coding theory</h3>
Main article: <a href="/facts/Hamming_bound/3P8HVgGF">Hamming bound § Covering radius and packing radius</a>
In the theory of <a href="/facts/Error-correcting_code/cLUTUJrA">error-correcting codes</a>, the metric space containing a <a href="/facts/Block_code/QVuqpGga">block code</a> C consists of strings of a fixed length, say n, taken over an alphabet of size q (can be thought of as <a href="/facts/Coordinate_vector/TEcLqS40">vectors</a>), with the <a href="/facts/Hamming_metric/MgdtbYPo">Hamming metric</a>. This space is denoted by ⁠
 
 
 
 
 
 
 A
 
 
 
 q
 
 
 n
 
 
 .
 
 
 {\displaystyle {\mathcal {A}}_{q}^{n}.}
 
⁠ The covering radius and packing radius of this metric space are related to the code's ability to correct errors. An example is provided by the <a href="/facts/Berlekamp_switching_game/ttl4mVb0">Berlekamp switching game</a>.

<h3>Approximation algorithms</h3>
Har-Peled & Raichel (2013) describe an algorithmic paradigm that they call "net and prune" for designing <a href="/facts/Approximation_algorithm/BWlf7M32">approximation algorithms</a> for certain types of geometric optimization problems defined on sets of points in <a href="/facts/Euclidean_space/R2UbzmzM">Euclidean spaces</a>. An algorithm of this type works by performing the following steps:

<ol><li>Choose a random point p from the point set, find its nearest neighbor q, and set ε to the distance between p and q.</li>
<li>Test whether ε is (approximately) bigger than or smaller than the optimal solution value (using a technique specific to the particular optimization problem being solved)
<ul><li>If it is bigger, remove from the input the points whose closest neighbor is farther than ε</li>
<li>If it is smaller, construct an ε-net N, and remove from the input the points that are not in N.</li></ul></li></ol>
In both cases, the expected number of remaining points decreases by a constant factor, so the time is dominated by the testing step. As they show, this paradigm can be used to construct fast approximation algorithms for <a href="/facts/K-center/Uvt3a9Xw">k-center</a> clustering, finding a pair of points with median distance, and several related problems.
A hierarchical system of nets, called a net-tree, may be used in <a href="/facts/Doubling_space/8y92hNdN">spaces of bounded doubling dimension</a> to construct <a href="/facts/Well-separated_pair_decomposition/lxJXArm9">well-separated pair decompositions</a>, <a href="/facts/Geometric_spanner/yblwj8bF">geometric spanners</a>, and approximate <a href="/facts/Nearest_neighbor_search/R6QTyAph">nearest neighbors</a>.<a class="footnote-ref" id="fnref:7" href="#fn:7">7</a><a class="footnote-ref" id="fnref:8" href="#fn:8">8</a>

<h3>Crystallography</h3>
For points in <a href="/facts/Euclidean_space/R2UbzmzM">Euclidean space</a>, a set X is a <a href="/facts/Meyer_set/NAj7VFHQ">Meyer set</a> if it is relatively dense and its <a href="/facts/Minkowski_difference/dEQfoJ1A">difference set</a> X − X is uniformly discrete. Equivalently, X is a Meyer set if both X and X − X are Delone sets. Meyer sets are named after <a href="/facts/Yves_Meyer/Vg24hnxz">Yves Meyer</a>, who introduced them (with a different but equivalent definition based on <a href="/facts/Harmonic_analysis/CyG5bIPb">harmonic analysis</a>) as a mathematical model for <a href="/facts/Quasicrystal/evHcQeCp">quasicrystals</a>. They include the point sets of <a href="/facts/Lattice_(group)/2ls9Iv9N">lattices</a>, <a href="/facts/Penrose_tiling/usLcMvNN">Penrose tilings</a>, and the <a href="/facts/Minkowski_sum/dEQfoJ1A">Minkowski sums</a> of these sets with finite sets.<a class="footnote-ref" id="fnref:9" href="#fn:9">9</a>
The <a href="/facts/Voronoi_cell/AhQY5LD8">Voronoi cells</a> of symmetric Delone sets form <a href="/facts/Space-filling_polyhedron/jPu5CD9k">space-filling polyhedra</a> called <a href="/facts/Plesiohedron/Lytb02ys">plesiohedra</a>.<a class="footnote-ref" id="fnref:10" href="#fn:10">10</a>

<h2 id="external-links">External links</h2>
<ul><li><a href="https://web.archive.org/web/20160304095756/http://tilings.math.uni-bielefeld.de/glossary/delone_set">Delone set</a> – Tilings Encyclopedia</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Clarkson, Kenneth L. (2006), "Building triangulations using ε-nets", STOC'06: Proceedings of the 38th Annual ACM Symposium on Theory of Computing, New York: ACM, pp. 326–335, doi:10.1145/1132516.1132564, ISBN 1595931341, MR 2277158, S2CID 14132888. <a href="1595931341" target="_blank">1595931341</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Some sources use " ε-net" for what is here called an " ε-covering"; see, e.g. Sutherland, W. A. (1975), Introduction to metric and topological spaces, Oxford University Press, p. 110, ISBN 0-19-853161-3, Zbl 0304.54002. <a href="0-19-853161-3" target="_blank">0-19-853161-3</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Har-Peled, S. (2004), "Clustering motion", Discrete and Computational Geometry, 31 (4): 545–565, doi:10.1007/s00454-004-2822-7, MR 2053498. <a href="/wiki/Sariel_Har-Peled" target="_blank">/wiki/Sariel_Har-Peled</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Har-Peled, S.; Raichel, B. (2013), "Net and prune: A linear time algorithm for Euclidean distance problems", STOC'13: Proceedings of the 45th Annual ACM Symposium on Theory of Computing, pp. 605–614, arXiv:1409.7425. <a href="/wiki/Symposium_on_Theory_of_Computing" target="_blank">/wiki/Symposium_on_Theory_of_Computing</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Gonzalez, T. F. (1985), "Clustering to minimize the maximum intercluster distance", Theoretical Computer Science, 38 (2–3): 293–306, doi:10.1016/0304-3975(85)90224-5, MR 0807927. <a href="/wiki/Theoretical_Computer_Science_(journal)" target="_blank">/wiki/Theoretical_Computer_Science_(journal)</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Har-Peled, S.; Mendel, M. (2006), "Fast construction of nets in low-dimensional metrics, and their applications", SIAM Journal on Computing, 35 (5): 1148–1184, arXiv:cs/0409057, doi:10.1137/S0097539704446281, MR 2217141, S2CID 37346335. <a href="/wiki/SIAM_Journal_on_Computing" target="_blank">/wiki/SIAM_Journal_on_Computing</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Har-Peled, S.; Mendel, M. (2006), "Fast construction of nets in low-dimensional metrics, and their applications", SIAM Journal on Computing, 35 (5): 1148–1184, arXiv:cs/0409057, doi:10.1137/S0097539704446281, MR 2217141, S2CID 37346335. <a href="/wiki/SIAM_Journal_on_Computing" target="_blank">/wiki/SIAM_Journal_on_Computing</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">Krauthgamer, Robert; Lee, James R. (2004), "Navigating nets: simple algorithms for proximity search", Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '04), Philadelphia, PA, USA: Society for Industrial and Applied Mathematics, pp. 798–807, ISBN 0-89871-558-X. <a href="0-89871-558-X" target="_blank">0-89871-558-X</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">Moody, Robert V. (1997), "Meyer sets and their duals", The Mathematics of Long-Range Aperiodic Order (Waterloo, ON, 1995), NATO Advanced Science Institutes Series C: Mathematical and Physical Sciences, vol. 489, Dordrecht: Kluwer Academic Publishers, pp. 403–441, MR 1460032, archived from the original on 2016-03-03, retrieved 2013-07-10. <a href="/wiki/Robert_Moody" target="_blank">/wiki/Robert_Moody</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
<li id="fn:10">Grünbaum, Branko; Shephard, G. C. (1980), "Tilings with congruent tiles", Bulletin of the American Mathematical Society, New Series, 3 (3): 951–973, doi:10.1090/S0273-0979-1980-14827-2, MR 0585178. <a href="/wiki/Branko_Gr%C3%BCnbaum" target="_blank">/wiki/Branko_Gr%C3%BCnbaum</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></li>
</ol>

Delone set open-in-new

Delone set