Origami can turn a sheet of paper into complex three-dimensional shapes, and similar folding techniques produce structures mechanisms. To demonstrate the application these to fabrication machines, we developed crawling robot that folds itself. The starts as flat with embedded electronics, transforms autonomously functional machine. accomplish this, shape-memory composites fold themselves along hinges. We used recreate fundamental folded patterns, derived from computational origami, be...

Programmable matter is a material whose properties can be programmed to achieve specific shapes or stiffnesses upon command. This concept requires constituent elements interact and rearrange intelligently in order meet the goal. paper considers achieving programmable sheets that form themselves different autonomously by folding. Past approaches creating transforming machines have been limited small feature sizes, large number of components, associated complexity communication among units. We...

Origami-inspired manufacturing can produce complex structures and machines by folding two-dimensional composites into three-dimensional structures. This fabrication technique is potentially less expensive, faster, easier to transport than more traditional machining methods, including 3-D printing. Self-folding enhances this method minimizing the manual labor involved in folding, allowing for geometries enabling remote or automated assembly. paper demonstrates a novel of self-folding hinges...

We introduce a new framework for designing fixed-parameter algorithms with subexponential running time---2 O(√k) n O(1) . Our results apply to broad family of graph problems, called bidimensional problems , which includes many domination and such as vertex cover, feedback set, minimum maximal matching, dominating edge disk dimension, others restricted bounded-genus graphs (phrased bipartite-graph problem ). Furthermore, it is fairly straightforward prove that bidimensional. In particular,...

The localization problem is to determine an assignment of coordinates nodes in a wireless ad-hoc or sensor network that consistent with measured pairwise node distances. Most previously proposed solutions this assume the can obtain distances other nearby using some ranging technology. However, for variety reasons include obstructions and lack reliable omnidirectional ranging, distance information hard practice. Even when between are known, there may not be enough solve uniquely. This paper...

Our newly developing theory of bidimensional graph problems provides general techniques for designing efficient fixed-parameter algorithms and approximation NPhard in broad classes graphs.This applies to that are the sense (1) solution value k x grid (and similar graphs) grows with k, typically as Q(k 2 ), (2) goes down when contracting edges optionally deleting edges.Examples such include feedback vertex set, cover, minimum maximal matching, face a series vertexremoval parameters,...

At the core of seminal graph minor theory Robertson and Seymour is a powerful structural theorem capturing structure graphs excluding fixed minor. This result used throughout algorithms, but existential. We develop polynomial-time algorithm using topological to decompose into guaranteed by theorem: clique-sum pieces almost-embeddable bounded-genus surfaces. has many applications. In particular we show applications developing approximation including 2-approximation coloring, constant-factor...

We develop a new technique for proving cell-probe lower bounds on dynamic data structures. This enables us to prove an amortized randomized $\Omega(\lg n)$ bound per operation several structural problems n elements, including partial sums, connectivity among disjoint paths (or forest or graph), and other graph (by simple reductions). Such breaks long-standing barrier of n\,/\lg\lg any language membership problem. It also establishes the optimality existing structures, such as Sleator...

We consider the problem of deploying or repairing a sensor network to guarantee specified level multi-path connectivity (k-connectivity) between all nodes. Such simultaneously provides fault tolerance against node failures and high capacity through routing. design analyze first algorithms that place an almost-minimum number additional sensors augment existing into k-connected network, for any desired parameter k. Our have provable guarantees on quality solution. Specifically, we prove is...

The edit distance between two ordered rooted trees with vertex labels is the minimum cost of transforming one tree into other by a sequence elementary operations consisting deleting and relabeling existing nodes, as well inserting new nodes. In this article, we present worst-case O ( n 3 )-time algorithm for problem when have size , improving previous best log algorithm. Our result requires novel adaptive strategy deciding how dynamic program divides subproblems, together deeper...

There is a fundamental connection between the notions of game and computation. At its most basic level, this implied by any complexity result, but deeper than this. One example concept alternating nondeterminism, which intimately connected with two-player games. In first half thesis. I develop idea as computation to greater degree has been done previously. present general family games, called Constraint Logic, both mathematically simple ideally suited for reductions many actual board A...

We present dynamic search-tree data structures that perform well in the setting of a hierarchical memory (including various levels cache, disk, etc.), but do not depend on number levels, block sizes and blocks at each level, or relative speeds access. In particular between any pair hierarchy, where transfers are done size B, our match optimal search bound /spl Theta/(log/sub B/ N) transfers. This is also achieved by classic B-tree structure, only when B known, which practice requires careful...