Circle Packing
en.wikipedia.org
Circle Packing
1–10 of 32 posts
Re: Circle Packing
#2Re: Circle Packing
#3Circle packing is one of my favorite applications to display hierarchical data where one dimension defines the radius, like the file size. Other dimensions may alter color or line width.
Circle packing is available as an example in D3, highly recommended.
Re: Circle Packing
#4I wrote about sphere packings and their relation to lattices here: https://nullset.xyz/2016/12/11/lattices-and-sphere-packings/
Re: Circle Packing
#5I always see circle packing using ideal circles(or other shapes) inside another ideal shape. It's my understanding that packing arbitrary shapes inside other shape(even an ideal one) or the reverse, packing ideal shapes inside an arbitrary shape, is NP hard. My limited research and experimentation proves this out but my work has been in the context of getting things done and not research or algorithm design.
Double packing, packing shapes inside shapes inside shapes is O(N^k) as far as I can tell.
Re: Circle Packing
#6Sphere packings are quite a deep and fascinating area of pure mathemaics. It has close relations to coding theory, lattice theory, number theory, modular forms.
John Conway [1] (who recently passed away due to COVID) wrote a famous book about it: Sphere Packings, Lattices and Groups -- which summarizes the subject concisely.
A recent (2017) break through, was the proof that the Leech Lattice [2] yields the optimal sphere packing in dimension 24 [3]. The error correcting code constructed from this lattice is the Binary Golay Error Correcting Code [4]. It is able to correct 3 bits for every 24 bits, and maximally efficient in doing so. It was used to communicate with the Voyager probes.
[1] https://en.wikipedia.org/wiki/John_Horton_Conway [2] https://en.wikipedia.org/wiki/Leech_lattice [3] https://arxiv.org/pdf/1603.06518.pdf [4] https://en.wikipedia.org/wiki/Binary_Golay_code
Re: Circle Packing
#7Sphere packings are quite a deep and fascinating area of pure mathemaics. It has close relations to coding theory, lattice theory, number theory, modular forms. John Conway [1] (who recently passed away due to COVID) wrote a famous book about it: Sphere Packings, Lattices and Groups -- which summarizes the subject concisely. A recent (2017) break through, was the proof that the Leech Lattice [2] yields the optimal sp…
I didn't realize he died from COVID complications. That just makes it all the worse.
Re: Circle Packing
#8I was surprised to see the Wikipedia page didn’t mention any best-effort algorithms but I guess they can’t list everything.
I like the natural noise you get from Poisson Disc Sampling [1]
Re: Circle Packing
#9I was surprised to see the Wikipedia page didn’t mention any best-effort algorithms but I guess they can’t list everything. I like the natural noise you get from Poisson Disc Sampling [1] [1] https://bl.ocks.org/mbostock/dbb02448b0f93e4c82c3
Poisson disc sampling is a brute force technique and isn't an analytic method for packing. Any sample pattern can be relaxed if you are finding neighbor points and using multiple iterations. Poisson sampling is just trying and rejecting many samples based on their neighbors' distances, there aren't any deep principles being used.
It is a lot like a bubble sort in that it is O(n^2) and is useful in practice on tiny sets and as a benchmark.
(Also that link is very cool, but it looks closer to n-rooks / latin hypercube sampling in that it used a grid, which means it won't work in higher dimensions)
Re: Circle Packing
#10Sphere packings are quite a deep and fascinating area of pure mathemaics. It has close relations to coding theory, lattice theory, number theory, modular forms. John Conway [1] (who recently passed away due to COVID) wrote a famous book about it: Sphere Packings, Lattices and Groups -- which summarizes the subject concisely. A recent (2017) break through, was the proof that the Leech Lattice [2] yields the optimal sp…
Sphere packing was my 3rd year internship project (summer of 2013), so happy to see what is quite the fascinating topic mentioned on HN! I'm a bit sad I don't have a lot to show for it, other than an old undocumented GitHub repo[1]...
Glad to hear there were breakthroughs in the field, thanks for the heap of links for me to delve into. :)