Hulver's site || Step AWAY from the keyboard!

Diaries
Everything
Who's Online?
FAQ / Help

sitting around, avoiding measure theory

By gzt (Thu Oct 24, 2013 at 10:15:34 PM EST) gzt, measure theory, rusty abysses of my mind (all tags)

damn, this feels like the early K5 days.

inside: a problem you cannot solve.

lol pushforward measure.

problem: how many congruent regular tetrahedra can be packed around a vertex?

I'm starting to have to tear this crap from the rusty abysses of my mind.

in other news, i got that time series test back, i did pretty okay, which surprised me for how much i was flubbing around at the time.

so this continues my trend: high marks on theory, abysmal on methods. maybe i should try to get a co-major with a department that would get me out of methods.

somebody's teaching an experimental course on "functional data analysis" eg analyzing functional data, which are high dimensional data resulting from discrete, error-contaminated measurements on smooth curves and images etc. uh, i think you mean, "a course on exactly what i want to go on to do after i finish this related project". i'll see what my adviser says, though i think he'll suggest it if he hears about it before i mention it to him. i mean, it's like i said, 'man, if only there were a course about the stuff i was trying to learn by reading papers but not quite getting,' and somebody said, 'sure, i'll totally teach this.'

"Why did the digamma die out?" "There was a stigma!" It's... a terrible pun.

< Biking in Sheffield | 43 species of parrot! Nipples for men! Slugs! Are we not in the hands of a lunatic? >

Login

Poll

Votes: 2
Results	\|	Other Polls

Related Links

- k5
- gzt's Diary

Hit Counter

69 Husi users have viewed this.

Comment Controls

sitting around, avoiding measure theory | 26 comments (26 topical, 0 hidden)

hmm by gzt (2.00 / 0) #1 Thu Oct 24, 2013 at 10:59:17 PM EST

apparently the parents had to put one of the dogs down. it wasn't that old - maybe 6.

Answer by ucblockhead (2.00 / 0) #2 Fri Oct 25, 2013 at 11:32:48 AM EST

As many as you want if your hammer is big enough.
---
[ucblockhead is] useless and subhuman

Someone by anonimouse (2.00 / 0) #3 Fri Oct 25, 2013 at 03:02:42 PM EST

Needs to get lots of D&D 4 sided dice...

Girls come and go but a mortgage is for 25 years -- JtL

Guess by anonimouse (2.00 / 0) #4 Fri Oct 25, 2013 at 03:07:34 PM EST

6 round flat, plus another 3 above them, plus a 'capstone' making 10, so 20 in total around a point.

Girls come and go but a mortgage is for 25 years -- JtL

20 is a lower bound, which you have achieved by gzt (2.00 / 0) #5 Fri Oct 25, 2013 at 04:30:39 PM EST

however, the question is, what's the upper bound? can we prove that 21 or 22 is impossible?

a naive numerical upper bound is 22.

[ Parent ]

I have a theory by anonimouse (2.00 / 0) #6 Fri Oct 25, 2013 at 05:27:35 PM EST

...it must be bunnies (/Buffy)

Each tetrahedron occupies the minimum amount of space at the point (0).
The entire volume surrounding the vertex is completely filled with tetrahedrons. i.e. there is no empty space.

I can't write a mathematica formula to prove it, but have a theory that the two facts are sufficient to prove that 21 or 22 is impossible

Girls come and go but a mortgage is for 25 years -- JtL

[ Parent ]

I'm not sure I can calculate it... by ana

(4.00 / 1) #7 Fri Oct 25, 2013 at 05:41:29 PM EST

but one could, in principle, calculate the solid angle subtended by a regular tetrahedron viewed from one vertex. I surmise, based on gzt's comment, that if one does this, and divides it into the 4*pi for the whole sphere, one gets 22 and change. So that's an upper limit. Whether you can actually pack that many in without dismembering or slicing them is another problem entirely.

I'd think studying how many you can gather around one edge might be fruitful. Then consider several different edges radiating from the vertex in question.

I now know what the noise that is usually spelled "lolwhut" sounds like. --Kellnerin

[ Parent ]

Yeah, that's how you get the 22 and change by gzt (4.00 / 1) #8 Fri Oct 25, 2013 at 05:57:21 PM EST

[ Parent ]

You can only get 6.9ish round an edge by ambrosen (2.00 / 0) #9 Fri Oct 25, 2013 at 06:10:59 PM EST

I calculated 6/(sin (pi/3)), which is messy thinking, and I can't be bothered to put it in a way that makes sense.

So it's a question of how you can gather the 0.93 of the space needed into enough of a place to put the spare tetrahedra.

[ Parent ]

Or whether you can gather more space elsewhere by gzt (2.00 / 0) #10 Fri Oct 25, 2013 at 06:48:50 PM EST

somehow. still an open question after 11 years.

[ Parent ]

i've probably said all this before by the mariner (2.00 / 0) #12 Mon Oct 28, 2013 at 05:55:42 PM EST

and this will just show how addled my brain has become, but a couple of things about your tetrahedron problem:

first, this is the kind of problem that someone like you should try simulating. it's not particularly hard to come up with a random model for points in the sphere with a unit tangent vector (msg for references if i can remember them). basically, i think you can use the SVD of a random matrix to sample uniformly from SO(3), which can be identified in a canonical and geometric way with the unit tangent bundle of the 2-sphere. with such a sampling method in hand, it is straightforward to produce random triangle configurations in the sphere, corresponding to your tetrahedron packings. then you need something to check your configurations for collisions in a reasonable way. i don't have any good ideas for that, actually -- this kind of thing is surprisingly annoying, i've found. hell, you could probably just use some kind of physics engine for games. this way, you can at least approach the question experimentally and possibly construct examples of maximal packings by blind luck/brute force.

of course, there's a more fun way to do it: you can build models. basically, you get a basketball or another standardized, spherical piece of sporting equipment and find out its radius. use this to make little curved triangles out of paper or whatever you have -- it would be particularly cool to do this with magnetic tape and a magnetic substrate. the triangles just have to have angles 70.5 degrees or whatever it is. the way to do this is to figure out what the lengths of the edges should be (something like radius*70.5*2*pi/360) then just glue them together. they'll bend for you automatically when you fasten them together this way. make 22 such triangles, and start sticking 'em on the ball. i call this the thurston method. fun for the whole family!

[ Parent ]

yes... by gzt (2.00 / 0) #14 Mon Oct 28, 2013 at 06:17:58 PM EST

...it's more willingness to actually sit down. checking for collisions is definitely the annoying part. I should look at how people do maximal sphere packing problems - very different problem, but it's the same general idea.

[ Parent ]

: well, here's a stupid way to do it: by the mariner (2.00 / 0) #15 Mon Oct 28, 2013 at 06:37:14 PM EST

pick a bunch of points on (the boundary of) each triangle and check for containment of each in other triangles, with some heuristics to avoid totally stupid comparisons. (e.g. first check distance between the centers of each triangle, etc.) a fairly stupid approach to this will efficiently eliminate almost all inadmissable configurations. if a configuration passes your stupid test, try a marginally smarter test with more test points.
my guess is this is the kind of thing that won't be that tight, anyway. like, if you can find one where your shitty collision detection works with, like, 100 points on the boundary of a triangle, then it's probably a correct configuration.

[ Parent ]

Can't you do it with flat equilateral triangles? by ambrosen (2.00 / 0) #16 Mon Oct 28, 2013 at 08:04:28 PM EST

and stick the centres on the ball. Side length of the triangles would be √(3r/2) for a ball of radius r.

[ Parent ]

: i guess you could, by the mariner (2.00 / 0) #17 Tue Oct 29, 2013 at 01:48:00 PM EST

but it seems somewhat messier than spherical triangles that exactly match the curvature of the ball. like i said, if you cut the lengths right and fasten them at their corners, they will want to bend into the right shape all by themselves.

[ Parent ]

oh, yeah... by the mariner (4.00 / 1) #13 Mon Oct 28, 2013 at 06:08:20 PM EST

part of my point in the other comment is that the question is actually one of two dimensional spherical geometry (the sphere = rays from the origin). perhaps another way to approach it is to think about packings of equilateral triangles with other angles to see if some interesting pattern emerges.

experiment!

[ Parent ]

-.- by the mariner (2.00 / 0) #11 Mon Oct 28, 2013 at 05:33:03 PM EST

the dihedral angles in a regular tetrahedron are a little over 70 degrees -- you can therefore only get five around an edge. i guess if you wanted to continue on this line of reasoning, you could think of the pentagon you get out of this if you do it in the most symmetric way and continue the opposite edges, calculate its area in the way ana suggests above (see the gauss-bonnet theorem) and see how many of those you can get in there. then you could try to actually realize a configuration with that many pentagons -- my guess is this is doable and that you can get 20 tetrahedra that way. anyway, see other comment...

[ Parent ]

You get an icosahedron that way by blarney (2.00 / 0) #18 Thu Oct 31, 2013 at 03:11:48 AM EST

I think the thing is if you actually replaced the faces of an icosahedron with tetrahedra you'd find that they didn't quite match the radius of the icosahedron - they'd have slop, they'd slide around - and the question is could he fit in a 21st or even a 22nd? I have no idea, I suspect you can't get more than 20 but I have no idea how to prove it.

If you look at the dual of the icosahedron, you get the dodecahedron, which makes me wonder if this problem is isomorphic to the proven "kissing number" of 12 for spheres - if you actually take 13 spheres and pack 12 around the remaining 1, it looks like you oughta be able to slide another sphere into there if you move things around right, but you can't and it's been proven that you can't.

I wonder if this problem can be reduced to that one.

[ Parent ]

it's not the same. by the mariner (2.00 / 0) #19 Thu Oct 31, 2013 at 07:18:20 AM EST

if you think about it in terms of packing spherical triangles, you're looking at packing equilateral triangles with angles 72 degrees vs. ~70.5. but you're right, the icosahedron gives you an example of a similar problem that is solved and a lower bound for the number of tetrahedra (i wasn't thinking of this when i wrote the pentagon bit, but i guess i should have).

i think gzt has written before that it's known the answer is at least 21 and from area considerations, it could be 22. i've never thought seriously about it or even done the area calculation, so you know...

actually, what the hell? so the area of a 72-72-72 spherical triangle is (2pi/360)*(216 - 180) = pi/5 (i think). you want to cover the sphere which has area 4pi with these things, so you get exactly 20. now if change your angles to 70.5, you're losing 4.5 degrees worth of area, which is actually a lot, more than 10% of the area of a triangle in the icosahedron case. if you renormalize the area to be in "degrees," you get about 720/31.5 as your naive upper bound on the number of triangles, which comes out to almost 23. so the change makes a surprisingly big difference in the "expected" outcome and it would seem really strange if you really couldn't wedge at least one more triangle in vs. the icosahedron.

[ Parent ]

21 isn't known to be a lower bound AFAIK by gzt (2.00 / 0) #20 Thu Oct 31, 2013 at 07:25:12 AM EST

yes, area comes out to 22.

[ Parent ]

i would be astonished if it isn't. by the mariner (2.00 / 0) #21 Thu Oct 31, 2013 at 07:58:42 AM EST

there's tons of space for an extra triangle. it wouldn't surprise me at all if there's room for 22 based on this calculation.

you know, another thing you could do is start with a known configuration like the icosahedron and do some kind of dynamical simulation with biased brownian motion or simulated annealing or sth. it sounds very likely to me that the answer is 22 and that an actual configuration could be found by a not-that-tricky simulation.

[ Parent ]

in other words, by the mariner (2.00 / 0) #22 Thu Oct 31, 2013 at 08:00:49 AM EST

try to simulate the process of pushing triangles away from certain points to make room for for new ones. obviously, a physical model would be a good way to do this...

[ Parent ]

You'd think someone would have found it by now by blarney (4.00 / 1) #23 Fri Nov 01, 2013 at 07:17:36 PM EST

This is a problem that's been worked on since Aristotle (erroneously) taught that tetrahedra, like cubes, could be packed to fill space, and his 12th Century fanboy Ibn Rushd falsely argued that the number of tetrahedra which can be packed around a vertex is 12.

So if there was an easy 21 or 22 configuration someone would have found it by now, probably?

Citation: http://www.ams.org/notices/201211/rtx121101540p.pdf

[ Parent ]

: that's so fuckin' weird. by the mariner (4.00 / 1) #25 Fri Nov 01, 2013 at 07:20:05 PM EST

i wrote that last comment without seeing yours o.o;

[ Parent ]
: dammit! by gzt (2.00 / 0) #26 Sat Nov 02, 2013 at 09:53:31 AM EST

the article merely acknowledges my question and its source, it doesn't solve it.

[ Parent ]

btw, you're in good company in this misconception. by the mariner (2.00 / 0) #24 Fri Nov 01, 2013 at 07:19:07 PM EST

aristotle thought the same thing.

[ Parent ]

sitting around, avoiding measure theory | 26 comments (26 topical, 0 hidden)