<jupyter_start><jupyter_text>SummaryWe are given :    *  a positive integer $n$ which is the number of dimension of the space. *  a positive integer $k$ which is the total number of discrete points we need to place inside that space.    *  each continuous point $x$ queried in that space that follows a probability density function $PDF$.And we are asked for:   *  the $k$ discrete points that are placed in a way that minimizes the average distance (or mean error $ME$) from those continuous points $x$ . Proposed approachWe propose a method that:    *   is an almost optimal solution that provides a decent decrease of the $ME$.*   works for almost any number $k$ of points.*   works for almost any number $n$ of dimensions.*   adapts very fast (close to $\log k$ rate).*   is always better than the $ME$ provided by a uniform discretization, even before it is adapted.*   is "model" free. The $PDF$ of the appearance of $x$'s don't have to be known. How it worksThe core idea behind this method is the $2^n$-trees. Like quadtrees and octrees with $n$ equal to 2 and 3 respectively, n-trees have any positive integer number $n$ as spatial subdivision factor, or also known as branching factor. $n$ describes the dimensions of the space that these trees spread. The $2^n$ child branches of each parent node, expand to all the basic directions in order to fill up all the space as uniform as possible. Each node is a point in space that covers a specified region. This region is the corresponding fraction of its parent's region. In other words, the parent splits the region that is assigned to it to $2^n$ equal sub-regions with volume $\frac{1}{2^n}$ times smaller than their parent's. The sub-regions that are produced are n-dimensional cubes too and have no overlapping except their touching surfaces. Of coursethey fully overlap with their parent because they are actually its sub-set. As the height of the tree is growing, the nodes that are created have smaller and smaller volumes. Each point is located in the middle of the cube so there will be no way for two or more points to be in the same location. So a tree with $k$ nodes will have $k$ different points inside the given space.We assign to the root node the whole space we want to use, in our case the unit cube between the points $[0, 0, ..., 0]$ and $[1, 1, ..., 1]$. For example, lets take $n=2$. Root, the node in level zero, will have the point $[0.5,0.5]$ and determined by the vertices $[0,0],[1,1]$. Its $2^n=4$ branches, will split this area in 4 equal 2d-cubes (aka rectangles) with vertices and points:   *   cube 1 -> vertices $[0,0],[0.5,0.5]$ , point $[0.25,0.25]$  *   cube 2 -> vertices $[0.5,0],[1,0.5]$ , point $[0.75,0.25]$  *   cube 3 -> vertices $[0,0.5],[0.5,1]$ , point $[0.25,0.75]$  *   cube 4 -> vertices $[0.5,0.5],[1,1]$ , point $[0.75,0.75]$     So now we have 5 points to fill up this space. Those 4 branches can be extended to create 16 new sub-branches (4 more branches each) adding to a total of 21 points.<jupyter_code>tree = Tree(2, 21)
tree.plot()

points = tree.get_points()

plt.figure()
for p in points:
    plt.plot(p[0], p[1], 'bo', label='Points')
plt.plot([0, 0], [0, 1], 'g--', label='Space')
plt.plot([0, 1], [0, 0], 'g--')
plt.plot([1, 1], [0, 1], 'g--')
plt.plot([1, 0], [1, 1], 'g--')

plt.xticks(np.linspace(0, 1, 9))
plt.yticks(np.linspace(0, 1, 9))
plt.title('Points spread into space')
plt.grid(True)
plt.legend()
plt.show()<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.11408815903197926, 'fraction_numerical': 0.03226735811005474, 'mean_word_length': 3.9458689458689458, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 9, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '1843', 'license': 'MIT', 'n_tokens_mistral': 1103, 'n_tokens_neox': 1023, 'n_words': 538, 'path': 'notebooks/my_approach.ipynb', 'repo_name': 'jimkon/adaptive-discretization', 'size': '3471'}