Circle Packing | Hacker News Reader

Circle Packing

en.wikipedia.org

Sphere 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

I didn't realize he died from COVID complications. That just makes it all the worse.

He was 82.

He was also a human being and he died.

How does it make it worse?

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. :)

[1]: https://github.com/dcoeurjo/ThicknessDiag

Our of curiosity and as a noob to coding theory, what makes a Binary Golay code more useful than say a RS Code or something else more common?

The linked wiki article said that given 12 bits, the BG code can encode them as 24 bits with the ability to correct up to 3 bit errors and detect up to 7. If I'm understanding RS codes correctly, an RS code with 12 data and 12 parity bits would be able to correct up to 6 bit errors and detect up to 12. So what is the advantage of a BG code in that case?

I am no expert either, but I just checked Wikipedia on Reed-Solomon codes [1]:

> By adding t check symbols to the data, a Reed–Solomon code can detect (but not correct) any combination of up to and including t erroneous symbols, OR locate and correct up to and including ⌊t/2⌋ erroneous symbols at unknown locations

So it looks like you would have to choose between, either:

   A) correcting 6 bits OR
   B) detecting 12 bit errors.

No?

[1] https://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_cor...

The correct interpretation there is that for any given R-S code, the tolerance for correctable errors is half as many bits as the tolerance for uncorrectable but still detectable errors. If you have an R-S code constructed to correct 6 bits or detect 12-bit errors, then for a given message:

if the number of corrupted bits is no more than six, you can reconstruct the original message

if the number of corrupted bits is between 6 and 12, you will detect the corruption

if the number of corrupted bits is larger than 12, you may or may not detect the corruption.

The binary Golay code works on bits. Reed-Solomon code works on symbols that are comprised of many bits. A RS code with 12 data and 12 parity symbols (not bits!) must have symbol representation of at least 5 bits to cover 12 + 12 = 24 possible code locations. Bit-wise such code will reliably correct only 6 bit errors out of 24 * 5 = 120 bits (assuming t/2 error correction algorithm). If the errors come in bursts, however, that code can correct up to 6 * 5 = 30 bits.

Can you suggest some books to learn interesting math topics for someone with just high school understanding of math?

There is a great Numerphile video that links sphere packing to mathematics. https://youtu.be/CROeIGfr3gs

One reason it’s fascinating for me is there are many unsolved problems that you can explain to lay people easily.

Sometimes it feels like it’s kind of trying to bait you into thinking: Hmm, that doesn’t seem that hard to prove, maybe I should spend some spare time on it.

edit: in case it’s not obvious I’m not trying to be presumptive The fart of trying some of these doesn’t last long .

I may fantasize for a minute after reading one, then remember there have been many “simple”problems that went unproven for hundreds of year or longer.

something like trisecting an angle with a protractor I would guess drove a few people to near insanity.

I 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)

I failed the class, but learned so many useful things.

I 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/conten...

I don't think space efficiency is a goal

Indeed. Having lots of space between the circles is a better goal, as that way people in motion also maintain distance.

Circular 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.

They 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.

There's a picture from a Belgian school using hexagons.

https://www.theguardian.com/world/gallery/2020/may/30/how-we...

I 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)

I wrote about sphere packings and their relation to lattices here: https://nullset.xyz/2016/12/11/lattices-and-sphere-packings/

Saw a beautiful example of this in action the other day in the Observable "cherry logo" notebook: https://observablehq.com/@observablehq/cheery-logo

Circle 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

I 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.

I made a tool that does this with Chrome memory profiles

https://heapviz.com/

Also ported d3s circle packing algorithm to C++ for compilation to WASM

https://github.com/tomlagier/circle-pack

Definitely love how that visualization turns out!

This 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.

I 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.

Reply on news.ycombinator.com