Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 8 of 8
Full-Text Articles in Physical Sciences and Mathematics
Flat-State Connectivity Of Linkages Under Dihedral Motions, Greg Aloupis, Erik D. Demaine, Vida Dujmović, Jeff Erickson, Stefan Langerman, Henk Meijer, Joseph O'Rourke, Mark Overmars, Michael Soss, Ileana Streinu, Godfried T. Toussaint
Flat-State Connectivity Of Linkages Under Dihedral Motions, Greg Aloupis, Erik D. Demaine, Vida Dujmović, Jeff Erickson, Stefan Langerman, Henk Meijer, Joseph O'Rourke, Mark Overmars, Michael Soss, Ileana Streinu, Godfried T. Toussaint
Computer Science: Faculty Publications
We explore which classes of linkages have the property that each pair of their flat states - that is, their embeddings in ℝ2 without self-intersection - can be connected by a continuous dihedral motion that avoids self-intersection throughout. Dihedral motions preserve all angles between pairs of incident edges, which is most natural for protein models. Our positive results include proofs that open chains with nonacute angles are flat-state connected, as are closed orthogonal unit-length chains. Among our negative results is an example of an orthogonal graph linkage that is flat-state disconnected. Several additional results are obtained for other restrictedclasses of …
Boosted Image Classification: An Empirical Study, Nicholas Howe
Boosted Image Classification: An Empirical Study, Nicholas Howe
Computer Science: Faculty Publications
The rapid pace of research in the fields of machine learning and image comparison has produced powerful new techniques in both areas. At the same time, research has been sparse on applying the best ideas from both fields to image classification and other forms of pattern recognition. This paper combines boosting with stateof-the-art methods in image comparison to carry out a comparative evaluation of several top algorithms. The results suggest that a new method for applying boosting may be most effective on data with many dimensions. Effectively marrying the best ideas from the two fields takes effort, but the techniques …
Computational Geometry Column 43, Joseph O'Rourke
Computational Geometry Column 43, Joseph O'Rourke
Computer Science: Faculty Publications
The concept of pointed pseudo-triangulations is defined and a few of its applications described.
Nonorthogonal Polyhedra Built From Rectangles, Melody Donoso, Joseph O'Rourke
Nonorthogonal Polyhedra Built From Rectangles, Melody Donoso, Joseph O'Rourke
Computer Science: Faculty Publications
We prove that any polyhedron of genus zero or genus one built out of rectangular faces must be an orthogonal polyhedron, but that there are nonorthogonal polyhedra of genus seven all of whose faces are rectangles. This leads to a resolution of a question posed by Biedl, Lubiw, and Sun [BLS99].
Enumerating Foldings And Unfoldings Between Polygons And Polytopes, Erik D. Demaine, Martin L. Demaine, Anna Lubiw, Joseph O'Rourke
Enumerating Foldings And Unfoldings Between Polygons And Polytopes, Erik D. Demaine, Martin L. Demaine, Anna Lubiw, Joseph O'Rourke
Computer Science: Faculty Publications
We pose and answer several questions concerning the number of ways to fold a polygon to a polytope, and how many polytopes can be obtained from one polygon; and the analogous questions for unfolding polytopes to polygons. Our answers are, roughly: exponentially many, or nondenumerably infinite.
Vertex-Unfoldings Of Simplicial Manifolds, Erik D. Demaine, David Eppstein, Jeff Erickson, George W. Hart, Joseph O'Rourke
Vertex-Unfoldings Of Simplicial Manifolds, Erik D. Demaine, David Eppstein, Jeff Erickson, George W. Hart, Joseph O'Rourke
Computer Science: Faculty Publications
We present an algorithm to unfold any triangulated 2-manifold (in particular, any simplicial polyhedron) into a non-overlapping, connected planar layout in linear time. The manifold is cut only along its edges. The resulting layout is connected, but it may have a disconnected interior; the triangles are connected at vertices, but not necessarily joined along edges. We extend our algorithm to establish a similar result for simplicial manifolds of arbitrary dimension.
Topological Sweep In Degenerate Cases, Eynat Rafalin, Diane Souvaine, Ileana Streinu
Topological Sweep In Degenerate Cases, Eynat Rafalin, Diane Souvaine, Ileana Streinu
Computer Science: Faculty Publications
Topological sweep can contribute to efficient implementations of various algorithms for data analysis. Real data, however, has degeneracies. The modification of the topological sweep algorithm presented here handles degenerate cases such as parallel or multiply concurrent lines without requiring numerical perturbations to achieve general position. Our method maintains the 0(n2) and 0(n) time and space complexities of the original algorithm, and is robust and easy to implement. We present experimental results.
Interlocked Open Linkages With Few Joints, Erik D. Demaine, Stefan Langerman, Joseph O'Rourke, Jack Snoeyink
Interlocked Open Linkages With Few Joints, Erik D. Demaine, Stefan Langerman, Joseph O'Rourke, Jack Snoeyink
Computer Science: Faculty Publications
We advance the study of collections of open linkages in 3-space that may be interlocked in the sense that the linkages cannot be separated without one bar crossing through another. We consider chains of bars connected with rigid joints, revolute joints, or universal joints and explore the smallest number of chains and bars needed to achieve interlock. Whereas previous work used topological invariants that applied to single or to closed chains, this work relies on geometric invariants and concentrates on open chains.