| Date: | December 14, 2004 / year-entry #422 |
| Tags: | non-computer |
| Orig Link: | https://blogs.msdn.microsoft.com/oldnewthing/20041214-00/?p=37023 |
| Comments: | 10 |
| Summary: | It's easy to distribute points evenly across a flat surface, but doing so over a curved surface is a much more complicated problem. Even spheres are hard. NPR's Scott Simon interviews mathematician Ed Saff who with colleague Doug Hardin has developed a new method of attacking this complex problem. Press release from Vanderbilt University .... |
It's easy to distribute points evenly across a flat surface, but doing so over a curved surface is a much more complicated problem. Even spheres are hard. NPR's Scott Simon interviews mathematician Ed Saff who with colleague Doug Hardin has developed a new method of attacking this complex problem. Press release from Vanderbilt University . You can also download the paper (in PDF form) from Dr. Saff's home page, if you think you're smart enough to understand it. (Don't ask me for help. I have two degrees in mathematics and was in over my head by halfway through page 2. I couldn't even make it out of the Introduction.) |
Comments (10)
Comments are closed. |
Distributing points evenly is very hard, I usually do something along the lines of http://mrl.nyu.edu/~perlin/experiments/repel/ as a preprocess and be done with it.
I don’t know that "make a bunch of points repel each other" is really a new technique. I first encountered this basic technique a long time ago, on this delightful (but rarely updated) home page:
http://www.traipse.com/nine/index.html
I don’t think the technique is new either. I haven’t read the paper yet, but I assume they’ve thrown in something new. I had a toy app a few years ago that used a similar technique to generate an arbitrary number of colors for a graph such that no two colors were too "close". In that case, the metric on the color space was more important than the particular exponent in the force function. But the idea is the same.
I also remember a talk from when I was in grad school by someone who was using the technique to place points on the surface of a sphere. In that case, it was a small number of points. E.g. 5 points go 3 on the equator, 2 at the poles, etc. (similar to Eric’s link). Some distributions were unintuitive, and some had several different "local minima".
I think the paper provides a mathematical tool to distribute points evenly on any type of curved surfaces, not just a sphere (as in most examples i read from some links)
Using repulsion to distribute points over a surface isn’t new. An analytical result connecting the way the points distribute, the exponent of the repelling function and the dimension of the surface, is new. This lets you choose a repelling function that will give a provably optimal distribution of points.
For those too lazy to navigate the gruesome Vanderbilt site (and I did not see a link in the news article):
http://www.math.vanderbilt.edu/~esaff/saff_articles.html
It’s the topmost paper.
"It’s the topmost paper" That criteria for finding the paper will certainly be no longer true at some point! The papers seem to have fixed numbers; is it the paper numbered 201? That’s the topmost at 6:04 PM Mountain time USA on 12/16/2004.
I was highly amused to read on Raymond Chen’s blog the other day that mathematicians are hard at work