Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 13 of 13
Full-Text Articles in Physical Sciences and Mathematics
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
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.
Unfolding Polyhedra Via Cut-Tree Truncation, Alex Benton, Joseph O'Rourke
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
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.
Band Unfoldings And Prismatoids: A Counterexample, Joseph O'Rourke
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
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
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, …
A New Lower Bound On Guard Placement For Wireless Localization, Mirela Damian, Robin Flatland, Joseph O'Rourke, Suneeta Ramswami
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
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.
Recognition-Based Motion Capture And The Humaneva Ii Test Data, Nicholas Howe
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.
In-Between Theory And Practice: Dialogues In Design Research, Arianna Bassoli, Johanna Brewer, Karen Martin
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.
Underground Aesthetics: Rethinking Urban Computing, Arianna Bassoli, Johanna Brewer, Paul Dourish, Karen Martin, Scott Mainwaring
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.
Graded Sparse Graphs And Matroids, Audrey Lee, Ileana Streinu, Louis Theran
Graded Sparse Graphs And Matroids, Audrey Lee, Ileana Streinu, Louis Theran
Computer Science: Faculty Publications
Sparse graphs and their associated matroids play an important role in rigidity theory, where they capture the combinatorics of some families of generic minimally rigid structures. We define a new family called graded sparse graphs, arising from generically pinned bar-and-joint frameworks, and prove that they also form matroids. We also address several algorithmic problems on graded sparse graphs: Decision, Spanning, Extraction, Components, Optimization, and Extension. We sketch variations on pebble game algorithms to solve them.
Connecting Polygonizations Via Stretches And Twangs, Mirela Damian, Robin Flatland, Joseph O'Rourke, Suneeta Ramswami
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(n2 ) “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.