Math II (Несколько текстов для зачёта)

UNLOCKING PUZZLING POLYGONS

Source: Science News, 09/23/2000, Vol. 158 Issue 13, p200, 2p, 6c, 1bw

Author(s): Peterson, Ivars

Proof settles a wickedly prickly question about unfurling crinkly shapes

Polygons come in all sorts of shapes: triangles, squares, hexagons, stars, and a host of other straight-edged forms.

Think of a polygon as a chain of rigid rods connected to each other in two dimensions with flexible joints. Start with any configuration, no matter how complex and intricately indented, or crinkly. Can you always find a sequence of moves that removes the indentations-unfurling the polygon into what mathematicians describe as a convex shape, like a triangle-without ever letting the rods cross each other?

That's not as easy to do as it may sound. Imagine, for example, the outline of a set of fearsome jaws with interlocking teeth.

Computational geometers and assorted others puzzled over this problem for more than a decade, ever since it came to the attention of robotics engineers who were trying to make a robot arm move from place to place. In recent years, the geometric speculation turned into a sort of game. Someone would propose a complicated configuration that appears to stay locked, and other enthusiasts would spend hours, even weeks, looking for the key to opening it up.

Most of those who tackled the polygon problem believed that someone ultimately would come up with a polygon that could not be unfurled, at least not in two dimensions.

No one ever came up with a stumper, however. Every tricky polygonal configuration anyone ever proposed was eventually cracked. "In a few cases, it took several months to find the answer," says Erik D. Demaine, a 19-year-old computer science graduate student at the University of Waterloo in Ontario.

Now, the question is finally settled. Demaine, Robert Connelly of Cornell University, and GUnter Rote of the Free University of Berlin have proved that any polygon can be uncrinkled in two dimensions without any sides crossing each other during the unfolding.

Pulling apart this jaw-shaped polygon (blue) without allowing any segments to cross proved to be a tough exercise in computational geometry.

The researchers announced their proof last June in Minneapolis at a Society for Industrial and Applied Mathematics conference on discrete mathematics.

Related geometric problems have practical applications, such as checking the range of movements of a jointed, robotic arm, designing a complicated antenna that opens up properly in space, or studying how a protein strand folds into a compact blob. At the moment, however, the new result appears to have no obvious applications.

The puzzle's real appeal has been aesthetic rather than practical. "It's simply a natural question to ask and a beautiful problem," insists computer scientist Joseph O'Rourke of Smith College in Northampton, Mass.

Over the years, studies of robotic arm movements have suggested purely mathematical questions about morphing one geometric shape into another. One important group of problems concerns chains made up of line segments. Such chains may be closed, like a polygon, or open-ended, like a segmented arc. Lines can also be linked to form a branched structure, termed a tree, where jointed segments sprout from a common vertex.

Suppose, for example, that a tree has eight chains emanating from a central point. Suppose further that each of these chains is made

up of three segments folded so that the entire tree looks like a stylized flower with eight petals.

Segment lengths determine whether it's possible to unfurl this eight-petal tree configuration without allowing segments to cross.

In 1998, Sue Whitesides of McGill University in Montreal and a large team of collaborators established that for certain segment lengths, the petals can't be straightened out without letting segments cross. Opening up one petal necessarily impinges on others.

Unlike a two- dimensional chain, this knotted, three-dimensional "knitting needle" chain in space can't be untangled. chers also found examples of three-dimensional chains, both open and closed, that are locked, or impossible to unfold. On the other hand, O'Rourke and Smith College colleague Roxana Cocan proved last year that in the roominess of four- or higher-dimensional space, one can straighten out any open chain and uncrinkle any polygon.

This polygon can be unlocked. The tree on which its shape is based can't be when its branches are close together. left the two-dimensional case as the major unsolved problem," O'Rourke says.

Last year in July, Demaine, Rote, and Connelly all happened to be at a geometry conference in Ascona, Switzerland. In considering the polygon puzzle,Rote suggested that uncrinkling polygons had to require some sort of expansion-as if a balloon were inflating inside the polygon and forcing

its sides outward.

A complex folded paper structure based on the hyperbolic paraboloid presents new geometric challenges.

"His suggestion was crucial, though we didn't realize why it was so helpful until later," Demaine remarks.

The trio did observe, however, that if they could somehow find a sequence of movements in which the distance between any pair of joints stayed the same or increased, then the segments could never cross. So, the problem could be converted from one about avoiding intersections into one about expanding movements.

The sequence of steps required to unlock the jaws configuration. time Demaine, Rote, and Connelly met again in November, this time in Budapest, Connelly had realized that the notion of expansion could be studied in the context of his own field of expertise: the rigidity of structures. With this concept, the team could look at polygons as frameworks of rods and invisible struts between nonadjacent joints, where rods have to stay the same size but struts can increase in length. The researchers could then consider stress patterns within that structure.

"This allowed us to apply some beautiful theorems in rigidity theory," Demaine notes.

A proof that flat polygonal chains can't lock followed from that insight. Along the way, Demaine, Rote, and Connelly also established that any open chain can always be straightened.

The big surprise is not the proof itself,

O'Rourke comments, but the conceptual breakthrough that the opening move in any successful uncrinkling process has to be one in which each joint moves apart or stays the same distance away from every other joint.

Last summer, Demaine, Connelly, and O'Rourke added another element to the original argument. They showed that the area inside an uncrinkling polygon must increase. "This seems almost obvious," Connelly notes, "but the proof that we have is not completely trivial."

Now that the two-dimensional case is solved, Demaine is tangling with other fierce geometric beasts. An origami enthusiast, he's tamed the hyperbolic paraboloid. Demaine developed instructions for folding and gluing this classic saddle shape into complex paper hats and starbursts.

A complex folded paper structure based on the hyperbolic paraboloid presents new geometric challenges.

"His suggestion was crucial, though we didn't realize why it was so helpful until later," Demaine remarks.

The trio did observe, however, that if they could somehow find a sequence of movements in which the distance between any pair of joints stayed the same or increased, then the segments could never cross. So, the problem could be converted from one about avoiding intersections into one about expanding movements.

The sequence of steps required to unlock the jaws configuration. time Demaine, Rote, and Connelly met again in November, this time in Budapest, Connelly had realized that the notion of expansion could be studied in the context of his own field of expertise: the rigidity of structures. With this concept, the team could look at polygons as frameworks of rods and invisible struts between nonadjacent joints, where rods have to stay the same size but struts can increase in length. The researchers could then consider stress patterns within that structure.

"This allowed us to apply some beautiful theorems in rigidity theory," Demaine notes.

A proof that flat polygonal chains can't lock followed from that insight. Along the way, Demaine, Rote, and Connelly also established that any open chain can always be straightened.

The big surprise is not the proof itself,

O'Rourke comments, but the conceptual breakthrough that the opening move in any successful uncrinkling process has to be one in which each joint moves apart or stays the same distance away from every other joint.

Last summer, Demaine, Connelly, and O'Rourke added another element to the original argument. They showed that the area inside an uncrinkling polygon must increase. "This seems almost obvious," Connelly notes, "but the proof that we have is not completely trivial."

Now that the two-dimensional case is solved, Demaine is tangling with other fierce geometric beasts. An origami enthusiast, he's tamed the hyperbolic paraboloid. Demaine developed instructions for folding and gluing this classic saddle shape into complex paper hats and starbursts.

MAPPING GALACTIC FOAM

Source: Smithsonian, Jun2001, Vol. 33 Issue 3, p48, 6p, 6c

Author(s): Jablow, Valerie

SMITHSONIAN ASTRONOMER MARGARET GELLER PLOTTED THE BUBBLE STRUCTURE OF THE UNIVERSE. NOW SHE'S WORKING TO FIND OUT HOW IT GOT THAT WAY

On a wall of her office Margaret Geller has hung a picture of the stickman-her stickman. It is not large, perhaps a foot on each side. As stickmen go, in fact, this one is just average-or mind-bogglingly huge, depending on how you look at it. It is made up of astronomical structures extending for hundreds of millions of light-years. As most of us will see it, however, it's just this, a cartoon figure outlined by glowing galaxies set against the dark emptiness of space.

For the past 20 years Geller, an astronomer and professor at the Harvard-Smithsonian Center for Astrophysics (CFA) in Cambridge, Massachusetts, has mapped the universe by plotting positions of galaxies. In 1986 the first of her maps, often called the stickman map, was evidence of something few had believed possible: on the largest scale, the universe has a distinct structure. With more plots, it became clear that the stickman was part of a pattern in which "walls" of galaxies surround vast areas with very few galaxies. Suddenly, the stickman map heralded a sea change in human perception.

In public lectures on her work, Geller likens the universe's 3-D pattern to soap bubbles or foam. (Imagine, if you will, a universe comprised of your kitchen sponge, its air pockets delineated by walls of galaxies instead of sponge material). Though astronomers have argued over which-bubbles or foam-is more accurate, Geller hasn't let that bother her. Having convinced the astronomical community with the stickman map, she is set on cracking the universe's next big puzzle: how it got this way.

"One of the great challenges of modern cosmology is to discover what the geometry of the universe really is."

Margaret Geller's clear, ringing voice, a remnant of childhood acting lessons, reaches even the farthest corners of a sloping lecture hall at the Harvard Science Center. Freshmen to seniors, English to economics majors, listen attentively. Their professor has notes, but rarely consults them. For 15 years, she has taught Astronomy 14, "The Universe and Everything," for anyone interested in the space we inhabit. The course is nearly always filled.

Today's lecture, on Einstein's general theory of relativity, at times seems far afield from Geller's mapping of the universe. She rolls a small metal ball across a suspended rubber mat. By pressing on the mat, she shows how changing the shape of space (the rubber mat) determines how the metal ball moves. Gravity, we learn, is not simply a force, but geometry--the heart of her quest.

"My father was a crystallographer," explains Geller in her CfA office half a mile from Harvard Yard. "He worked on the relationship between the arrangement of atoms in solids and their properties. He showed me the relation between geometry and nature, and I have always been fascinated with it. So it's no accident that I would do projects like these maps."

Now 53, the crystallographer's daughter is busy planning her next act, a map of galaxies seven billion light-years away. The idea is not to chart the nearby, current universe. The stickman map did that--albeit for only a tiny slice of the sky. The goal this time is to discern meaning from galactic geometry over time. Only great distances allow such time travel, for the farther out you look, the farther back in time you go. Andromeda, for instance, the closest large galaxy to our own Milky Way, is more than two million light-years away. Light generated by it appears two million years afterward in our telescopes. Geller's new survey will look deep into space at a seven-billion-year-old universe. About half the universe's age, that region should allow Geller to chart geometric changes over time by comparison with the newer universe closer by.

The stickman map indicated that the universe has distinct patterns, shown here by galaxies (dots) lining vast dark areas. Previously, only smaller portions of the universe had been mapped, revealing few patterns.

To illustrate, Geller pulls a physics book off shelves opposite her desk. She flips to a picture of the stickman. On the next page is another map, showing undifferentiated blotches and blobs. Created from measurements of background radiation remaining from the big bang by NASA's COBE (Cosmic Background Explorer) satellite, this map is our best picture of the very early universe, just 200,000 years after it was formed. Geller cradles the book. "The idea is that the COBE map shows that there was very little structure, and the stickman shows that there are very large, very well-defined structures. The contrast between these two specifies the puzzle. I think these are used as a kind of icon for the real problem: How do objects form and evolve in the universe?"

To even start toward an answer for that, you need a big telescope. Geller will use the Smithsonian's newly redesigned one on Mount Hopkins in Arizona. The instrument was initially named the Multiple Mirror Telescope (MMT) because it contained six 72-inch mirrors that acted like one giant mirror 176 inches (or 14 feet, 8 inches) wide. In spring 1999, a single 21-foot mirror replaced the smaller ones. The converted MMT (as it is still called) is now ideally suited for peering at galaxies seven billion light-years away.

But in mapping the universe, it isn't enough just to see galaxies. Their distance must also be understood so that their location in space can be mapped. To do that, astronomers take advantage of an old idea: redshift. In 1929 astronomer Edwin Hubble recognized that galaxies appear to move away from us at speeds proportional to their distances. As a result, the spectrum of light from a galaxy "shifts" toward the red end of the spectrum with the apparent speed, and distance, of that galaxy: the larger the redshift, the greater the galaxy's speed and distance. Thus, to calculate the distance of far-off galaxies, astronomers measure redshift.