Description

2. Part I. Carpenter\'s Rule Questionwith Erik Demaine and G

Transcripts

Decorations, Flowers, and Kneser-Poulsen Bob Connelly Cornell University (going to University of Cambridge)

Part I Carpenter\'s Rule Question with Erik Demaine and Günter Rote 2000

Carpenter\'s control result Given a shut polygon in the plane that does not converge itself there is a nonstop movement that moves it in a manner that no edges cross and every one of the edges remain a similar length and the last arrangement is arched.

Carpenter\'s lead result Given a shut polygon in the plane that does not meet itself there is a nonstop movement that moves it in a manner that no edges cross and every one of the edges remain a similar length and the last design is raised .

Two cases The opening outcome applies to the instance of an open chain or a basic shut chain.

Moral of this story The polygon opens by extending . At the end of the day, every combine of vertices of the polygon, that can possibly get further separated amid the movement, do. Growing polygons can\'t have self-crossing points. The best way to stop is the point at which it gets to be distinctly curved.

Methods (CDR 2000) Canonical extension which differs constantly as the information is fluctuated. (I. Streinu 2000) Series of one-parameter far reaching movements utilizing pseudo-triangulations. (J. Canterella, E. Demaine, H. Iben, J. O\'brien 2004) Energy driven opening, yet not really far reaching.

Part II Adornments with E. Demaine, M. Demaine, S. Fekete, S. Langerman, J. Mitchell, A. Ribo Mor, G. Repetition.

What about a chain of shapes other than line portions? A few shapes can bolt keeping them from opening, for example, the accompanying:

Is there a fascinating class of shapes that do open? Join non-covering decorations to every line fragment. As the chain opens, convey the decorations along. How brave would you be able to be in permitting embellishments so they don\'t catch each other? The accompanying is a to some degree bashful case.

Slender Adornments We recommend that every decoration be a locale limited by a bend on every side of the line portion with the end goal that the separation along the bend to every end purpose of the line fragment be (pitifully) monotone. Call these slim embellishments .

Symmetric Slender Adornments An embellishment joined to a line fragment is symmetric in the event that it is symmetric about the line.

Adornment Result Theorem (CDDFLMRR): Any shut or open polygonal chain with non-covering thin embellishments piece-wise easily opens without covering to a design with the center chain raised.

Adornments won\'t not grow Remark: Even when the basic chain is extending, a few purposes of the enhancement may get nearer together. The red focuses grow, however the blue focuses contract in the Figure.

Part III Kneser-Poulsen inquiries with K. Bezdek

Unions of round plates Suppose that we have a union of roundabout circles, and we revise the plates so that their focuses grow.

Unions of round plates Suppose that we have a union of roundabout circles, and we rework the circles so that their focuses grow.

Kneser-Poulsen Conjecture (Kneser 1955, Poulsen 1954): The volume/region of the union (or crossing point) of a limited accumulation of plates in E d does not get littler (or bigger) when they are revamped with the end goal that every match of focuses p does not get littler.

History Kirszbraun (1934): If a limited number of circles have an unfilled crossing point, and their focuses p are extended to q , then the new arrangement of plates with focuses at the setup q and similar radii likewise have a vacant convergence. (In any E d .) B. Bollobás (1968): K-P for the plane for all radii equivalent, and q a consistent development of p . M. Gromov (1987): K-P for any measurement d, however just for d+1 plates. V. Capoyleas and J. Pach (1991): K-P for any measurement d, however just for d+1 plates. H. Edelsbrunner (1995): Introduces Voronoi locales to help in the estimation.

History (proceeded with) M. Bern and A. Sahai (1998): K-P for the plane for any radii, and q is a constant development of p enlivened by Edelsbrunner\'s comments. B. Csikós (1995): K-P for all measurements, any radii, yet just when q is a persistent extension of p. ( Inspired by Bern and Sahai?) K. Bezdek and R. Connelly (2001): The K-P guess is right in the plane when the design of focuses q is any discrete development of p . (Roused by all the above.)

Flowers Gordon and Meyer (1995) and Gromov (1987) recommended a K-P guess for mixes of unions and crossing points of balls. For instance for the expression, (B 1 Ç B 2 ) U (B 3 Ç B 4 ) U (B 5 Ç B 6 ) U B 7 Centers of the circles are just permitted to move together or separated as an element of their position in the expression. This is appeared with strong or dashed lines in the figure. Range monotonicity takes after from Csikós\' equation as well as our outcomes.

Symmetric slim decorations are blossoms Symmetric thin enhancements are the (perhaps interminable) union U x [D a (x) Ç D b (x)], where the circles D a (x) and D b (x) are focused at the two end focuses an and b individually, and x, on the limit of every plate, keeps running over the limit of the embellishment.

Intersecting thin embellishments Two slim enhancements converge if and just if four roundabout circles comparing to the four end purposes of the two line fragments meet.

Adorned chains again Theorem: If a chain, which has non-covering symmetric thin embellishments joined, is extended (discretely) to another chain, the relating decorations are still non-covering. Confirmation: If the extended chain has covering decorations, somewhere in the range of 4 round plates about the end focuses must cross, while the first circles did not. This negates Kirszbraun\'s Theorem.

Discrete non-symmetric decorations can cross If the slim enhancement is not symmetric, a discrete extension can make convergences.

Continuous developments Theorem (CDDFLMRR): If slim, non-covering, yet not really symmetric, enhancements are appended to a chain, and the extension is ceaseless, then the embellishments on the extended chain won\'t cover. Verification: For every match of decorations hold up until the symmetric other half can be appended disjointly and apply the discrete outcome. It is sufficient to take a gander at the two sets of converging plates on every side.

Some cases

Extra blooms If symmetric slim embellishments do cross, then under a discrete extension of plane, the range of the union does not diminish. (C-B connected to blossoms.) This works in any measurement if the expected extension is consistent (Csikós connected to blooms).

Best conceivable? There are cases of enhancements to chains that are somewhat bigger than thin, and the chains can\'t open in any capacity without the decorations impacting.