Computer Sciences Commons^™

On-Line Distributed Traffic Grooming, R. Jordan Crouser, Brian Rice, Adrian Sampson, Ran Libeskind-Hadas

Computer Science: Faculty Publications

This paper addresses the problem of on-line traffic grooming in WDM paths. Each request consists of a source node, a destination node, and the desired bandwidth for the connection. Connections may be multi-hop, permitting the use of multiple lightpaths. We describe a new distributed on-line algorithm for this problem that is provably wide-sense non-blocking under cer- tain assumptions. Moreover, we use simulations to demonstrate that the algorithm is extremely effective even when some of these assumptions are relaxed.

Edge-Unfolding Nested Polyhedral Bands, Greg Aloupis, Erik D. Demaine, Stefan Langerman, Pat Morin, Joseph O'Rourke, Ileana Streinu, Godfried Toussaint

Computer Science: Faculty Publications

A band is the intersection of the surface of a convex polyhedron with the space between two parallel planes, as long as this space does not contain any vertices of the polyhedron. The intersection of the planes and the polyhedron produces two convex polygons. If one of these polygons contains the other in the projection orthogonal to the parallel planes, then the band is nested. We prove that all nested bands can be unfolded, by cutting along exactly one edge and folding continuously to place all faces of the band into a plane, without intersection. © 2007 Elsevier B.V.

Unfolding Polyhedra Via Cut-Tree Truncation, Alex Benton, Joseph O'Rourke

Computer Science: Faculty Publications

We prove that an infinite class of convex polyhedra, produced by restricted vertex truncations, always unfold without overlap. The class includes the "domes," providing a simpler proof that these unfold without overlap.

The Slider-Pinning Problem, Audrey Lee, Ileana Streinu, Louis Theran

Computer Science: Faculty Publications

A Laman mechanism is a flexible planar bar-and-joint framework with m ≤ 2n-3 edges and exactly k = 2n-m degrees of freedom. The slider-pinning problem is to eliminate all the degrees of freedom of a Laman mechanism, in an optimal fashion, by individually fixing x or y coordinates of vertices. We describe two easy to implement O(n2) time algorithms.

Vertex Pops And Popturns, Greg Aloupis, Brad Ballinger, Prosenjit Bose, Mirela Damian, Erik D. Demaine, Martin L. Demaine, Robin Flatland, Ferran Hurtado, Stefan Langerman, Joseph O'Rourke, Perouz Taslakian, Godfried Toussaint

Computer Science: Faculty Publications

No abstract provided.

Band Unfoldings And Prismatoids: A Counterexample, Joseph O'Rourke

Computer Science: Faculty Publications

This note shows that the hope expressed in [ADL+07]--that the new algorithm for edge-unfolding any polyhedral band without overlap might lead to an algorithm for unfolding any prismatoid without overlap--cannot be realized. A prismatoid is constructed whose sides constitute a nested polyhedral band, with the property that every placement of the prismatoid top face overlaps with the band unfolding.

Unfolding Restricted Convex Caps, Joseph O'Rourke

Computer Science: Faculty Publications

This paper details an algorithm for unfolding a class of convex polyhedra, where each polyhedron in the class consists of a convex cap over a rectangular base, with several restrictions: the cap’s faces are quadrilaterals, with vertices over an underlying integer lattice, and such that the cap convexity is "radially monotone," a type of smoothness constraint. Extensions of Cauchy’s arm lemma are used in the proof of non-overlap.

Epsilon-Unfolding Orthogonal Polyhedra, Mirela Damian, Robin Flatland, Joseph O'Rourke

Computer Science: Faculty Publications

An unfolding of a polyhedron is produced by cutting the surface and flattening to a single, connected, planar piece without overlap (except possibly at boundary points). It is a long unsolved problem to determine whether every polyhedron may be unfolded. Here we prove, via an algorithm, that every orthogonal polyhedron (one whose faces meet at right angles) of genus zero may be unfolded. Our cuts are not necessarily along edges of the polyhedron, but they are always parallel to polyhedron edges. For a polyhedron of n vertices, portions of the unfolding will be rectangular strips which, in the worst case, …

Recognition-Based Motion Capture And The Humaneva Ii Test Data, Nicholas Howe

Computer Science: Faculty Publications

Quantitative comparison of algorithms for human motion capture have been hindered by the lack of standard benchmarks. The development of the HumanEva I & II test sets provides an opportunity to assess the state of the art by evaluating existing methods on the new standardized test videos. This paper presents a comprehensive evaluation of a monocular recognition-based pose recovery algorithm on the HumanEva II clips. The results show that the method achieves a mean relative error of around 10-12 cm per joint.

A New Lower Bound On Guard Placement For Wireless Localization, Mirela Damian, Robin Flatland, Joseph O'Rourke, Suneeta Ramswami

Computer Science: Faculty Publications

The problem of wireless localization asks to place and orient stations in the plane, each of which broadcasts a unique key within a fixed angular range, so that each point in the plane can determine whether it is inside or outside a given polygonal region. The primary goal is to minimize the number of stations. In this paper we establish a lower bound of ⌊2n/3⌋−1 stations for polygons in general position, for the case in which the placement of stations is restricted to polygon vertices, improving upon the existing ⌈n/2⌉ lower bound.

A Handle On What's Going On: Combining Tangible Interfaces And Ambient Displays For Collaborative Groups, Johanna Brewer, Amanda Williams, Paul Dourish

Computer Science: Faculty Publications

While tangible interfaces open up new possibilities for in- put and interaction, they are also interesting because of the ways in which they occupy the physical world just as we do. We have been working at the intersection of three research areas – tangible interfaces, ambient displays, and collaboration awareness. Our system, Nimio, uses engaging physical objects as both input devices (capturing aspects of individual activity) and output devices (expressing aspects of group activity). We present our design and experiences, focusing in particular on the tension between legibility and ambiguity and its relevance in collaborative settings.

Underground Aesthetics: Rethinking Urban Computing, Arianna Bassoli, Johanna Brewer, Paul Dourish, Karen Martin, Scott Mainwaring

Computer Science: Faculty Publications

An ethnographic study and a design proposal for a situated music-exchange application suggest how explicitly foregrounding the experiential qualities of urban life can help rethink urban computing design.

Connecting Polygonizations Via Stretches And Twangs, Mirela Damian, Robin Flatland, Joseph O'Rourke, Suneeta Ramswami

Computer Science: Faculty Publications

We show that the space of polygonizations of a fixed planar point set S of n points is connected by O(n² ) “moves” between simple polygons. Each move is composed of a sequence of atomic moves called “stretches” and "twangs". These atomic moves walk between weakly simple "polygonal wraps" of S. These moves show promise to serve as a basis for generating random polygons.

In-Between Theory And Practice: Dialogues In Design Research, Arianna Bassoli, Johanna Brewer, Karen Martin

Computer Science: Faculty Publications

Why Wait? and Betwixt are two of the workshops we have recently run on the theme of in-between-ness. The approach of social computing, where researchers work to understand how the socio-cultural aspects of human life relate to the design of new technologies, was the starting point for our investigation. By observing actual instances of in-between-ness in context we explored how design activities can be used as an opportunity to discuss and take positions on a specific theme, and as a space for narrowing the gap in design research between theoretical and practical thinking.

Sexual Interactions: Why We Should Talk About Sex In Hci, Johanna Brewer, Joseph Jofish Kaye, Amanda Williams, Susan Wyche

Computer Science: Faculty Publications

Within the CHI community there is growing interest in moving beyond cognition and expanding into the social, emotional, and bodily aspects of the human-computer experience. Sex lies at the intersection of these concerns, and indeed outside of HCI, has become a central topic for anthropology, behavioral sciences, and other areas of intellectual inquiry. Examining sex and themes related to it has benefited these disciplines and we intend to understand how it can contribute to HCI. There is a tendency to desexualize technology, despite the presence of sex and sexuality in a variety of interactions, including the use of the internet …

Hamiltonicity And Colorings Of Arrangement Graphs, Stefan Felsner, Ferran Hurtado, Marc Noy, Ileana Streinu

Computer Science: Faculty Publications

We study connectivity, Hamilton path and Hamilton cycle decomposition, 4-edge and 3-vertex coloring for geometric graphs arising from pseudoline (affine or projective) and pseudocircle (spherical) arrangements. While arrangements as geometric objects are well studied in discrete and computational geometry, their graph theoretical properties seem to have received little attention so far. In this paper we show that they provide well-structured examples of families of planar and projective-planar graphs with very interesting properties. Most prominently, spherical arrangements admit decompositions into two Hamilton cycles; this is a new addition to the relatively few families of 4-regular graphs that are known to have …

Boundary Fragment Matching And Articulated Pose Under Occlusion, Nicholas Howe

Computer Science: Faculty Publications

Silhouette recognition can reconstruct the three-dimensional pose of a human subject in monocular video so long as the camera’s view remains unoccluded by other objects. This paper develops a shape representation that can describe and compare partial shapes, extending the silhouette recognition technique to apply to video with occlusions. The new method operates without human intervention, and experiments demonstrate that it can reconstruct accurate three-dimensional articulated pose tracks from single-camera walking video despite occlusion of one-third to one-half of the subject.

Geometric Restrictions On Producible Polygonal Protein Chains, Erik D. Demaine, Stefan Langerman, Joseph O'Rourke

Computer Science: Faculty Publications

Fixed-angle polygonal chains in three dimensions serve as an interesting model of protein backbones. Here we consider such chains produced inside a "machine" modeled crudely as a cone, and examine the constraints this model places on the producible chains. We call this notion producible, and prove as our main result that a chain whose maximum turn angle is α is producible in a cone of half-angle ≥ α if and only if the chain is flattenable, that is, the chain can be reconfigured without self-intersection to lie flat in a plane. This result establishes that two seemingly disparate classes of …

On The Maximum Span Of Fixed-Angle Chains, Nadia Benbernou, Joseph O’Rourke

Computer Science: Faculty Publications

Soss proved that it is NP-hard to find the maximum flat span of a fixed-angle polygonal chain: the largest distance achievable between the endpoints in a planar embedding. These fixed-angle chains can serve as models of protein backbones. The corresponding problem in 3D is open. We show that two special cases of particular relevance to the protein model are solvable in polynomial time: when all link lengths are equal, and all angles are equal, the maximum 3D span is achieved in a flat configuration and can be computed in constant time. When all angles are equal (but the link lengths …

Polygons Flip Finitely: Flaws And A Fix, Erik D. Demaine, Blaise Gassend, Joseph O’Rourke, Godfried T. Toussaint

Computer Science: Faculty Publications

Every simple planar polygon can undergo only a finite number of pocket flips before becoming convex. Since Erdős posed this as an open problem in 1935, several independent purported proofs have been published. However, we uncover a plethora of errors and gaps in these arguments, and remedy these problems with a new (correct) proof.

Evaluating Lookup-Based Monocular Human Pose Tracking On The Humaneva Test Data, Nicholas Howe

Computer Science: Faculty Publications

This work presents an evaluation of several lookup-based methods for recovering three-dimensional human pose from monocular video sequences. The methods themselves are largely described elsewhere [1, 2], although the work presented here incorporates a few minor enhancements. The primary contribution of this work is the evaluation of the results on a data set with ground truth available, which allows for quantitative comparisons with other techniques. Methods relying upon silhouettes produced via background subtraction tend to act as a “straw man” in relation to the current state of the art; many recently proposed techniques work without reliance upon background subtraction and …

A Methodology For Efficiently Sampling The Conformation Space Of Molecular Structures, Audrey Lee, Ileana Streinu, Oliver Brock

Computer Science: Faculty Publications

Motivated by recently developed computational techniques for studying protein flexibility, and their potential applications in docking, we propose an efficient method for sampling the conformational space of complex molecular structures. We focus on the loop closure problem, identified in the work of Thorpe and Lei (2004 Phil. Mag. 84 1323-31) as a primary bottleneck in the fast simulation of molecular motions. By modeling a molecular structure as a branching robot, we use an intuitive method in which the robot holds onto itself for maintaining loop constraints. New conformations are generated by applying random external forces, while internal, attractive forces pull …

Flow Lookup And Biological Motion Perception, Nicholas Howe

Computer Science: Faculty Publications

Optical flow in monocular video can serve as a key for recognizing and tracking the three-dimensional pose of human subjects. In comparison with prior work using silhouettes as a key for pose lookup, flow data contains richer information and in experiments can successfully track more difficult sequences. Furthermore, flow recognition is powerful enough to model human abilities in perceiving biological motion from sparse input. The experiments described herein show that a tracker using flow moment lookup can reconstruct a common biological motion (walking) from images containing only point light sources attached to the joints of the moving subject.

Boosted Decision Trees For Word Recognition In Handwritten Document Retrieval, Nicholas Howe, Toni M. Rath, R. Manmatha

Computer Science: Faculty Publications

Recognition and retrieval of historical handwritten material is an unsolved problem. We propose a novel approach to recognizing and retrieving handwritten manuscripts, based upon word image classification as a key step. Decision trees with normalized pixels as features form the basis of a highly accurate AdaBoost classifier, trained on a corpus of word images that have been resized and sampled at a pyramid of resolutions. To stem problems from the highly skewed distribution of class frequencies, word classes with very few training samples are augmented with stochastically altered versions of the originals. This increases recognition performance substantially. On a standard …

Non-Stretchable Pseudo-Visibility Graphs, Ileana Streinu

Computer Science: Faculty Publications

We exhibit a family of graphs which can be realized as pseudo-visibility graphs of pseudo-polygons, but not of straight-line polygons. The example is based on the characterization of vertex-edge pseudo-visibility graphs of O'Rourke and Streinu [Proc. ACM Symp. Comput. Geometry, Nice, France, 1997, pp. 119-128] and extends a recent result of the author [Proc. ACM Symp. Comput. Geometry, Miami Beach, 1999, pp. 274-280] on non-stretchable vertex-edge visibility graphs. We construct a pseudo-visibility graph for which there exists a unique compatible vertex-edge visibility graph, which is then shown to be non-stretchable. The construction is then extended to an infinite family. © …

A Dictionary Construction Technique For Code Compression Systems With Echo Instructions, Philip Brisk, Jamie Macbeth, Ani Nahapetian, Majid Sarrafzadeh

Computer Science: Faculty Publications

No abstract provided.

Finding And Maintaining Rigid Components, Audrey Lee, Ileana Streinu, Louis Theran

Computer Science: Faculty Publications

We give the first complete analysis that the complexity of finding and maintaining rigid components of planar bar-and-joint frameworks and arbitrary d-dimensional body-and-bar frameworks, using a family of algorithms called pebble games, is O(n2). To this end, we intro- duce a new data structure problem called union pair- find, which maintains disjoint edge sets and supports pair-find queries of whether two vertices are spanned by a set. We present solutions that apply to generalizations of the pebble game algorithms, beyond the original rigidity motivation.

Computing Rigid Components Of Pseudo-Triangulation Mechanisms In Linear Time, Jack Snoeyink, Ileana Streinu

Computer Science: Faculty Publications

We investigate the problem of detecting rigid components (maximal Laman subgraphs) in a pseudotriangulation mechanism and in arbitrary pointed planar frameworks.F or general Laman graphs with some missing edges, it is known that rigid components can be computed in O(n2) time.Here we make substantial use of the special geometry of pointed pseudo-triangulation mechanisms to achieve linear time. The main application is a more robust implementation and a substantial reduction in numerical computations for the solution to the Carpenter's Rule problem given by the second author.

Pseudo-Triangulations, Rigidity And Motion Planning, Ileana Streinu

Computer Science: Faculty Publications

This paper proposes a combinatorial approach to planning non-colliding trajectories for a polygonal bar-and-joint framework with n vertices. It is based on a new class of simple motions induced by expansive one-degree-of-freedom mechanisms, which guarantee noncollisions by moving all points away from each other. Their combinatorial structure is captured by pointed pseudo-triangulations, a class of embedded planar graphs for which we give several equivalent characterizations and exhibit rich rigidity theoretic properties. The main application is an efficient algorithm for the Carpenter's Rule Problem: convexify a simple bar-and-joint planar polygonal linkage using only non-self-intersecting planar motions. A step of the algorithm …

The Correlation Between Internal & External Markers For Abdominal Tumors: Implications For Respiratory Gating, David P. Gierga, Johanna Brewer, Gregory C. Sharp, Margrit Betke, Christopher G. Willett, George T.Y. Chen

Computer Science: Faculty Publications

Purpose: The correlation of the respiratory motion of external patient markers and abdominal tumors was examined. Data of this type are important for image-guided therapy techniques, such as respiratory gating, that monitor the movement of external fiducials.

Methods and Materials: Fluoroscopy sessions for 4 patients with internal, radiopaque tumor fiducial clips were analyzed by computer vision techniques. The motion of the internal clips and the external markers placed on the patient’s abdominal skin surface were quantified and correlated.

Results: In general, the motion of the tumor and external markers were well correlated. The maximum amount of peak-to-peak craniocaudal tumor motion …