Slashdot Mirror
Computational Origami and David Huffman
geeber writes "Here is an article about David Huffman's work in the mathematics of computational origami at the New York Times (soul sucking registration required). According to the article, computational origami, "also known as technical folding, or origami sekkei, draws on fields that include computational geometry, number theory, coding theory and linear algebra." David Huffman is also the inventor of Huffman coding used in MP3s and was mentioned prieviously here."
lol nub
"Let's sue HIM too!!!" -RIAA
"Meow meow Matt Bruce meow meow Henrietta Pussycat meow meow Presidents of the United States of America meow Kitty?"
Are the purty pictures... Some of these origamis are incredibly beautiful. Does anybody know where to find other (high-res) pictures of them?
The right to offend is far more important than the right not to be offended. (Rowan Atkinson)
fetch me a lemonaide, poindexter!
*_g_o_a_t_s_e_x_*_g_o_a_t_s_e_x_*_g_o_a_t_s_e_x_*_ _ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __
g_______________________________________________g
o_/_____\_____________\____________/____\_______o
a|_______|_____________\__________|______|______a
t|_______`._____________|_________|_______:_____t
s`________|_____________|________\|_______|_____s
e_\_______|_/_______/__\\\___--___\\_______:____e
x__\______\/____--~~__________~--__|_\_____|____x
*___\______\_-~____________________~-_\____|____*
g____\______\_________.--------.______\|___|____g
o______\_____\______//_________(_(__>__\___|____o
a_______\___.__C____)_________(_(____>__|__/____a
t_______/\_|___C_____)/_LINUX\_(_____>__|_/_____t
s______/_/\|___C_____)_INSIDE|__(___>___/__\____s
e_____|___(____C_____)\_(TM)_/__//__/_/_____\___e
x_____|____\__|_____\\_________//_(__/_______|__x
*____|_\____\____)___`----___--'_____________|__*
g____|__\______________\_______/____________/_|_g
o___|______________/____|_____|__\____________|_o
a___|_____________|____/_______\__\___________|_a
t___|__________/_/____|_________|__\___________|t
s___|_________/_/______\__/\___/____|__________|s
e__|_________/_/________|____|_______|_________|e
x__|__________|_________|____|_______|_________|x
*_g_o_a_t_s_e_x_*_g_o_a_t_s_e_x_*_g_o_a_t_s_e_x_*
Important Stuff: Please try to keep posts on topic. Try to reply to other people's comments instead of starting new threads. Read other people's messages before posting your own to avoid simply duplicating what has already been said. Use a clear subject that describes what your message is about. Offtopic, Inflammatory, Inappropriate, Illegal, or Offensive comments might be moderated. (You can read everything, even moderated posts, by adjusting your threshold on the User Preferences Page) If you want replies to your comments sent to you, consider logging in or creating an account.
Important Stuff: Please try to keep posts on topic. Try to reply to other people's comments instead of starting new threads. Read other people's messages before posting your own to avoid simply duplicating what has already been said. Use a clear subject that describes what your message is about. Offtopic, Inflammatory, Inappropriate, Illegal, or Offensive comments might be moderated. (You can read everything, even moderated posts, by adjusting your threshold on the User Preferences Page) If you want replies to your comments sent to you, consider logging in or creating an account.
Important Stuff: Please try to keep posts on topic. Try to reply to other people's comments instead of starting new threads. Read other people's messages before posting your own to avoid simply duplicating what has already been said. Use a clear subject that describes what your message is about. Offtopic, Inflammatory, Inappropriate, Illegal, or Offensive comments might be moderated. (You can read everything, even moderated posts, by adjusting your threshold on the User Preferences Page) If you want replies to your comments sent to you, consider logging in or creating an account.
Huffman coding was one of the first codings used to compress data LONG LONG time ago, in a galaxy far far away where MP3's were billions of years yet to come in the future.
It is real cool to see such pioneering people still involved in new things.
Yamaha Paper Craft
Life is the leading cause of death in America.
If your into folding and you like SETI@Home checkout Stamfords Folding@Home, it's not oragami but instead something alot more useful: understanding protien folding. Check it out here: http://www.stanford.edu/group/pandegroup/folding/
so this stuff would really turn Bender on ? and no i didn't rtfa :( anyone have a non-subscribe link ?
So.. who knows how to actually do all of that?
Hmmm.
www.mercatur.net
Why does mercatur taunt me...
She goes out with men who aren't me...
She hardly ever turns on her webcam anymore...
She never gets naked anymore...
She's having sex with every man she meets but won't consider me...
Why won't she love me?
Mercatur, please consider me for your next boyfriend.
Thangyoo.
www.mercatur.net
props to rrrroar
Click through from Google.
Life is the leading cause of death in America.
as /. performs computational origami on the server and fold it into a crumpled half-finished paper swan on the floor
--
Since he died in '99 he has become less involved.
Also, origami is not actually a new thing.
What Huffman was interested in was curved folds and stress points. Maybe it should be called Extreme Origami.
for those who don't want to bother with NYTimes "soul sucking registration" (or bugmenot.com ;)
Cones, Curves, Shells, Towers: He Made Paper Jump to Life
By MARGARET WERTHEIM
SANTA CRUZ, Calif. - On the mantel of a quiet suburban home here stands a curious object resembling a small set of organ pipes nestled into a neat, white case. At first glance it does not seem possible that such a complex, curving form could have been folded from a single sheet of paper, and yet it was.
The construction is one of an astonishing collection of paper objects folded by Dr. David Huffman, a former professor of computer science at the University of California, Santa Cruz, and a pioneer in computational origami, an emerging field with an improbable name but surprisingly practical applications.
Dr. Huffman died in 1999, but on a recent afternoon his daughter Elise Huffman showed a visitor a sampling of her father's enigmatic models. In contrast to traditional origami, where all folds are straight, Dr. Huffman developed structures based around curved folds, many calling to mind seedpods and seashells. It is as if paper has been imbued with life.
In another innovative approach, Dr. Huffman explored structures composed of repeating three-dimensional units - chains of cubes and rhomboids, and complex tesselations of triangular, pentagonal and star-shaped blocks. From the outside, one model appears to be just a rolled-up sheet of paper, but looking down the tube reveals a miniature spiral staircase. All this has been achieved with no cuts or glue, the one classic origami rule that Dr. Huffman seemed inclined to obey.
Derived from the Japanese ori, to fold, and gami, paper, origami has come a long way from cute little birds and decorative boxes. Mathematicians and scientists like Dr. Huffman have begun mapping the laws that underlie folding, converting words and concepts into algebraic rules. Computational origami, also known as technical folding, or origami sekkei, draws on fields that include computational geometry, number theory, coding theory and linear algebra. This weekend, paper folders from around the nation will gather at the Fashion Institute of Technology in New York for the annual convention of Origami USA. At an adjacent conference on origami and education, Dr. Robert Lang, a leading computational origamist, will give a talk on mathematics and its application to origami design, including such real-world problems as folding airbags and space-based telescopes.
Dr. Lang, a laser physicist in Alamo, Calif., who trained at the California Institute of Technology, gave up that career 18 months ago to become a full-time folder. "Some people are peculiarly susceptible to the charms of origami," he said, "and somewhere along the way the ranks of the infected were joined by mathematicians." Dr. Lang is the author of a recent book on technical folding, "Origami Design Secrets: Mathematical Methods for an Ancient Art."
Most computational origamists are driven by sheer curiosity and the aesthetic pleasure of these structures, but their work is also finding application in fields like astronomy and protein folding, and even automobile safety. These days when Dr. Lang is not inventing new models using a specialized origami software package he has developed, he acts as an origami consultant. He has helped a German manufacturer design folding patterns for airbags and advised astronomers on how to fold up a huge flat-screen lens for a telescope based in space.
Dr. Lang has been studying Dr. Huffman's models and research notes, and is amazed at what he has found. Although Dr. Huffman is a legend in the tiny world of origami sekkei, few people have seen his work. During his life he published only one paper on the subject. Dr. Huffman worked on his foldings from the early 1970's, and over the years, said Dr. Lang, "he anticipated a great deal of what other people have since rediscovered or are only now discovering. At least half of what he did is
SIGSEGV caught, terminating
wait... not that kind of sig.
By MARGARET WERTHEIM
SANTA CRUZ, Calif. - On the mantel of a quiet suburban home here stands a curious object resembling a small set of organ pipes nestled into a neat, white case. At first glance it does not seem possible that such a complex, curving form could have been folded from a single sheet of paper, and yet it was.
The construction is one of an astonishing collection of paper objects folded by Dr. David Huffman, a former professor of computer science at the University of California, Santa Cruz, and a pioneer in computational origami, an emerging field with an improbable name but surprisingly practical applications.
Dr. Huffman died in 1999, but on a recent afternoon his daughter Elise Huffman showed a visitor a sampling of her father's enigmatic models. In contrast to traditional origami, where all folds are straight, Dr. Huffman developed structures based around curved folds, many calling to mind seedpods and seashells. It is as if paper has been imbued with life.
In another innovative approach, Dr. Huffman explored structures composed of repeating three-dimensional units - chains of cubes and rhomboids, and complex tesselations of triangular, pentagonal and star-shaped blocks. From the outside, one model appears to be just a rolled-up sheet of paper, but looking down the tube reveals a miniature spiral staircase. All this has been achieved with no cuts or glue, the one classic origami rule that Dr. Huffman seemed inclined to obey.
Derived from the Japanese ori, to fold, and gami, paper, origami has come a long way from cute little birds and decorative boxes. Mathematicians and scientists like Dr. Huffman have begun mapping the laws that underlie folding, converting words and concepts into algebraic rules. Computational origami, also known as technical folding, or origami sekkei, draws on fields that include computational geometry, number theory, coding theory and linear algebra. This weekend, paper folders from around the nation will gather at the Fashion Institute of Technology in New York for the annual convention of Origami USA. At an adjacent conference on origami and education, Dr. Robert Lang, a leading computational origamist, will give a talk on mathematics and its application to origami design, including such real-world problems as folding airbags and space-based telescopes.
Dr. Lang, a laser physicist in Alamo, Calif., who trained at the California Institute of Technology, gave up that career 18 months ago to become a full-time folder. "Some people are peculiarly susceptible to the charms of origami," he said, "and somewhere along the way the ranks of the infected were joined by mathematicians." Dr. Lang is the author of a recent book on technical folding, "Origami Design Secrets: Mathematical Methods for an Ancient Art."
Most computational origamists are driven by sheer curiosity and the aesthetic pleasure of these structures, but their work is also finding application in fields like astronomy and protein folding, and even automobile safety. These days when Dr. Lang is not inventing new models using a specialized origami software package he has developed, he acts as an origami consultant. He has helped a German manufacturer design folding patterns for airbags and advised astronomers on how to fold up a huge flat-screen lens for a telescope based in space.
Dr. Lang has been studying Dr. Huffman's models and research notes, and is amazed at what he has found. Although Dr. Huffman is a legend in the tiny world of origami sekkei, few people have seen his work. During his life he published only one paper on the subject. Dr. Huffman worked on his foldings from the early 1970's, and over the years, said Dr. Lang, "he anticipated a great deal of what other people have since rediscovered or are only now discovering. At least half of what he did is unlike anything I've seen."
One of Dr. Huffman's main interests was to calculate precisely what struct
...is in Mark Nelson's "The Data Compression Book".
What's especially nice is that the book walks you thru the various steps - minimum redundancy coding, adaptive huffman coding, arithmetic coding... so the improvements are introduced gradually and logically. Good stuff.
The Army reading list
To be totally honest with this genius you have to mention that he was also member of the trio who invented the LZH (yes he was the "H" - good guess) compression algorithm.
testing 123, testing...
How many more slashdot frontpages before the NY times realise that by taking away registration, their advertising revenues will quintuple?
Or maybe they don't care about revenues! Maybe they just want our DATA?!?
Wait, wait.... sorry. It's the NEW YORK times! Silly me
May the Maths Be with you!
It's great to see someone so skillfully merge his knowledge of computer science and his appreciation for good aesthetics into such beautiful shapes. It seems many people who have an interest in programming and design try to merge these skills together, but more often than not the results are nothing but mindless attempts at combining the two just for the sake of it. It is good to see someone who has an real understanding of both and who can create meaningful examples of why each part is such a big part of the other.
Be sure to join us next week as David Huffman invites us to take a peek into the exciting world of quantum flower arrangement. :p
Can we drop the lame "(soul sucking registration required)" comments everytime a NY Times or similiar news posting is displayed? Those who read here are quite knowledgeable in getting around the registration process; if not, someone's going to post a comment with a Google link within minutes of posting anyways.
A simple "reg. req." is sufficient.
It seems to me that this is just taking another piece of art and removing the uniqueness of it. By taking Origami to a technical level is similar to looking at computer generated images instead of works of art. Granted, the ideas that are being calculated are still unique, but the look and feel may not be.
Aj
GroupShares Inc. - An Interactive Stock Market Community. If you're a trader check it out.
-------
artlu.net
Click here for a Penguin not as hard as David Huffmans designs but ideal for your linux box
Blarney Quality Restaurant, Plants
***General Consultant to the Human Race*** My opinions are free. You get what you pay for.
google link here
7680 MB Disk,192 GB Transfer,
It's funny guys! C'mon, it was a good Futurama joke!
Wheel in the sky keeps on turnin'.
Small world? Or a common name? You decide.
That's right. All your base.
If this interests you, be sure to check out Erik Demaine's work at MIT, Issei Yoshino's Super Complex Origami, HOYJO Takashi, Biruta Kresling's Keikki Bamboo folds, Robert Lang's Design Secrets of Origami, Robert Hull's Origami^3 compilation. Not all computational origami looks mathematical but the methods for getting to and end are clearly designed from step one. Quite frankly I understand very little of the math, but I can appreciate the elegance of an efficient fold.
I've always liked the idea of using origami for spacecraft. I can also envision universal constructor machines that convert asteroid materials into flat sheet and robotic systems that then fold long pieces of flat sheet stock into any shape that's needed (such as full size versions of these Star Wars spacecraft).
Two wrongs don't make a right, but three lefts do.
What I find impressive is that people like Huffman are possibly defining new application fields for mathematics, maybe leading to new theories, all from (originally) a hobby.
This reminds me of former mathematicians such as Euler and his Konigsberg bridges...
Ceci n'est pas une signature
[...] Huffman coding used in MP3s [...]
Why does everything have to be compared to MP3s? Why couldn't it have been 'Huffman coding used in ZIP files' or '[...] used by GZip' or '[...] used by the huffyuv lossless video codec' or any of about 5 million other applications that use huffman coding. Most of which are a lot more specific than MP3 which also uses a cocktail of other techniques to achieve compression and is, above all else, lossy, which huffman coding isn't.
To be transmitted across the Internet, this message was broken down into bits, like MP3s are.
3D objects, soccer balls, boxes or protein.
r ch /folding/
http://parasol.tamu.edu/groups/amatogroup/resea
As usual, several areas of math that are widely considered "pure" rather than "applied" turn out to have real world implications. The relationship of something as apparently trivial as folding paper to compressing and encoding data is a remarkable example of isomorphism in itself, beyond that:
If you're funding education or pure research, you never know when something will unexpectedly prove useful, or even valuable.
If you're the NSA, the RIAA, or any regulator you never know when or where the djinni will get out of the bottle.
(Insert pithy saying about chinese ideograms for danger and opportunity being isomorphic)
Who is John Cabal?
Vry nfrmtv chptr n lssy cmprsn?
Thr shld b n 'n' n th wrd 'on'
John_Chalisque
You misspelled Xtreme.
Eine kleiner, Amerikana!
I took a class taught by Professor Huffman at the University of California at Santa Cruz. He was an excellent teacher and really enjoyed teaching. The class, Introduction to Cybernetics, included Huffman coding and some basic neural network stuff, but never once did he call it Huffman Coding. One thing I remember from his class was we had to use a lot of logarithms and the results would have to be something like 5*log2(7) + log3(5). This ruled out using a calculator or a computer for the most part.
He also frequently gave credit to Claude Shannon on information coding.
Sadly (or fortunately) I avoided his other class, due to the fact that the failure rate was 60% for people taking the class for the second time. I think the first time takers failed at 90%.
-Aaron
This post is encrypted twice with ROT-13. Documenting or attempting to crack this encryption is illegal.
David Huffman passed away on October 7, 1999 from cancer.
Huffman coding is a way of representing some stream of symbols using bits in the most optimal way possible.
Essentially, it breaks down to using your bits in such a way that the most common symbols are represented by the fewest number of bits. The result is a prefix-free code, meaning that no string of bits that represents a symbol is part of the beginning of any other symbol. You'll never get both "01" and "010" representing something in a Huffman Code.
A Huffman Code is optimal, meaning that it results in the shortest possible way to turn symbols into strings of bits with a one to one mapping between a symbol and the bits that represent it. As a result, it's used in a lot of compression methods.
There are better methods, like arithmetic coding. Huffman coding assumes an integral number of bits used for each symbol. Arithmetic coding results in a scheme where you end up with, essentially, fractions of bits being used. Naturally, this requires a lot more computation. Huffman coding is relatively cheap, computation-wise, and it's pretty easy to do. This is why it gets used so much.
The really big deal about Huffman Coding, however, is that you can *prove* that it's the most optimal method for doing what it does. That was Huffman's big accomplishment, really. Shannon-Fano coding is similar to (but not the same as) Huffman coding, but Huffman can be proven to be the optimal way of doing it.
Do you know how many hours do classical musicians practice per day their technique? Obviously not.
Do you know how many hours do dancers practice their physical technoique? Certainly not.
Do you know that many of the most insightful writers will be voraceous readers and will constantly refer to grammar books, dictionaries and other technical resources? It would seem you don't.
Inspiration is frankly overrated, such point of view regarding "inspiration by the muses" so highly is a hangover of the XIX century romantic mentalitly, which of course forgot how the artists of that time worked uncountable hours to polish their technique.
IANAL but write like a drunk one.
Over 20 years ago, while I was an undergrad at UC Santa Cruz ("Go Slugs!"), I had David Huffman for CIS (Computer and Information Sciences) 10, "Introduction to Cypernetics".
This class covered a range of codes and encoding methods. We spent, surprise, some time on Huffman encoding, as well as covering Shannon's work.
Huffman was a great professor, and even back then he was doing the Origami work and should it to us in class.
Yours,
Jordan
There was also an article in Computer World Magazine, about Robert Lang's software that's being used to fold stuff from airbags to solar panels in spacecraft.
The class, Introduction to Cybernetics, included Huffman coding and some basic neural network stuff, but never once did he call it Huffman Coding.
I imagine that him calling it "Huffman Coding" would be a bit like going to China and asking where to eat Chinese food.
You may want to read the article I wrote over at kuro5hin on Christian Reconstructionism. Yes, self promotion. But it ties in closely with your sig.
http://www.hitmaker.co.jp/site/download_pcm.html
On the topic of origami, I'm currently interacting with one of the top twenty something origami designers in the US, and I must say that the art origami is much more beautiful and elegant than I expected.
On the note of the origami folder, I said interacting with because he isn't a coworker.. He's a student at an academic camp I'm working at. I'd seriously suggest looking at his work, or at least some specific amazing folds that he's designed. The designs clearly have mathematical elements, and he currently plans on developing a Java program to aid in creating the circle/river packing diagrams (the red lines.)
It's kind of scary to know that a sixteen/seventeen year old is doing such complex work, as is evident from his origami folding and his mathematical ability in class.
This statement is false.
I took Huffman's Cybernetics course a decade ago at U.C.S.C., and he did call it Huffman Coding at that time. He even told us the story of how it originated. He was a grad student at M.I.T., and I believe Claude Shannon was his advisor. He had a choice where he would either have to take a nasty final exam or do an independent project.
He decided to work on the issue of finding the most efficient way to re-code a known set of symbols. So he played around with all sorts of approaches, but the deadline for the final was approaching. Finally he had to go out and take the final, because he was out of time, so he tossed all his note papers in the trash. As he was heading for the door, he noticed the paper which had landed on the top of the pile in the trash, and there was Huffman coding.
I get the impression that Shannon may have come up the idea that it would be useful to replace symbols in a message with codes of variable byte-length, assigning the shortest length codes to the most frequently used symbols, but it was Huffman who - through considerable grinding effort plus a flash of serendipity - came up with the algorithm that does it most efficiently.
-Alan
I think Huffman was just being humble, hence he did not use his name for the coding.
Re your Chinese food comment: in US asking where to eat American food would be a valid question, since "American" is one of restaurant categories. Check any business/restaurant locator (superpages.com f.ex.).
The purpose of life is to find the purpose of life.
Now let's fold Space itself!
I think Huffman was just being humble, hence he did not use his name for the coding.
I agree. I took a class from G. Blakely, author of the "Blakely secret-sharing scheme", which is what he called it in class. (Yes, I know, Shamir's idea is more well known, and Blakely definitely gave it props in his class.) That's not to say that Blakely wasn't humble, but rather to say that calling something after yourself isn't that weird, especially if that's what it's commonly called.
and it does
Nothing in the world is more dangerous than sincere ignorance and conscientious stupidity.