9 ms·
Circle Packing
- hyperpower 6y agoI wrote about sphere packings and their relation to lattices here: https://nullset.xyz/2016/12/11/lattices-and-sphere-packings/ https://nullset.xyz/2016/12/11/lattices-and-sphere-packings/
- iamthepieman 6y agoI 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.
- dan-robertson 6y agoSee also https://www2.stetson.edu/~efriedma/maxmin/ https://www2.stetson.edu/~efriedma/maxmin/
- jhoechtl 6y agoCircle 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. https://observablehq.com/@d3/zoomable-circle-packing https://observablehq.com/@d3/zoomable-circle-packing
- anamexis 6y agoI don't think defining the radius with data makes for good charts, because we tend to perceive the area as size, not radius, and area of course scales with the square of the radius. So if you have 2 circles depicting files, and one of the files is 3x the size of the other, its circle will have 9x the area and appear 9x larger.
- tomlagier 6y agoI made a tool that does this with Chrome memory profiles https://heapviz.com/ https://heapviz.com/ Also ported d3s circle packing algorithm to C++ for compilation to WASM https://github.com/tomlagier/circle-pack https://github.com/tomlagier/circle-pack Definitely love how that visualization turns out!
- heinrichhartman 6y agoSphere 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 https://en.wikipedia.org/wiki/John_Horton_Conway [2] https://en.wikipedia.org/wiki/Leech_lattice https://en.wikipedia.org/wiki/Leech_lattice [3] https://arxiv.org/pdf/1603.06518.pdf https://arxiv.org/pdf/1603.06518.pdf [4] https://en.wikipedia.org/wiki/Binary_Golay_code https://en.wikipedia.org/wiki/Binary_Golay_code
- jedimastert 6y agoI didn't realize he died from COVID complications. That just makes it all the worse.
- jon_elbrook 6y agoHe was 82.
- taylorlunt 6y agoHe was also a human being and he died.
- beefman 6y agoHow does it make it worse?
- jmcomets 6y agoSphere 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. :) [1]: https://github.com/dcoeurjo/ThicknessDiag https://github.com/dcoeurjo/ThicknessDiag
- cbisnett 6y agoI 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 https://bl.ocks.org/mbostock/dbb02448b0f93e4c82c3
- BubRoss 6y agoPoisson 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)
- deleted 6y ago[deleted]
- jhardcastle 6y agoThis is important now as schools are working to figure out how to place desks so that each student is 6 feet apart from their peers.
- julien__c 6y agoI recently saw pictures of social distancing circles drawn on the grass in parks [1]. They were drawn in a square grid. It would be more space-efficient to draw them in a hexagonal packing arrangement. [1] example: https://images.foxtv.com/static.ktvu.com/www.ktvu.com/content/uploads/2020/05/724/407/A79C558C64154B59A31E5D70963CFB76.jpg?ve=1&tl=1 https://images.foxtv.com/static.ktvu.com/www.ktvu.com/conten...
- skrebbel 6y agoI don't think space efficiency is a goal
- jakear 6y agoIndeed. Having lots of space between the circles is a better goal, as that way people in motion also maintain distance.
- jka 6y agoCircular markers could also be a lot easier to create repeatably and quickly (for example, using a pole and string) by staff responsible for creating distancing markers.
- adrianmonk 6y agoThey might have enough land in this park that they are not worried about running out of space before they can fit enough people in. In that sense, space efficiency probably isn't a goal. However, in the context of social distancing, 2m is a guideline, but additional distance will reduce your risk more. You can flip the question on its head and ask, if I used larger circles (such as 3m or 4m), is there an arrangement I could use to still fit the people into the area? If so, then using this arrangement should reduce risk further than using an arrangement that can only accommodate 2m circles. In other words, even if you are below max capacity and meeting the 2m minimum, different arrangements still have different levels of risk of transmission. Of course, at low enough densities, the gain becomes negligible.
- 6y ago
- simonw 6y agoSaw a beautiful example of this in action the other day in the Observable "cherry logo" notebook: https://observablehq.com/@observablehq/cheery-logo https://observablehq.com/@observablehq/cheery-logo
- dekhn 6y agoI once took a class from Huffman (one of the inventors of compression) and the very first class he talked about error correcting codes, and I remember him saying (25 years ago!) "Sphere packing is hard... except in 8 dimensions!" (https://en.wikipedia.org/wiki/Kissing_number https://en.wikipedia.org/wiki/Kissing_number) I failed the class, but learned so many useful things.