thinking

[New wiki page on Voronoi diagrams]

A Voronoi diagram (named after Russian mathematician Georgy Voronoi, 1868-1908) is a partition of space based on a set of points. This is the main idea: we are given a set – usually small and sparse – of points which we’ll call Voronoi centers. Let’s suppose that each of these center points has its own color. Then we can color all of space by coloring any point according to the center it is closest to.

In the figure here (from wikipedia), each black dot is a Voronoi center, and the cells are colored accordingly.

It’s easy to think of some places where we might see similar patterns in nature. For example, the shapes on a turtle’s shell, or the hexagons of a honeycomb resemble Voronoi diagrams. Close-packed living cells sometimes do as well, maybe because as they became further squished together, their boundaries approached a shape optimized for packing.

You might notice that every cell in a Voronoi diagram is convex - it is a shape without “dents” – every line between two points in a Voronoi cell is contained within that cell (contrast this with, say, pac man). So every Voronoi diagram is a convex partition. Is every convex partition also a Voronoi diagram? No! In fact, there are many ways to draw a convex partition which is impossible to represent as a Voronoi diagram (see the wiki for some details).

But for those convex partitions which allow a Voronoi diagram, how hard is it to find the corresponding center points? With the right algorithm, it’s not so difficult. Here’s the main idea: draw a circle around some intersection of three boundaries in the convex partition, pick a random point, and reflect it around the boundaries. After reflecting three times, take the average of this point, and the starting point, along the circle. What you get is a working Voronoi center for that intersection. Reflect this point around to find the other two centers (if you reflect it three times, you’ll just get back to your original point). Check out the figure.

Once we have candidate Voronoi centers for any two adjacent 3-intersections, you can expand the circles on which these centers exist until the centers line up. These centers are guaranteed to be the correct unique center for their cells (assuming that the convex partition is a Voronoi diagram). From here, just reflect the centers over the neighboring boundaries of the partition to find all other centers.

This is just a quick summary of a few of the thoughts on the wiki page.

Let’s imagine: tomorrow your employer dissolves. All corporate assets are split evenly among all employees, and everyone is told to work for themself, or in a group of former co-workers. Would the innovation in your sector get better or worse?

Let’s call this hypothetical post-employer innovation your company’s creative baseline.

A lot of companies follow goals that look like this: make money by solving problems we can get paid to solve. Often, they think this way because it’s just a job to most employees — including executives.

Without any serious experience or business degrees to justify my claims (well, beyond some raw rationalization below), I’m going to propose the following business paradigm:
1. Do one thing very well
2. Keep your creative baseline high
3. Exceed your baseline

Of course, these ideas go together. You could always claim 1 as your ultimate goal, and argue that money and innovation are just subgoals to keep doing that one thing really well, for more customers, over a longer timespan.

But it seems as if a lot of companies aren’t thinking about 2 and 3.

Keeping your baseline high means working with people who think for themselves – and are good at it. If you’re hiring people you couldn’t imagine as worthy competitors, why are you expecting anything more from them at your company?

Exceeding your baseline is even trickier. But this is the fundamental idea of growing a company in the first place – you can do better together than you could apart. The problem is that an employee, as opposed to a founder, inherently has less freedom and less accountability for their contributions. At the same time, you can offer them access to invaluable resources they’d probably miss on their own: capital, an existing corporate reputation, and each other.

Why should these goals, among the plethora of proffered principles, be singled out?

Because stagnant and errant businesses die, but sectors keep on going. Company Old doesn’t disappear because customers stop caring about a general problem they need solved — it gets replaced by Company New that offers a better approach. The golden ticket for Company Old to avoid replacement is to employ the creative minds that can create the new – and to enable them to build Company New from within.

Have you ever wanted to put something very silly, esoteric, zany, or just very poorly edited on wikipedia, but never bothered because you knew it would be removed immediately anyway? I know the feeling. But now at long last is your chance to edit a very new, wide-open, and very-poorly-edited wiki!

Introducing the thinking blog’s wiki.

To get things started, I’ve added a few brainteasers. Add your own! Or anything you’d like! Enjoy.

civilization = opportunity available to every individual

It might be good to have a way to measure civilization, since it’s certainly something we want to improve throughout the world, and (a fact which I think is often overlooked), things are not always improving. If you compare the enlightened advances made by Greek polymaths and efficient Roman administration to the backwards thinking and atrocious living conditions of the dark ages, you might be able to imagine how such a relative change might still occur from our current seemingly-secure quality of life. It’s not an Orwellian dystopia or world war III we should fear so much as it is a gradual and subtle shift of cultural and moral attitudes toward dogmatic, authority-based, or mystically-inspired modes of “thinking”.

The point is that we should keep our eyes open to how well the world is doing.

Of course, there are too many factors and subjective terms to immediately quantify “civilization” as if it were some kind of test score. Nonetheless, numbers, as objectively defined as is reasonably possible, are less likely to fall prey to misinterpretation.

So how can we quantify opportunity? As any engineer is likely to suggest, when you’re trying to improve the overall performance of a complex system, it’s a good idea to start with the bottlenecks – the pieces that are holding everything else back.

With that in mind, I propose that we could currently use the number of years of wasted life as a number for how much the world could be improved. It will be a great day when we can pragmatically measure opportunity and civilization in some more optimistic terms, such as average years of education per individual, or amount of nutrition practically attainable to anyone. For now it seems that preventable (by education or otherwise) diseases, conditions, or circumstances (such as war or human-created accidents) is certainly the most significant reason typical for an individual to be deprived of a great deal of living opportunities.

To list just a few major preventable causes of death at large today in the world:

Current (very rough approximation) civilization score (in #deaths / year): -8 million

Most proofs that I’ve seen feel like defensive, motley soups of disparate thoughts whose composition does indeed imply the theorem in question; but the reader is left without a strong intuition as to why the fact is true.

To illustrate: Consider one of the most fundamental theorems of mathematics: the Pythagorean. Given a right triangle with sides of lengths a, b, and hypotenuse c, we must have a² + b² = c². Euclid, in The Elements, presented an argument for a proof involving many steps (14, by wikipedia’s current count) which involves showing the similarity of several triangles and the equivalence in area of various different shapes. Check out wikipedia for the full proof.

Euclid’s proof is mathematically sound. It achieves its aim of demonstrating, beyond a doubt, that in fact a² + b² = c² for all (Euclidean) right triangles. What it leaves wanting is intuition. Why? How can a human, without resorting to memorization, understand that the sides must relate in this manner, upon seeing any right triangle? [The word grok comes to mind.]

I think that some proofs do achieve this higher standard of explaining the fact that they defend. Here, in a single picture, is a complete proof of the Pythagorean:

If I were a teacher, trying to convey as best I could the intuition behind this theorem, I would animate this figure so that the ratio a/b transitioned from 0 to infinity and back repeatedly — the point being to further the deep comprehension that the equality in area between the squares in question is independent of the acute angles of the triangle.

To give another example: one way to view De Moivre’s theorem is

cos (nx) = Real[ (cos x + i sin x)ⁿ ].

De Moivre proved this before Euler’s formula, e^ix = cos x + i sin x, was known. One proof follows by induction on n — assume it holds for n, then show it still holds for n+1. (The base case, n=1, is trivial.)

Suppose you saw this formula and the proof by induction. Would you really say that you knew why the formula was true? I am guessing that most people, including mathematicians, would gain profound new insight into this theorem when seen in terms of Euler’s formula. In that case, we should restate De Moivre’s theorem as

(cos x + i sin x)ⁿ = cos(nx) + i sin(nx),

and it becomes a very straightforward corollary of Euler’s formula:

(e^ix)ⁿ = e^i(nx).

With Euler’s formula, De Moivre is just one perspective of a special case; it’s a shadow on our allegorical wall, while Euler shows us the true form of the fact.

Most math work today is presented as if intuition were a burden to be borne rather than the enabler of our creativity. Gauss in particular is infamous for hiding the how-d’you-think-of-that of his work. Perhaps the math community as a whole would move along more constructively if we embraced the major role intuition and deep understanding play in our creative efforts.

One does not discover a complex path of reasoning without a guess at the lay of the land. Why ignore the curve of the lines while we strive to connect the dots?

I’ve always been curious about why certain musical entities “feel” a certain way to most people — for example, why does a major chord feed nicer than a minor, or just a bunch of other random notes?

For elements of feeling which seem to be built in for most people, it makes sense to look for an evolutionary cause. Here are two possibilities that might relate our backgrounds with our current musical interpretations:

(1) Rising vs. dropping pitch. Usually when you hear an increasing pitch, it’s associated with increasing anticipation, while decreasing notes often reflect a release or departure. Simple examples include the half-note rising motive of the Jaws theme, or the ultimate farewell denoted by Chopin’s falling funeral march. Perhaps these connotations could have arisen from the natural Doppler effect — when a predator is approaching, or we are approaching prey, any noises from the nearing object will be increasing in pitch, while if our prey is escaping or we from a predator, the pitch is decreasing.

(2) Major and similar “nice” chords vs. dissonance. It seems to me that many “nice-sounding” chords are composed of pitch spectrums which could occur naturally as the overtones of a single sound-producer, while more dissonant progressions have less natural frequency ratios. In nature, we could associate something like a major chord with a single producer — be it friend or foe, it is easy to understand and work with. Dissonance could only arise from a large group (who are not inclined to speak in pitch). So our sense of harmony among chords might have some foundation in the mere plurality vs unity of a sound-producing unit.

I’d be interested to see more work along these lines. Perhaps if we can physiologically or evolutionarily understand why some things sound good to us, and others less so, we could be more conscious of how to make good music with more awareness than the current traditional teachings — which I think are more historically based than scientifically discovered — would otherwise encourage.

This is the answer to the last math puzzle. You should check out the puzzle before you read the answer!

avg(sums(S)) = ½ ∑S.

Why?

The main observation is that, for any T ⊂ S, avg({∑ T, ∑(S-T)}) = ½ ∑ S. We should also note that if ∑ T₁ = ∑ T₂, then ∑ S-T₁ = ∑ S-T₂; this means that whenever the sums of T₁ and T₂ overlap in sums(S), so do the sums of their complements. If we think of adding each pair {∑ T, ∑(S-T)} one at a time to build sums(S), then either both elements of the pair are already in the set, or both are not — either way, the average remains the same.

My friend Chris Altomare once asked me a math question which inspired this one:

Given a set S of real numbers, define the set

sums(S) := {t: t = ∑ T for some T ⊂ S}

and the set function

avg(S) := ∑ S / #S,

where #S denotes the size of the set S (we can leave avg(empty set) undefined).

As an example, let S = {2, 5, 7}. Then

sums(S) = {0, 2, 5, 7, 9, 12, 14};

the 0 is always included in sums(S) as the sum of the empty set. In this example, we also have avg(sums(S)) = 7.

Can you find a general formula for avg(sums(S)), for any set S?

This is actually not super-hard, but the trick is that the “obvious proof” is wrong — in other words, if we thought of the sums function as giving a multiset, then it becomes a linear function, which would make everything straightforward (since avg is based on linear functions, so avg(sums) is still linearly analyzable and thus easy to find and prove). But this is not the case!

Good luck! I’ll post the answer soon.

Have you ever noticed that you can pour soda directly into a cup of ice at most restaurants, but when you try it at home, your cup fizzes out the wazoo and all your carbonation is gone, like so many childhood daydreams dashed by the cruel, merciless fist of fate?

As a dedicated soda fan, this problem used to present no small helping of consternation at mealtime. Alas, by experimentation and some web browsing, I found that one small factor makes all the difference — the surface quality of the ice itself. If you simply make sure your ice is wet (no, ice is not always wet) then you will have copious carbonation upon pouring. Check out the video for some (informal) experimental evidence.

The inquisitive reader may inquire at this point: (a) how does that explain the way restaurant pouring works? and (b) why does this work at all?

(a) I believe many restaurants store ice not in a freezer, but rather in a bucket or other receptacle from which it may be easily dispensed. By allowing the ice to start thawing, the surface begins to melt, so that the ice is covered by a thin layer of water (i.e. it’s wet).

(b) Rob Landolfi describes the action of the surface of the ice as a collecting point for carbon dioxide molecules. CO₂ is non-polar, as opposed to H₂O, so that when a bubble of the gas starts to form within the liquid, it leads to a cascading effect (more CO₂ is likely to run into a large gas bubble) which results in a larger bubble that rises to the surface and escapes. In the absence of a rough surface to catch a few CO₂ molecules, they are more likely to never hit each other, and the bubbles are less likely to form.

Notice in the experiment that many factors remain the same — the temperature of the soda, the number of ice cubes, the surface area of the ice and the glass — even the temperature of the ice itself remains very similar. This should debunk some other possible hypotheses about how ice removes carbonation.

Enjoy your drink!

I just wrote up a quick hint and a solution to the gnomes-in-a-circle puzzle (see the last post for the puzzle).