Physical Sciences and Mathematics Commons^™

Angular Rigidity In 3d: Combinatorial Characterizations And Algorithms, Audrey Lee-St.John, Ileana Streinu

Computer Science: Faculty Publications

Constraint-based CAD software, used by engineers to design sophisticated mechanical systems, relies on a wide range of geometrical constraints. In this paper we focus on one special case: angular constraints in 3D. We give a complete combinatorial characterization for generic minimal rigidity in two new models: line- plane-and-angle and body-and-angle structures. As an immediate consequence, we obtain efficient algorithms for analyzing angular rigidity.

Press The Cancel Button! A Performance Evaluation Of Scalable In-Network Data Aggregation, Jamie Macbeth, Majid Sarrafzadeh

Computer Science: Faculty Publications

We perform real-world tests of the performance of medium access control protocol schemes for scalable data aggregation in sensor networks. Specifically, we evaluate the performance of a Listen-and-Suppress Carrier Sense Multiple Access (LAS-CSMA) scheme on the duplicate-insensitive exemplary monotonic aggregates MAX and MIN. These schemes reduce power consumption, network bandwidth usage and delays by suppressing node packet transmissions that are proven to be unnecessary in the query response. This is possible when nodes listen to the transmissions of other nodes as they respond.

Scalability tests were performed for 8 networks of various sizes, the largest having 24 Crossbow IRIS wireless …

Finding Words In Alphabet Soup: Inference On Freeform Character Recognition For Historical Scripts, Nicholas Howe, Shaolei Feng, R. Manmatha

Computer Science: Faculty Publications

This paper develops word recognition methods for historical handwritten cursive and printed documents. It employs a powerful segmentation-free letter detection method based upon joint boosting with histograms of gradients as features. Efficient inference on an ensemble of hidden Markov models can select the most probable sequence of candidate character detections to recognize complete words in ambiguous handwritten text, drawing on character n" role="presentation" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline-block; line-height: normal; font-size: 16.2px; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;">n-gram and physical …

Sparse Hypergraphs And Pebble Game Algorithms, Ileana Streinu, Louis Theran

Computer Science: Faculty Publications

A hypergraph G=(V,E) is (k,ℓ)-sparse if no subset V^′⊂V spans more than k|V^′|−ℓ hyperedges. We characterize (k,ℓ)-sparse hypergraphs in terms of graph theoretic, matroidal and algorithmic properties. We extend several well-known theorems of Haas, Lovász, Nash-Williams, Tutte, and White and Whiteley, linking arboricity of graphs to certain counts on the number of edges. We also address the problem of finding lower-dimensional representations of sparse hypergraphs, and identify a critical behavior in terms of the sparsity parameters k and ℓ. Our constructions extend the pebble games of Lee and Streinu [A. Lee, I. Streinu, Pebble game algorithms …

Link Scheduling For Scalable Data Aggregation, Jamie Macbeth, Majid Sarrafzadeh

Computer Science: Faculty Publications

We explore the link scheduling optimization problem in the context of scalable in-network data aggregation, extending results for broadcast networks to routing in general networks. The primary vehicle for resource preservation is transmission suppression. For certain types of queries, nodes can avoid transmitting records if they can locally infer that their data is not needed to execute the query. We introduce a novel protocol paradigm for duplicate-insensitive exemplary monotonic (e.g. MIN and MAX) data aggregation queries. Performance of query execution in these networks is measured through collective expected number of transmissions in the network, and is linked to the minimum …

Linear Reconfiguration Of Cube-Style Modular Robots, Greg Aloupis, Sébastien Collette, Mirela Damian, Erik D. Demaine, Robin Flatland, Stefan Langerman, Joseph O'Rourke, Suneeta Ramaswami, Vera Sacristán, Stefanie Wuhrer

Computer Science: Faculty Publications

In this paper we propose a novel algorithm that, given a source robot S and a target robot T, reconfigures S into T. Both S and T are robots composed of n atoms arranged in 2×2×2 meta-modules. The reconfiguration involves a total of O(n) atomic operations (expand, contract, attach, detach) and is performed in O(n) parallel steps. This improves on previous reconfiguration algorithms [D. Rus, M. Vona, Crystalline robots: Self-reconfiguration with compressible unit modules, Autonomous Robots 10 (1) (2001) 107-124; S. Vassilvitskii, M. Yim, J. Suh, A complete, local and parallel reconfiguration algorithm for cube style modular robots, in: Proc. …

Some Properties Of Yao Y4 Subgraphs, Joseph O'Rourke

Computer Science: Faculty Publications

The Yao graph for k = 4, Y₄, is naturally partitioned into four subgraphs, one per quadrant. We show that the subgraphs for one quadrant differ from the subgraphs for two adjacent quadrants in three properties: planarity, connectedness, and whether the directed graphs are spanners.

Sparsity-Certifying Graph Decompositions, Ileana Streinu, Louis Theran

Computer Science: Faculty Publications

We describe a new algorithm, the (k, ℓ)-pebble game with colors, and use it to obtain a characterization of the family of (k, ℓ)-sparse graphs and algorithmic solutions to a family of problems concerning tree decompositions of graphs. Special instances of sparse graphs appear in rigidity theory and have received increased attention in recent years. In particular, our colored pebbles generalize and strengthen the previous results of Lee and Streinu [12] and give a new proof of the Tutte-Nash-Williams characterization of arboricity. We also present a new decomposition that certifies sparsity based on the (k …

Comparing The Use Of Tangible And Graphical Programming Languages For Informal Science Education, Michael S. Horn, Erin T. Solovey, R. Jordan Crouser, Robert J.K. Jacob

Computer Science: Faculty Publications

Much of the work done in the field of tangible interaction has focused on creating tools for learning; however, in many cases, little evidence has been provided that tangible interfaces offer educational benefits compared to more conventional interaction techniques. In this paper, we present a study comparing the use of a tangible and a graphical interface as part of an interactive computer programming and robotics exhibit that we designed for the Boston Museum of Science. In this study, we have collected observations of 260 museum visitors and conducted interviews with 13 family groups. Our results show that visitors found the …

Enumeration Of Optimal Pin-Jointed Bistable Compliant Mechanisms With Non-Crossing Members, M. Ohsaki, N. Katoh, T. Kinoshita, S. Tanigawa, D. Avis, I. Streinu

Computer Science: Faculty Publications

An optimization approach is presented for enumerating pin-jointed bistable compliant mechanisms. In the first stage, the statically determinate trusses with non-crossing members containing a given set of nodes and some pre-defined members are regarded as minimally rigid framework or a Laman framework, and are enumerated without repetitions by the graph enumeration algorithm. In the second stage, the nodal locations and the cross-sectional areas are optimized under mechanical constraints, where the snapthrough behavior is extensively utilized to produce a pin-jointed bistable compliant mechanism. In the numerical examples, many bistable compliant mechanisms are generated to show the effectiveness of the proposed method. …