Computer Sciences Commons^™

Edge-Guarding Orthogonal Polyhedra, Nadia M. Benbernou, Erik D. Demaine, Martin L. Demaine, Anastasia Kurdia, Joseph O'Rourke, Godfried Toussaint, Jorge Urrutia, Giovanni Viglietta

Computer Science: Faculty Publications

We address the question: How many edge guards are needed to guard an orthogonal polyhedron of e edges, r of which are reflex? It was previously established [3] that e/12 are sometimes necessary and e/6 always suf- fice. In contrast to the closed edge guards used for these bounds, we introduce a new model, open edge guards (excluding the endpoints of the edge), which we argue are in some sense more natural in this context. After quantifying the relationship between closed and open edge guards, we improve the upper bound to show that, asymptotically, (11/72)e (open or closed) edge guards …

A Recognition-Based Motion Capture Baseline On The 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. 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 it. Finally, it investigates the …

Frēstyl: Simplifying The Process Of Promoting And Discovering Local Live Music, Arianna Bassoli, Johanna Brewer

Computer Science: Faculty Publications

In this paper, we present a new service for web and iPhone for promoting and discovering live music, frēstyl. We will show how frēstyl addresses and attempts to solve the problem that emerging musicians, local promoters and small/medium venues face when publicizing their events, both on a local and global level, and the problem that music fans face when trying to gather a complete but not overwhelming understanding of local and global live music events.

Exploring Agent-Based Simulations In Political Science Using Aggregate Temporal Graphs, R. Jordan Crouser, Jeremy G. Freeman, Remco Chang

Computer Science: Faculty Publications

Agent-based simulation has become a key technique for modeling and simulating dynamic, complicated behaviors in social and behavioral sciences. Lacking the appropriate tools and support, it is difficult for social scientists to thoroughly analyze the results of these simulations. In this work, we capture the complex relationships between discrete simulation states by visualizing the data as a temporal graph. In collaboration with expert analysts, we identify two graph structures which capture important relationships between pivotal states in the simulation and their inevitable outcomes. Finally, we demonstrate the utility of these structures in the interactive analysis of a large-scale social science …

How Locus Of Control Influences Compatibility With Visualization Style, Caroline Ziemkiewicz, R. Jordan Crouser, Ashley Rye Yauilla, Sara L. Su, William Ribarsky, Remco Chang

Computer Science: Faculty Publications

Existing research suggests that individual personality differences are correlated with a user’s speed and accuracy in solving problems with different types of complex visualization systems. In this pa- per, we extend this research by isolating factors in personality traits as well as in the visualizations that could have contributed to the observed correlation. We focus on a personality trait known as “lo- cus of control,” which represents a person’s tendency to see them- selves as controlled by or in control of external events. To isolate variables of the visualization design, we control extraneous factors such as color, interaction, and labeling, …

On The Lack Of Consensus Over The Meaning Of Openness: An Empirical Study, Alicia M. Grubb, Steve M. Easterbrook

Computer Science: Faculty Publications

This study set out to explore the views and motivations of those involved in a number of recent and current advocacy efforts (such as open science, computational provenance, and reproducible research) aimed at making science and scientific artifacts accessible to a wider audience. Using a exploratory approach, the study tested whether a consensus exists among advocates of these initiatives about the key concepts, exploring the meanings that scientists attach to the various mechanisms for sharing their work, and the social context in which this takes place. The study used a purposive sampling strategy to target scientists who have been active …

Exact Workspace Boundary By Extremal Reaches, Ciprian S. Borcea, Ileana Streinu

Computer Science: Faculty Publications

We present the first exact, combinatorial, polynomial time algorithm for computing the description of the workspace boundary for the class of revolute jointed robot arms arising from polygonal orthogonal chains in 3D. Copyright 2011 ACM.

Extremal Reaches In Polynomial Time, Ciprian S. Borcea, Ileana Streinu

Computer Science: Faculty Publications

Given a 3D polygonal chain with fixed edge lengths and fixed angles between consecutive edges (shortly, a revolutejointed chain or robot arm), the Extremal Reaches Problem asks for those configurations where the distance between the endpoints attains a global maximum or minimum value. In this paper, we solve it with a polynomial time algorithm. Copyright 2011 ACM.

Kinari-Web: A Server For Protein Rigidity Analysis, Naomi Fox, Filip Jagodzinski, Yang Li, Ileana Streinu

Computer Science: Faculty Publications

KINARI-Web is an interactive web server for performing rigidity analysis and visually exploring rigidity properties of proteins. It also provides tools for pre-processing the input data, such as selecting relevant chains from PDB files, adding hydrogen atoms and identifying stabilizing interactions. KINARI-Web offers a quick-start option for beginners, and highly customizable features for the experienced user. Chains, residues or atoms, as well as stabilizing constraints can be selected, removed or added, and the user can designate how different chemical interactions should be modeled during rigidity analysis. The enhanced Jmol-based visualizer allows for zooming in, highlighting or investigating different calculated rigidity …

Tangible Interaction And Learning: The Case For A Hybrid Approach, Michael S. Horn, R. Jordan Crouser, Marina U. Bers

Computer Science: Faculty Publications

Research involving tangible interaction and children has often focused on how tangibles might sup- port or improve learning compared to more traditional methods. In this paper, we review three of our research studies involving tangible computer programming that have addressed this question in a variety of learning environments with a diverse population of children. Through these studies, we identify situations in which tangible interaction seems to offer advantages for learning; how- ever, we have also identify situations in which tangible interaction proves less useful and an alternative interaction style provides a more appropriate medium for learning. Thus, we advocate for …

Common Edge-Unzippings For Tetrahedra, Joseph O'Rourke

Computer Science: Faculty Publications

It is shown that there are examples of distinct polyhedra, each with a Hamiltonian path of edges, which when cut, unfolds the surfaces to a common net. In particular, it is established for infinite classes of triples of tetrahedra.

Continuous Blooming Of Convex Polyhedra, Erik D. Demaine, Martin L. Demaine, Vi Hart, Joan Iacono, Stefan Langerman, Joseph O'Rourke

Computer Science: Faculty Publications

We construct the first two continuous bloomings of all convex polyhedra. First, the source unfolding can be continuously bloomed. Second, any unfolding of a convex polyhedron can be refined (further cut, by a linear number of cuts) to have a continuous blooming.

Conical Existence Of Closed Curves On Convex Polyhedra, Joseph O'Rourke, Costin Vîlcu

Computer Science: Faculty Publications

Let C be a simple, closed, directed curve on the surface of a convex polyhedron P. We identify several classes of curves C that "live on a cone," in the sense that C and a neighborhood to one side may be isometrically embedded on the surface of a cone Lambda, with the apex a of Lambda enclosed inside (the image of) C; we also prove that each point of C is "visible to" a. In particular, we obtain that these curves have non-self-intersecting developments in the plane. Moreover, the curves we identify that live on cones to both sides support …

Convex Polyhedra Realizing Given Face Areas, Joseph O'Rourke

Computer Science: Faculty Publications

Given n ≥ 4 positive real numbers, we prove in this note that they are the face areas of a convex polyhedron if and only if the largest number is not more than the sum of the others.

Efficient Constant-Velocity Reconfiguration Of Crystalline Robots, Greg Aloupis, Sébastien Collette, Mirela Damian, Erik D. Demaine, 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 constant velocity and can displace at most a constant number of other atoms. We assume that one of the atoms has access to the coordinates of atoms in the …

A Laplacian Energy For Document Binarization, Nicholas Howe

Computer Science: Faculty Publications

This paper describes a new algorithm for document binarization, building upon recent work in energy-based segmentation methods. It uses the Laplacian operator to assess the local likelihood of foreground and background labels, Canny edge detection to identify likely discontinuities, and a graph cut implementation to efficiently find the minimum energy solution of an objective function combining these concepts. The results of this algorithm place it near the top on both the DIBCO-09 and H-DIBCO assessments.

Style-Based Retrieval For Ancient Syriac Manuscripts, Emma Dalton, Nicholas Howe

Computer Science: Faculty Publications

Thousands of documents written in Syriac script by early Christian theologians are of unknown provenance and uncertain date, partly due to a shortage of human expertise. This paper addresses the problem of attribution by developing a novel algorithm for offline handwriting style identification and document retrieval, demonstrated on a set of documents in the Estrangelo variant of Syriac writing. The method employs a feature vector based upon the estimated affine transformation of actual observed characters, character parts, and voids within characters as compared to a hypothetical average or ideal form. Experiments on seventy-six pages from nineteen Syriac manuscripts written by …

Natural Realizations Of Sparsity Matroids, Ileana Streinu, Louis Theran

Computer Science: Faculty Publications

A hypergraph G with n vertices and m hyperedges with d endpoints each is (k; ℓ)- sparse if for all sub-hypergraphs G′ on n′ vertices and m′ edges, m′ < kn′ - ℓ. For integers k and ℓ satisfying 0 ≤ ℓ ≤ dk - 1, this is known to be a linearly representable matroidal family. Motivated by problems in rigidity theory, we give a new linear representation theorem for the (k; ℓ)-sparse hypergraphs that is natural; i.e., the representing matrix captures the vertex-edge incidence structure of the underlying hypergraph G. Copyright © 2011 DMFA Slovenije.

A Note On Solid Coloring Of Pure Simplicial Complexes, Joseph O'Rourke

Computer Science: Faculty Publications

We establish a simple generalization of a known result in the plane. The simplices in any pure simplicial complex in R^d may be colored with d+1 colors so that no two simplices that share a (d-1)-facet have the same color. In R² this says that any planar map all of whose faces are triangles may be 3-colored, and in R³ it says that tetrahedra in a collection may be "solid 4-colored" so that no two glued face-to-face receive the same color.

Sweeping Minimum Perimeter Enclosing Parallelograms: Optimal Crumb Cleanup, Yonit Bousany, Mary Leah Karker, Joseph O'Rourke, Leona Sparaco

Computer Science: Faculty Publications

We examine the problem of pushing all the points of a planar region into one point using parallel sweeps of an infinite line, minimizing the sum of the lengths of the sweep vectors. We characterize the optimal 2-sweeps of triangles, and provide a linear-time algorithm for convex polygons.

Flat Zipper-Unfolding Pairs For Platonic Solids, Joseph O'Rourke

Computer Science: Faculty Publications

We show that four of the five Platonic solids' surfaces may be cut open with a Hamiltonian path along edges and unfolded to a polygonal net each of which can "zipper-refold" to a flat doubly covered parallelogram, forming a rather compact representation of the surface. Thus these regular polyhedra have particular flat "zipper pairs." No such zipper pair exists for a dodecahedron, whose Hamiltonian unfoldings are "zip-rigid." This report is primarily an inventory of the possibilities, and raises more questions than it answers.

Flattening Single-Vertex Origami: The Non-Expansive Case, Gaiane Panina, Ileana Streinu

Computer Science: Faculty Publications

A single-vertex origami is a piece of paper with straight-line rays called creases emanating from a fold vertex placed in its interior or on its boundary. The Single-Vertex Origami Flattening problem asks whether it is always possible to reconfigure the creased paper from any configuration compatible with the metric, to a flat, non-overlapping position, in such a way that the paper is not torn, stretched and, for rigid origami, not bent anywhere except along the given creases. Streinu and Whiteley showed how to reduce the problem to the carpenter's rule problem for spherical polygons. Using spherical expansive motions, they solved …

Grouped Variable Model Selection For Heterogeneous Medical Signals, Jamie Macbeth, Majid Sarrafzadeh

Computer Science: Faculty Publications

We explore statistical regression techniques for use in medical monitoring and telehealth applications. Medical embedded systems of the present and future are recording vast sets of data related to medical conditions and physiology. In this paper, distributed time-lag linear models are proposed as a means to help explain relationships between two or more medical and physiological measurements. The issues associated with performing multiple regression with heterogeneous medical data are treated as problems in model selection. An automatic method of model selection is proposed to construct models for high sample rate data by grouping sets of predictor variables.

The grouped predictor …

Engaging Students In Information Storage Management Courses, Vladan Jovanovic, Timur Mirzoev, Lee Toderick, Rick Homkes, Mark Stockman

Computer Science: Faculty Publications

This panel will elaborate on faculty experiences with specific ways used to engage students in the Information Storage and Management, formerly Storage Technology, and the Virtualization coursework. The emphasize of the discussion will be on the mechanisms used in engaging students in learning and on experiences with various activities helpful for varying learning preferences/modes. All invited panelists are experienced faculty involved with subject matter courses via EMC’s Academic Alliance program. The resources made available via this alliance and through exchange among the faculty involved in teaching related subjects in IT and CS programs will be discussed and evaluated. The impact …

Wanda B.: Weight And Activity With Blood Pressure Monitoring System For Heart Failure Patients, Myung Kyung Suh, Lorraine S. Evangelista, Victor Chen, Wen Sao Hong, Jamie Macbeth, Ani Nahapetian, Florence Joy Figueras, Majid Sarrafzadeh

Computer Science: Faculty Publications

Heart failure is a leading cause of death in the United States, with around 5 million Americans currently suffering from congestive heart failure. The WANDA B. wireless health technology leverages sensor technology and wireless communication to monitor heart failure patient activity and to provide tailored guidance. Patients who have cardiovascular system disorders can measure their weight, blood pressure, activity levels, and other vital signs in a real-time automated fashion. The system was developed in conjunction with the UCLA Nursing School and the UCLA Wireless Health Institute for use on actual patients. It is currently in use with real patients in …

On Folding A Polygon To A Polyhedron, Joseph O'Rourke

Computer Science: Faculty Publications

We show that the open problem presented in "Geometric Folding Algorithms: Linkages, Origami, Polyhedra" [DO07] is solved by a theorem of Burago and Zalgaller [BZ96] from more than a decade earlier.

On Flat Polyhedra Deriving From Alexandrov's Theorem, Joseph O'Rourke

Computer Science: Faculty Publications

We show that there is a straightforward algorithm to determine if the polyhedron guaranteed to exist by Alexandrov's gluing theorem is a degenerate flat polyhedron, and to reconstruct it from the gluing instructions. The algorithm runs in O(n³) time for polygons whose gluings are specified by n labels.

Shrinking Symbolic Regression Over Medical And Physiological Signals, Jamie Macbeth, Majid Sarrafzadeh

Computer Science: Faculty Publications

Medical embedded systems of the present and future are recording vast sets of data related to medical conditions and physiology. Linear modeling techniques are proposed as a means to help explain relationships between two or more medical or physiological signal measurements from the same human subject. In this paper a statistical regression algorithm is explored for use in medical monitoring, telehealth, and medical research applications.

An essential element in applying linear modeling to physiological data is determining functional forms for the predictor signals. In this paper we demonstrate an efficient method for symbolic regression and model selection among possible transformation …

Health Econometrics: Respiration- Oxygenation Correlation Through Spectral Models, Jamie Macbeth, Majid Sarrafzadeh

Computer Science: Faculty Publications

Medical embedded systems are capable of recording vast data sets for physiological and medical research. Linear modeling techniques are proposed as a means to explore relationships between two or more medical or physiological signal measurements where a causal relationship is believed to be present. Multiple regression is explored for use in medical monitoring, telehealth, and clinical applications.

Spectral regression methods for high-bandwidth medical and physiological signals are demonstrated. The twostage method consists of performing an FFT over a timelagged window of the predictor signal, and constructing a model based on the FFT coefficients. The output of the regression is used …

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

Computer Science: Faculty Publications

We extend the notion of star unfolding to be based on a quasigeodesic loop Q rather than on a point. This gives a new general method to unfold the surface of any convex polyhedron ℘ to a simple (nonoverlapping) planar polygon: cut along one shortest path from each vertex of ℘ toQ, and cut all but one segment of Q.