Open Access. Powered by Scholars. Published by Universities.®
- Discipline
- Institution
- Keyword
-
- COVID-19 (7)
- Computational geometry (6)
- Periodic framework (6)
- Protein rigidity (6)
- Unfolding (6)
-
- Flexibility (5)
- Folding (5)
- Review (5)
- Dilution (4)
- Historical manuscripts (4)
- Image Schemas (4)
- Rigid clusters (4)
- Sexuality (4)
- Simulated unfolding (4)
- Theory (4)
- Vulpes vulpes (4)
- Algorithms (3)
- Auxetic deformation (3)
- Circuit polynomial (3)
- Combinatorial resultant (3)
- Conceptual Dependency (3)
- Conceptual dependency (3)
- Education (3)
- Evaluation (3)
- Gender (3)
- Genus-zero (3)
- Gröbner basis elimination (3)
- High performance computing (3)
- Inductive construction (3)
- Knots (3)
- Publication Year
Articles 331 - 360 of 364
Full-Text Articles in Computer Sciences
Computational Geometry Column 41, Joseph O'Rourke
Computational Geometry Column 41, Joseph O'Rourke
Computer Science: Faculty Publications
The recent result that n congruent balls in Rd have at most 4 distinct geometric permutations is described.
On The Folkman-Lawrence Topological Representation Theorem For Oriented Matroids Of Rank 3, Jürgen Bokowski, Susanne Mock, Ileana Streinu
On The Folkman-Lawrence Topological Representation Theorem For Oriented Matroids Of Rank 3, Jürgen Bokowski, Susanne Mock, Ileana Streinu
Computer Science: Faculty Publications
We present a new direct proof of the Folkman-Lawrence topological representation theorem for oriented matroids of rank 3. © 2001 Academic Press.
Combinatorial Approach To Planar Non-Colliding Robot Arm Motion Planning, Ileana Streinu
Combinatorial Approach To Planar Non-Colliding Robot Arm Motion Planning, Ileana Streinu
Computer Science: Faculty Publications
We propose a combinatorial approach to plan non-colliding motions for a polygonal bar-and-joint framework. Our approach yields very efficient deterministic algorithms for a category of robot arm motion planning problems with many degrees of freedom, where the known general roadmap techniques would give exponential complexity. It is based on a novel class of one-degree-of-freedom mechanisms induced by pseudo triangulations of planar point sets, for which we provide several equivalent characterization and exhibit rich combinatorial and 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 …
Computational Geometry Column 40, Joseph O'Rourke
Computational Geometry Column 40, Joseph O'Rourke
Computer Science: Faculty Publications
It has recently been established by Below, De Loera, and Richter-Gebert that finding a minimum size (or even just a small) triangulation of a convex polyhedron is NP-complete. Their 3SAT-reduction proof is discussed.
On Reconfiguring Tree Linkages: Trees Can Lock, Therese Biedl, Erik D. Demaine, Martin L. Demaine, Sylvain Lazard, Anna Lubiw, Joseph O'Rourke, Steve Robbins, Ileana Streinu, Godfried Toussaint, Sue Whitesides
On Reconfiguring Tree Linkages: Trees Can Lock, Therese Biedl, Erik D. Demaine, Martin L. Demaine, Sylvain Lazard, Anna Lubiw, Joseph O'Rourke, Steve Robbins, Ileana Streinu, Godfried Toussaint, Sue Whitesides
Computer Science: Faculty Publications
It has recently been shown that any simple (i.e. nonintersecting) polygonal chain in the plane can be reconfigured to lie on a straight line, and any simple polygon can be reconfigured to be convex. This result cannot be extended to tree linkages: we show that there are trees with two simple configurations that are not connected by a motion that preserves simplicity throughout the motion. Indeed, we prove that an N-link tree can have 2Ω(N) equivalence classes of configurations.
Pushpush And Push-1 Are Np-Hard In 2d, Erik D. Demaine, Martin L. Demaine, Joseph O'Rourke
Pushpush And Push-1 Are Np-Hard In 2d, Erik D. Demaine, Martin L. Demaine, Joseph O'Rourke
Computer Science: Faculty Publications
We prove that two pushing-blocks puzzles are intractable in 2D. One of our constructions improves an earlier result that established intractability in 3D [OS99] for a puzzle inspired by the game PushPush. The second construction answers a question we raised in [DDO00] for a variant we call Push-1. Both puzzles consist of unit square blocks on an integer lattice; all blocks are movable. An agent may push blocks (but never pull them) in attempting to move between given start and goal positions. In the PushPush version, the agent can only push one block at a time, and moreover when a …
Computational Geometry Column 39, Joseph O'Rourke
Computational Geometry Column 39, Joseph O'Rourke
Computer Science: Faculty Publications
The resolution of a decades-old open problem is described: polygonal chains cannot lock in the plane.
Examples, Counterexamples, And Enumeration Results For Foldings And Unfoldings Between Polygons And Polytopes, Erik D. Demaine, Martin L. Demaine, Anna Lubiw, Joseph O'Rourke
Examples, Counterexamples, And Enumeration Results For Foldings And Unfoldings Between Polygons And Polytopes, Erik D. Demaine, Martin L. Demaine, Anna Lubiw, Joseph O'Rourke
Computer Science: Faculty Publications
We investigate how to make the surface of a convex polyhedron (a polytope) by folding up a polygon and gluing its perimeter shut, and the reverse process of cutting open a polytope and unfolding it to a polygon. We explore basic enumeration questions in both directions: Given a polygon, how many foldings are there? Given a polytope, how many unfoldings are there to simple polygons? Throughout we give special attention to convex polygons, and to regular polygons. We show that every convex polygon folds to an infinite number of distinct polytopes, but that their number of combinatorially distinct gluings is …
Computational Geometry Column 38, Joseph O'Rourke
Computational Geometry Column 38, Joseph O'Rourke
Computer Science: Faculty Publications
Recent results on curve reconstruction are described.
Computational Geometry Column 37, Erik D. Demaine, Joseph O'Rourke
Computational Geometry Column 37, Erik D. Demaine, Joseph O'Rourke
Computer Science: Faculty Publications
Open problems from the 15th Annual ACM Symposium on Computational Geometry.
Pushpush Is Np-Hard In 2d, Erik D. Demaine, Martin L. Demaine, Joseph O'Rourke
Pushpush Is Np-Hard In 2d, Erik D. Demaine, Martin L. Demaine, Joseph O'Rourke
Computer Science: Faculty Publications
We prove that a particular pushing-blocks puzzle is intractable in 2D, improving an earlier result that established intractability in 3D [OS99]. The puzzle, inspired by the game *PushPush*, consists of unit square blocks on an integer lattice. An agent may push blocks (but never pull them) in attempting to move between given start and goal positions. In the PushPush version, the agent can only push one block at a time, and moreover, each block, when pushed, slides the maximal extent of its free range. We prove this version is NP-hard in 2D by reduction from SAT.
Using Artificial Queries To Evaluate Image Retrieval, Nicholas Howe
Using Artificial Queries To Evaluate Image Retrieval, Nicholas Howe
Computer Science: Faculty Publications
This paper addresses the evaluation and comparison of algorithms for generalized image retrieval. The forms of evaluation currently in vogue are not calibrated with each other and thus do not allow the comparison of results reported by different research groups. We address the problem by proposing a class of tests that are algorithmically defined and relatively independent of the image test set. The proposed tests can be tailored to investigate retrieval performance under specific sets of adverse conditions, allowing additional insight into the strengths and weaknesses of different retrieval mechanisms.
Bayesian Reconstruction Of 3d Human Motion From Single-Camera Video, Nicholas Howe, Michael E. Leventon, William T. Freeman
Bayesian Reconstruction Of 3d Human Motion From Single-Camera Video, Nicholas Howe, Michael E. Leventon, William T. Freeman
Computer Science: Faculty Publications
The three-dimensional motion of humans is underdetermined when the observation is limited to a single camera, due to the inherent 3D ambiguity of 2D video. We present a system that reconstructs the 3D motion of human subjects from single-camera video, relying on prior knowledge about human motion, learned from training data, to resolve those ambiguities. After initialization in 2D, the tracking and 3D reconstruction is automatic; we show results for several video sequences. The results show the power of treating 3D body tracking as an inference problem.
Integrating Color, Texture, And Geometry For Image Retrieval, Nicholas Howe, Daniel P. Huttenlocher
Integrating Color, Texture, And Geometry For Image Retrieval, Nicholas Howe, Daniel P. Huttenlocher
Computer Science: Faculty Publications
This paper examines the problem of image retrieval from large, heterogeneous image databases. We present a technique that fulfills several needs identified by surveying recent research in the field. This technique fairly integrates a diverse and expandable set of image properties (for example, color, texture, and location) in a retrieval framework, and allows end-users substantial control over their use. We propose a novel set of evaluation methods in addition to applying established tests for image retrieval; our technique proves competitive with state-of-the-art methods in these tests and does better on certain tasks. Furthermore, it improves on many standard image retrieval …
Data As Ensembles Of Records: Representation And Comparison, Nicholas Howe
Data As Ensembles Of Records: Representation And Comparison, Nicholas Howe
Computer Science: Faculty Publications
Many collections of data do not come packaged in a form amenable to the ready application of machine learning techniques. Nevertheless, there has been only limited research on the problem of preparing raw data for learning, perhaps because widespread differences between domains make generalization difficult. This paper focuses on one common class of raw data, in which the entities of interest actually comprise collections of (smaller pieces of) homologous data. We present a technique for processing such collections into high-dimensional vectors, suitable for the application of many learning algorithms including clustering, nearestneighbors, and boosting. We demonstrate the abilities of the …
Computational Geometry Column 36, Joseph O'Rourke
Computational Geometry Column 36, Joseph O'Rourke
Computer Science: Faculty Publications
Two results in "computational origami" are illustrated.
Pushpush Is Np-Hard In 3d, Joseph O'Rourke, The Smith Problem Solving Group
Pushpush Is Np-Hard In 3d, Joseph O'Rourke, The Smith Problem Solving Group
Computer Science: Faculty Publications
We prove that a particular pushing-blocks puzzle is intractable in 3D. The puzzle, inspired by the game PushPush, consists of unit square blocks on an integer lattice. An agent may push blocks (but never pull them) in attempting to move between given start and goal positions. In the PushPush version, the agent can only push one block at a time, and moreover, each block, when pushed, slides the maximal extent of its free range. We prove this version is NP-hard in 3D by reduction from SAT. The corresponding problem in 2D remains open.
Zero-Parity Stabbing Information, Joseph O'Rourke, Irena Pashchenko
Zero-Parity Stabbing Information, Joseph O'Rourke, Irena Pashchenko
Computer Science: Faculty Publications
Everett et al. [EHN96, EHN97] introduced several varieties of stabbing information for the lines determined by pairs of vertices of a simple polygon P, and established their relationships to vertex visibility and other combinatorial data. In the same spirit, we define the “zero-parity (ZP) stabbing information” to be a natural weakening of their “weak stabbing information,” retaining only the distinction among {zero, odd, even > 0} in the number of polygon edges stabbed. Whereas the weak stabbing information’s relation to visibility remains an open problem, we completely settle the analogous questions for zero parity information, with three results: (1) ZP information …
Embedded Training For Complex Information Systems, Brant A. Cheikes
Embedded Training For Complex Information Systems, Brant A. Cheikes
Computer Science: Faculty Publications
One approach to providing affordable operator training in the workplace is to augment applications with intelligent embedded training systems (ETS). Intelligent embedded training is highly interactive: trainees practice realistic problem-solving tasks on the prime application with guidance and feedback from the training system. This article makes three contributions to the theory and technology of ETS design. First, we describe a framework based on Norman’s “stages of user activity” model for defining the instructional objectives of an ETS. Second, we demonstrate a non-invasive approach to instrumenting software applications, thereby enabling them to collaborate with an ETS. Third, we describe a method …
Stretchability Of Star-Like Pseudo-Visibility Graphs, Ileana Streinu
Stretchability Of Star-Like Pseudo-Visibility Graphs, Ileana Streinu
Computer Science: Faculty Publications
We present advances on the open problem of characterizing vertex-edge visibility graphs (ve-graphs), reduced by results of O'Rourke and Streinu to a stretchability question for pseudo-polygons. We introduce star-like pseudo-polygons as a special subclass containing all the known instances of non-stretchable pseudo-polygons. We give a complete combinatorial characterization and a linear-time decision procedure for star-like pseudo-polygon stretchability and star-like ve-graph recognition. To the best of our knowledge, this is the first problem in computational geometry for which a combinatorial characterization was found by first isolating the oriented matroid substructure and then separately solving the stretchability question. It is also the …
Weighting Unusual Feature Types, Nicholas Howe, Claire Cardie
Weighting Unusual Feature Types, Nicholas Howe, Claire Cardie
Computer Science: Faculty Publications
Feature weighting is known empirically to improve classification accuracy for k-nearest neighbor classifiers in tasks with irrelevant features. Many feature weighting algorithms are designed to work with symbolic features, or numeric features, or both, but cannot be applied to problems with features that do not fit these categories. This paper presents a new k-nearest neighbor feature weighting algorithm that works with any kind of feature for which a distance function can be defined. Applied to an image classification task with unusual set-like features, the technique improves classification accuracy significantly. In tests on standard data sets from the UCI repository, the …
Locked And Unlocked Polygonal Chains In 3d, Therese Biedl, Erik D. Demaine, Martin L. Demaine, Sylvain Lazard, Anna Lubiw, Joseph O'Rourke, Mark Overmars, Steve Robbins, Ileana Streinu, Godfried Toussaint, Sue Whitesides
Locked And Unlocked Polygonal Chains In 3d, Therese Biedl, Erik D. Demaine, Martin L. Demaine, Sylvain Lazard, Anna Lubiw, Joseph O'Rourke, Mark Overmars, Steve Robbins, Ileana Streinu, Godfried Toussaint, Sue Whitesides
Computer Science: Faculty Publications
In this paper, we study movements of simple polygonal chains in 3D. We say that an open, simple polygonal chain can be straightened if it can be continuously reconfigured to a straight sequence of segments in such a manner that both the length of each link and the simplicity of the chain are maintained throughout the movement. The analogous concept for closed chains is convexification: reconfiguration to a planar convex polygon. Chains that cannot be straightened or convexified are called locked. While there are open chains in 3D that are locked, we show that if an open chain has a …
Computational Geometry Column 35, Joseph O'Rourke
Computational Geometry Column 35, Joseph O'Rourke
Computer Science: Faculty Publications
The subquadratic algorithm of Kapoor for finding shortest paths on a polyhedron is described.
Computational Geometry Column 33, Joseph O'Rourke
Computational Geometry Column 33, Joseph O'Rourke
Computer Science: Faculty Publications
Several recent SIGGRAPH papers on surface simplification are described.
Percentile Blobs For Image Similarity, Nicholas Howe
Percentile Blobs For Image Similarity, Nicholas Howe
Computer Science: Faculty Publications
We present a new algorithm called PBSIM for computing image similarity, based upon a novel method of extracting bloblike features from images. In tests on a classification task using a data set of over 1000 images, PBSIM shows significantly higher accuracy than algorithms based upon color histograms, as well as previously reported results for another approach based upon bloblike features.
Illumination By Floodlights, William Steiger, Ileana Streinu
Illumination By Floodlights, William Steiger, Ileana Streinu
Computer Science: Faculty Publications
We consider three problems about the illumination of planar regions with floodlights of prescribed angles. Problem 1 is the decision problem: given a wedge W of angle φ ≤ π, n points p1 . . . . . pn in the plane and n angles α1 . . . . . αn such that ∑ni=1 αi ≤ θ, decide whether W can be illuminated by floodlights of angles α1 , . . . , αn placed in some order at the points p1 , . . . , pn and then rotated appropriately. We show that this problem is the …
Computational Geometry Column 34, Pankaj K. Agarwal, Joseph O'Rourke
Computational Geometry Column 34, Pankaj K. Agarwal, Joseph O'Rourke
Computer Science: Faculty Publications
Problems presented at the open-problem session of the 14th Annual ACM Symposium on Computational Geometry are listed.
The Vertex-Edge Visibility Graph Of A Polygon, Joseph O'Rourke, Ileana Streinu
The Vertex-Edge Visibility Graph Of A Polygon, Joseph O'Rourke, Ileana Streinu
Computer Science: Faculty Publications
We introduce a new polygon visibility graph, the vertex-edge visibility graph GV E, and demonstrate that it encodes more geometric information about the polygon than does the vertex visibility graph GV. © 1998 Elsevier Science B.V.
Computational Geometry Column 32, Joseph O'Rourke
Computational Geometry Column 32, Joseph O'Rourke
Computer Science: Faculty Publications
The proof of Dey's new k-set bound is illustrated.
Vertex-Edge Pseudo-Visibility Graphs: Characterization And Recognition, Joseph O'Rourke, Ileana Streinu
Vertex-Edge Pseudo-Visibility Graphs: Characterization And Recognition, Joseph O'Rourke, Ileana Streinu
Computer Science: Faculty Publications
We extend the notion of polygon visibility graphs to pseudo-polygons defined on generalized configurations of points. We consider both vertex-to-vertex, as well as vertex-to-edge visibility in pseudo-polygons. We study the characterization and recognition problems for vertex-edge pseudo-visibility graphs. Given a bipartite graph G satisfying three simple properties, which can all be checked in polynomial time, we show that we can define a generalized configuration of points and a pseudo-polygon on it, so that its vertex-edge pseudo-visibility graph is G. This provides a full characterization of vertex-edge pseudo-visibility graphs and a polynomial-time algorithm for the decision problem. It also implies that …