{"id":1272,"date":"2021-12-02T11:46:04","date_gmt":"2021-12-02T17:46:04","guid":{"rendered":"https:\/\/sites.imsa.edu\/hadron\/?p=1272"},"modified":"2021-12-02T11:47:46","modified_gmt":"2021-12-02T17:47:46","slug":"debunking-flatland-space-filling-curves","status":"publish","type":"post","link":"https:\/\/sites.imsa.edu\/hadron\/2021\/12\/02\/debunking-flatland-space-filling-curves\/","title":{"rendered":"Debunking Flatland: Space Filling Curves"},"content":{"rendered":"

Written by: Gautham Anne<\/span><\/p>\n

 <\/p>\n

In 1877, George Cantor discovered that the number of points in a 2-dimensional plane is the same as the number of points in a 1-dimensional line. This is tremendously counterintuitive since a plane can have an infinite number of lines placed \u2018side by side,\u2019 and stating that one line can pass through every other line seems absurd. Even Cantor himself wrote, \u201cI see it, but I don\u2019t believe it.\u201d This revelation is astounding and has many practical applications. This type of thinking revolutionized the way mathematicians have thought about dimensions and infinitesimal mathematical objects and had transformed the realm of set theory forever.<\/span><\/p>\n

 <\/p>\n

Rigorous Definitions and More History<\/b><\/p>\n

Cantor defined a one to one correspondence between the perimeter of a square and the points that lie within it. This means that every point that lies within the square can be mapped, or associated with, a point on the perimeter. This is a common methodology to prove that the cardinality, or the number of elements in a set, of two separate infinite sets are equal. If it can be shown that each element of one infinite set can be associated with exactly one element in another, then the number of elements of both sets must be the same. It is common to call this a bijection between two sets. Thus, sets with a bijective relationship have the same cardinality.<\/span><\/p>\n

Soon after Cantor\u2019s discovery, a new question arose: \u201cIs there a continuous mapping between a line and a 2 dimensional plane?\u201d In other words, is it possible to trace a line that goes through every point in a plane without lifting the pencil once? After nearly a decade, many different types of such curves were discovered.<\/span><\/p>\n

 <\/p>\n

Filling Up a Plane with a Curve<\/b><\/p>\n

There are multiple ways to solve the problem regarding the continuous mapping. For example, two such \u2018go-to\u2019 solutions are depicted below, commonly referred to as the \u2018lawn mower solutions.\u2019\u00a0<\/span><\/p>\n

 <\/p>\n

Figure 1<\/span><\/p>\n

\"\"<\/p>\n

Lawn Mower Solutions<\/span><\/p>\n

Source: <\/span>American Scientist<\/span><\/i><\/p>\n

 <\/p>\n

In 1890, the first successful solution was described by Giuseppe Peano, who was an Italian mathematician also known for his famous Peano Axioms, the set of postulates that all of number theory is based upon. However, Peano did not describe the methodology of creating such a curve, but rather found a mathematical function that defines coordinates <\/span>x<\/span><\/i> and <\/span>y<\/span><\/i> given a point <\/span>t<\/span><\/i> on the line. David Hilbert, often regarded as one of the most influential mathematicians of the 20th century, devised a simple version of Peano\u2019s curve through a recursive, geometrical interpretation. Figure 2 shows the family of <\/span>Hilbert Curves<\/span><\/i>, through which each iteration, the curve gets closer and closer to reaching a completely filled square. In other words, the limit of the number of points that the curve does not pass through goes to 0 as the iterations increase to infinity.<\/span><\/p>\n

 <\/p>\n

Figure 2<\/span><\/p>\n

\"\"<\/p>\n

First 6 iterations of the Hilbert Curve<\/span><\/p>\n

Source: <\/span>McGill University<\/span><\/i><\/p>\n

Other Space Filling Curves<\/b><\/p>\n

Although the Hilbert curve is one such mathematical procedure to impose a linear order of points in a 2 dimensional space (linearization), it is not the only one. Mathematicians have discovered numerous different curves which accomplish the same thing, yet have different structures. These curves can be split into recursive space filling curves (RSFC) and non-recursive space filling curves (NRSFC).<\/span><\/p>\n

Looking at Figure 2, one can determine that each iteration of Hilbert Curves are fractals. That is, the previous iteration is repeated multiple times and joined together to form the next. This is precisely what an RSFC is. Each quadrant of a space RFSC is equivalent to the previous iteration of the curve. NRSFC do not recurse or possess fractal traits. Figure 4 shows some of the most common space filling curves<\/span>.<\/span><\/p>\n

 <\/p>\n

Figure 4<\/span><\/p>\n

\"\"<\/p>\n

Different types of space filling curves<\/span><\/p>\n

Source: <\/span>Purdue University, University of Minnesota<\/span><\/i><\/p>\n

 <\/p>\n

Mathematicians have also generalized space filling curves to any dimension; any multidimensional space can be mapped onto a linear space, or a line. Figure 5 shows some of the common mappings of the 3 dimensional space onto a linear space at an nth iteration.<\/span><\/p>\n

Figure 5<\/span>
\n\"\"<\/p>\n

Different types of 3-dimensional space filling curve<\/span><\/p>\n

Source: <\/span>Purdue University, University of Minnesota<\/span><\/i><\/p>\n

 <\/p>\n

Locality<\/b><\/p>\n

One interesting property of some space filling curves is that they preserve locality, which is when a point on the n dimensional space when iterated by a space filling curve does not \u2018move\u2019 in the space. The point\u2019s position is as close to being conserved as possible throughout the iterations. The classic Hilbert Curve has remarkable locality preserving properties, and Figure 6 demonstrates this in the 2 dimensional space.<\/span><\/p>\n

 <\/p>\n

Figure 6<\/span><\/p>\n

\"\"<\/p>\n

The location of the white point is very nearly preserved throughout the iteration process. This implies that the Hilbert Curve preserves locality very well.<\/span><\/p>\n

Source: <\/span>3Blue1Brown<\/span><\/i><\/p>\n

 <\/p>\n

Applications<\/b><\/p>\n

Interestingly, many of the properties that space filling curves possess make them very useful for practical applications. One remarkable application of space filling curves was when a couple colleagues at the Georgia Institute of Technology aimed to find efficient routes to deliver meals to elderly clients scattered across Atlanta. This, in principle, is quite similar to the traveling salesman problem, which is notorious in computer science fields. Because some space filling curves preserve locality, a mapping across the streets of Atlanta could be approximated with such curves, providing a close to optimal path, even better than the one that can be predicted from the Bartholdi algorithm.\u00a0<\/span><\/p>\n

Another application of space-filling curves is in the realm of linear algebra; specifically, the multiplication of matrices. For a computer to store or read rows and columns of matrices, some values may need to be accessed from the memory multiple times. In 2006, it was found that clustering the data of matrices with space filling curves can reduce memory traffic. Clustering is the process of mapping each cell in an matrix (or in general, an array) to a space filling curve, so the computer only has to store data on a single dimension, similar to how a plane can be mapped to a 1 dimensional line.<\/span><\/p>\n

Laser printers have also enlisted the assistance of space-filling curves for a process known as half-toning. Half-toning allows laser printers to produce tones of gray. Traditional half-toning uses an array of pixels that vary in size and darkness to produce grays. However, storing the pixels along the path of a Hilbert or Peano curve can help create smoother gradients of gray.<\/span><\/p>\n

Finally, image processing heavily relies on space filling curves. Originally, each pixel in an image was stored in an array, which required a lot of memory. Later on, it was proposed that each pixel could be mapped onto a Hilbert curve, which would allow every pixel to be represented as a function, rather than an array, thus saving a lot of space. Another advantage of the use of space-filling curves in image processing is that if the resolution of an image changes, the same curve, but a different iteration, can be used since it preserves locality.<\/span><\/p>\n

 <\/p>\n

Conclusion<\/b><\/p>\n

From the time of Descartes, it was thought that every point in a <\/span>d<\/span><\/i>-dimensional space must be represented in <\/span>d<\/span><\/i> coordinates. For example, in the xy plane, we use two coordinates. However, space-filling curves propose a radically different way of representing multidimensional spaces. A single number can represent every single point, whether that point be in a line, plane, 3 dimensional solid, or even the 11-dimensional spaces that high energy physics involves.<\/span><\/p>\n

In the novel <\/span>Flatland<\/span><\/i>, by Edwin Abbott, there exist creatures constrained to a one and two-dimensional world that yearn to break free into higher dimensional spaces. In fact, they might be able to do so, by simply being a space-filling curve.<\/span><\/p>\n

 <\/p>\n

References and Sources<\/span><\/p>\n

Crinkly Curves. (2017). Retrieved 19 November 2021, from <\/span>https:\/\/www.americanscientist.org\/article\/crinkly-curves<\/span><\/a><\/p>\n

Hilbert Space Filling Curves. (2021). Retrieved 19 November 2021, from <\/span>http:\/\/www.bic.mni.mcgill.ca\/~mallar\/CS-644B\/hilbert.html<\/span><\/a><\/p>\n

 <\/p>\n

Mokbel, M., & Aref, W. (2008). Space-Filling Curves. Encyclopedia Of GIS, 1068-1072. doi: 10.1007\/978-0-387-35973-1_1233<\/span><\/p>\n

Space-filling Curve. (2021). Retrieved 19 November 2021, from <\/span>https:\/\/people.math.osu.edu\/fiedorowicz.1\/math655\/Peano.html<\/span><\/a><\/p>\n

(2021). Retrieved 19 November 2021, from <\/span>https:\/\/arxiv.org\/pdf\/1801.07399.pdf<\/span><\/a><\/p>\n

 <\/p>\n","protected":false},"excerpt":{"rendered":"

Written by: Gautham Anne   In 1877, George Cantor discovered that the number of points in a 2-dimensional plane is the same as the number of points in a 1-dimensional line. This is tremendously counterintuitive since a plane can have an infinite number of lines<\/p>\n","protected":false},"author":704,"featured_media":1336,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"ngg_post_thumbnail":0,"footnotes":""},"categories":[11],"tags":[],"class_list":["post-1272","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-math"],"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/sites.imsa.edu\/hadron\/wp-json\/wp\/v2\/posts\/1272","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/sites.imsa.edu\/hadron\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/sites.imsa.edu\/hadron\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/sites.imsa.edu\/hadron\/wp-json\/wp\/v2\/users\/704"}],"replies":[{"embeddable":true,"href":"https:\/\/sites.imsa.edu\/hadron\/wp-json\/wp\/v2\/comments?post=1272"}],"version-history":[{"count":2,"href":"https:\/\/sites.imsa.edu\/hadron\/wp-json\/wp\/v2\/posts\/1272\/revisions"}],"predecessor-version":[{"id":1337,"href":"https:\/\/sites.imsa.edu\/hadron\/wp-json\/wp\/v2\/posts\/1272\/revisions\/1337"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/sites.imsa.edu\/hadron\/wp-json\/wp\/v2\/media\/1336"}],"wp:attachment":[{"href":"https:\/\/sites.imsa.edu\/hadron\/wp-json\/wp\/v2\/media?parent=1272"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/sites.imsa.edu\/hadron\/wp-json\/wp\/v2\/categories?post=1272"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/sites.imsa.edu\/hadron\/wp-json\/wp\/v2\/tags?post=1272"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}