Computer Sciences Commons^™

The Yao Graph Y6 Is A Spanner, Joseph O'Rourke

Computer Science: Faculty Publications

We prove that Y₆ is a spanner. Y₆ is the Yao graph on a set of planar points, which has an edge from each point x to a closest point y within each of the six angular cones of 60^◦ surrounding x .

Realistic Reconfiguration Of Crystalline (And Telecube) Robots, Greg Aloupis, Sébastien Collette, Mirela Damian, Erik D. Demaine, Dania El-Khechen, Robin Flatland, Stefan Langerman, Joseph O'Rourke, Val Pinciu, Suneeta Ramaswami, Vera Sacristán, Stefanie Wuhrer

Computer Science: Faculty Publications

In this paper we propose novel algorithms for reconfiguring modular robots that are composed of n atoms. Each atom has the shape of a unit cube and can expand/contract each face by half a unit, as well as attach to or detach from faces of neighboring atoms. For universal reconfiguration, atoms must be arranged in 2×2×2 modules. We respect certain physical constraints: each atom reaches at most unit velocity and (via expansion) can displace at most one other atom. We require that one of the atoms can store a map of the target configuration. Our algorithms involve a total of …

Highway Hull Revisited, Greg Aloupis, Jean Cardinal, Sébastien Collette, Ferran Hurtado, Stefan Langerman, Joseph O'Rourke, Belén Palop

Computer Science: Faculty Publications

A highway H is a line in the plane on which one can travel at a greater speed than in the remaining plane. One can choose to enter and exit H at any point. The highway time distance between a pair of points is the minimum time required to move from one point to the other, with optional use of H. The highway hull H(S,H) of a point set S is the minimal set containing S as well as the shortest paths between all pairs of points in H(S,H), using the highway time distance. We provide a Θ(nlogn) worst-case …

A Curriculum Unit On Programming And Robotics, Marina U. Bers, Louise Flannery, Elizabeth Kazakoff, R. Jordan Crouser

Computer Science: Faculty Publications

The Tangible Kindergarten project studies how, when given age-appropriate tools, young children can actively engage in computer programming and robotics in a way that is consistent with developmentally appropriate practice. This research project explores the creation of novel human computer interaction techniques to support learning with technology in early elementary school, with a focus on kindergarten. Since many modern graphical user interfaces are not designed with the developmental needs of such young learners in mind, they are generally ill-suited for use in early elementary school classrooms, especially for computer programming activities. To overcome this problem, this research project has created …

Morphing Of Triangular Meshes In Shape Space, Stefanie Wuhrer, Prosenjit Bose, Chang Shu, Joseph O'Rourke, Alan Brunton

Computer Science: Faculty Publications

We present a novel approach to morph between two isometric poses of the same non-rigid object given as triangular meshes. We model the morphs as linear interpolations in a suitable shape space S. For triangulated 3D polygons, we prove that interpolating linearly in this shape space corresponds to the most isometric morph in R³ . We then extend this shape space to arbitrary triangulations in 3D using a heuristic approach and show the practical use of the approach using experiments. Furthermore, we discuss a modified shape space that is useful for isometric skeleton morphing. All of the newly presented …

How Far Can You Reach?, Ciprian Borcea, Ileana Streinu

Computer Science: Faculty Publications

The problem of computing the maximum reach configurations of a 3D revolute-jointed manipulator is a long-standing open problem in robotics. In this paper we present an optimal algorithmic solution for orthogonal polygonal chains. This appears as a special case of a larger family, fully characterized here by a technical condition. Until now, in spite of the practical importance of the problem, only numerical optimization heuristics were available, with no guarantee of obtaining the global maximum. In fact, the problem was not even known to be computationally solvable, and in practice, the numerical heuristics were applicable only to small problem sizes. …

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 …

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.

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 …

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. …

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 …

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.

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. …

Aesthetic Journeys, Johanna Brewer, Scott Mainwaring, Paul Dourish

Computer Science: Faculty Publications

Researchers and designers are increasingly creating technologies intended to support urban mobility. However, the question of what mobility is remains largely under-examined. In this paper we will use the notion of aesthetic journeys to reconsider the relationship between urban spaces, people and technologies. Fieldwork on the Orange County bus system and in the London Underground leads to a discussion of how we might begin to design for multiple mobilities.

Analyzing Rigidity With Pebble Games, Audrey Lee, Ileana Streinu, Louis Theran

Computer Science: Faculty Publications

How many pair-wise distances must be prescribed between an unknown set of points, and how should they be distributed, to determine only a discrete set of possible solutions? These questions, and related generalizations, are central in a variety of applications. Combinatorial rigidity shows that in two-dimensions one can get the answer, generically, via an efficiently testable sparse graph property. We present a video and a web site illustrating algorithmic results for a variety of rigidity-related problems, as well as abstract generalizations. Our accompanying interactive software is based on a comprehensive implementation of the pebble game paradigm.

Combinatorial Genericity And Minimal Rigidity, Ileana Streinu, Louis Theran

Computer Science: Faculty Publications

A well studied geometric problem, with applications ranging from molecular structure determination to sensor networks, asks for the reconstruction of a set P of n unknown points from a finite set of pairwise distances (up to Euclidean isometries). We are concerned here with a related problem: which sets of distances are minimal with the property that they allow for the reconstruction of P, up to a finite set of possibilities? In the planar case, the answer is known generically via the landmark Maxwell-Laman Theorem from Rigidity Theory, and it leads to a combinatorial answer: the underlying structure of such a …

Unfolding Convex Polyhedra Via Quasigeodesic Star Unfoldings, Jin-Ichi Itoh, Joseph O'Rourke, Costin Vîlcu

Computer Science: Faculty Publications

We extend the notion of a star unfolding to be based on a simple quasigeodesic loop Q rather than on a point. This gives a new general method to unfold the surface of any convex polyhedron P to a simple, planar polygon: shortest paths from all vertices of P to Q are cut, and all but one segment of Q is cut.

Draining A Polygon-Or-Rolling A Ball Out Of A Polygon, Greg Aloupis, Jean Cardinal, Sébastien Collette, Ferran Hurtado, Stefan Langerman, Joseph O'Rourke

Computer Science: Faculty Publications

We introduce the problem of draining water (or balls representing water drops) out of a punctured polygon (or a polyhedron) by rotating the shape. For 2D polygons, we obtain combinatorial bounds on the number of holes needed, both for arbitrary polygons and for special classes of polygons. We detail an O(n2 log n) algorithm that finds the minimum number of holes needed for a given polygon, and argue that the complexity remains polynomial for polyhedra in 3D. We make a start at characterizing the 1-drainable shapes, those that only need one hole.

Isometric Morphing Of Triangular Meshes, Prosenjit Bose, Joseph O'Rourke, Chang Shu, Stefanie Wuhrer

Computer Science: Faculty Publications

We present a novel approach to morph between two isometric poses of the same non-rigid object given as triangular meshes. We model the morphs as linear interpolations in a suitable shape space S. For triangulated 3D polygons, we prove that interpolating linearly in this shape space corresponds to the most isometric morph in R3. We extend this shape space to arbitrary triangulations in 3D using a heuristic approach.

A Pumping Lemma For Homometric Rhythms, Joseph O'Rourke, Perouz Taslakian, Godfried Toussaint

Computer Science: Faculty Publications

Homometric rhythms (chords) are those with the same histogram or multiset of intervals (distances). The purpose of this note is threefold. First, to point out the potential importance of isospectral vertices in a pair of homometric rhythms. Second, to establish a method ("pumping") for generating an infinite sequence of homometric rhythms that include isospectral vertices. And finally, to introduce the notion of polyphonic homometric rhythms, which apparently have not been previously explored.

Scalable Medium Access Control For In-Network Data Aggregation, Jamie Macbeth, Majid Sarrafzadeh

Computer Science: Faculty Publications

We present conflict-free and contention-based medium access control (MAC) protocols designed for resource-aware data collection in sensor networks. We are interested in the performance of these schemes when used in in-network data aggregation systems. We introduce a Listen-and-Suppress (LAS) MAC protocol paradigm which can conserve network and node resources and cut delays through the interaction between the constituent nodes. In LAS-TDMA and LASCSMA, nodes listen to the channel and suppress their transmissions and sleep if their data is not needed. Under these conditions, we compare conflict-free scheduling and random scheduling in a general setting along several performance metrics. We find …

Unfolding Manhattan Towers, Mirela Damian, Robin Flatland, Joseph O'Rourke

Computer Science: Faculty Publications

We provide an algorithm for unfolding the surface of any orthogonal polyhedron that falls into a particular shape class we call Manhattan Towers, to a nonoverlapping planar orthogonal polygon. The algorithm cuts along edges of a 4×5×1 refinement of the vertex grid.

Evaluating Recognition-Based Motion Capture On Humaneva Ii Test Data, Nicholas Howe

Computer Science: Faculty Publications

The advent of the HumanEva standardized motion capture data sets has enabled quantitative evaluation of motion capture algorithms on comparable terms. This paper measures the performance of an existing monocular recognition-based pose recovery algorithm on select HumanEva data, including all the HumanEva II clips. The method uses a physically-motivated Markov process to connect adajacent frames and achieve a 3D relative mean error of 8.9 cm per joint, better than recently reported results. It further investigates factors contributing to the error, and finds that research into better pose retrieval methods offers promise for improvement of this technique and those related to …

Cauchy’S Arm Lemma On A Growing Sphere, Zachary Abel, David Charlton, Sébastien Collette, Erik D. Demaine, Martin L. Demaine, Stefan Langerman, Joseph O'Rourke, Val Pinciu, Godfried Toussaint

Computer Science: Faculty Publications

We propose a variant of Cauchy's Lemma, proving that when a convex chain on one sphere is redrawn (with the same lengths and angles) on a larger sphere, the distance between its endpoints increases. The main focus of this work is a comparison of three alternate proofs, to show the links between Toponogov's Comparison Theorem, Legendre's Theorem and Cauchy's Arm Lemma.

Grid Vertex-Unfolding Orthogonal Polyhedra, Mirela Damian

Computer Science: Faculty Publications

No abstract provided.

A Class Of Convex Polyhedra With Few Edge Unfoldings, Alex Benton, Joseph O'Rourke

Computer Science: Faculty Publications

We construct a sequence of convex polyhedra on n vertices with the property that, as n -> infinity, the fraction of its edge unfoldings that avoid overlap approaches 0, and so the fraction that overlap approaches 1. Nevertheless, each does have (several) nonoverlapping edge unfoldings.

Automated Journeys, Arianna Bassoli, Johanna Brewer, Alex Taylor

Computer Science: Faculty Publications

Computing technology now pervades those moments of our day when we move through our cities. Mobile phones, music players, vending machines, contact-less payment systems and RFID-enabled turnstiles are de rigueur on our daily journeys. This workshop aims to examine these augmented journeys, to reflect on the public, semi-public and private technologies available to us in them, and to speculate on what innovations might be to come. Taking as our starting point cities such as Seoul, we aim to take seriously the developments in mobile technology as well as the advancements in autonomous machinery and how these mesh with our urban …

A Hidden Markov Model For Alphabet-Soup Word Recognition, Shaolei Feng, Nicholas Howe, R. Manmatha

Computer Science: Faculty Publications

Recent work on the “alphabet soup” paradigm has demonstrated effective segmentation-free character-based recognition of cursive handwritten historical text documents. The approach first uses a joint boosting technique to detect potential characters - the alphabet soup. A second stage uses a dynamic programming algorithm to recover the correct sequence of characters. Despite experimental success, the ad hoc dynamic programming method previously lacked theoretical justification. This paper puts the method on a sounder footing by recasting the dynamic programming as inference on an ensemble of hidden Markov models (HMMs). Although some work has questioned the use of score outputs from classifiers like …

On Corners Of Objects Built From Parallelepiped Bricks, Mirela Damian, Joseph O'Rourke

Computer Science: Faculty Publications

We investigate a question initiated in the work of Sibley and Wagon, who proved that 3 colors suffice to color any collection of 2D parallelograms glued edge-to-edge. Their proof relied on the existence of an "elbow" parallelogram. We explore the existence of analogous "corner" parallelepipeds in 3D objects. Our results are twofold. First, we refine the 2D proof to render information on the number and location of the 2D elbows. Second, we prove that not all of the 2D refinements extend to 3D.