Centroidal Voronoi Tessellations

Today was my first full day at the visualization conference in Minneapolis “dang it’s cold here” Minnesota. All of my local contacts informed me there were still tickets available for the Packers-Vikings game. Not wanting to find out if pigs were clogging the airways, I passed up the opportunity and went to the conference.

In my bike’s standard commuter configuration (rack, fenders, lights, handlebar bag, bungee cords, seat pack, mirror), it weighs a hefty 38.5 pounds. I had to take all that stuff and the pedals off to pack it into the suitcase. The bike was much lighter: 19.5 pounds. Minneapolis’ weather is supposed to be sunny this week, so I left everything except the lights and mirror at home. Total weight of the bike, pedals, tools, spare tire, seat pack and suitcase: 25.5 pounds (airport scale). TSA did not want to inspect it. This means they’ll want to do everything to it on the way home.

On the bus to the hotel this morning, we ran into Pete, an ex-employee. Pete’s a funny guy, and for some reason was ranting about “obsessive exercisers” at his current place of employment. Both of my corworkers were laughing their asses off because not only did I have my Ride Around Washington T-shirt on, but I had brought my bike with me. I think they told Pete later.

My primary reason for coming here so early, on a Sunday, was to sit in on the general purpose computation using graphics hardware tutorial. The theory is desktop CPUs have reached limits in raw processor speed because of density and cooling concerns. CPU manufacturers are working around some of these limitations by making “dual core” processors available as their marketing people stopped touting the “GHz” in favor of relative numbers. Now they’re back to stupid terms like “Extreme Edition Dual Core” Meanwhile, video cards’ performance has been driven by high-end games. They have processors capable of sustained, high-rate computation and parallelism, e.g. tricks to make Halo 2 and Doom 3 quickly animate beads of flesh off an exploding Bugblatter beast of Traal (or whatever) when hit by the BFG. The presenters suggested the newer video processors are 10x as fast as a CPU for some operations.

It’s interesting stuff, but still a couple of years away from my marketing sense feeling like it’s a strong
enough proposition to undertake. For example, although NVIDIA and ATI are the big gorillas in the market, there’s insufficient standardization and open documention. (Makes sense: this falls outside of their business case.) If I, a vendor, spent a year writing and debugging an application for low-level usage of the processors, I’m afraid I might likely discover the cards are obsoleted. Or perhaps not upwardly compatible with the new hotness designed for Halo 3 or Doom 4. GPUs also aren’t ideal for reading data back into the computer where I could store a result.

When the discussion got too technical for me, I sat in on other seminars, including “voronoi treemaps.” It’s been 15 years since I regularly looked at pure, technical papers like thes. I had flashbacks to the Ph.D. program when I
read this:

“A centroidal voronoi tesselation is a special Voronoi tesselation with the property that each generator pi is itself the center of mass ci of the corrosponding Voronoi region V(pi). Obviously there exist many different CVTs for a given number of generators.” (source)


Thanfully the presenter wisely included animations showing how this treemap algorithm works for weird (non-rectangular) shapes. I’m not sure on the applicability to my product, though the animations and pictures were pretty.

3 thoughts on “Centroidal Voronoi Tessellations”

  1. The only testellations I’m familiar with are the MC Escher kind. I went to an Escher exhibit at a gallery in Los Angeles back in ’72 or ’73 with some high school friends. As I recall, brownies were involved…

Leave a Comment

Your email address will not be published. Required fields are marked *