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 301 - 330 of 364
Full-Text Articles in Computer Sciences
Partitioning Regular Polygons Into Circular Pieces Ii: Nonconvex Partitions, Mirela Damian, Joseph O'Rourke
Partitioning Regular Polygons Into Circular Pieces Ii: Nonconvex Partitions, Mirela Damian, Joseph O'Rourke
Computer Science: Faculty Publications
We explore optimal circular nonconvex partitions of regular k-gons. The circularity of a polygon is measured by its aspect ratio: the ratio of the radii of the smallest circumscribing circle to the largest inscribed disk. An optimal circular partition minimizes the maximum ratio over all pieces in the partition. We show that the equilateral triangle has an optimal 4-piece nonconvex partition, the square an optimal 13-piece nonconvex partition, and the pentagon has an optimal nonconvex partition with more than 20 thousand pieces. For hexagons and beyond, we provide a general algorithm that approaches optimality, but does not achieve it.
Unfolding Smooth Prismatoids, Nadia Benbernou, Patricia Cahn, Joseph O'Rourke
Unfolding Smooth Prismatoids, Nadia Benbernou, Patricia Cahn, Joseph O'Rourke
Computer Science: Faculty Publications
We define a notion for unfolding smooth, ruled surfaces, and prove that every smooth prismatoid (the convex hull of two smooth curves lying in parallel planes), has a nonoverlapping “volcano unfolding.” These unfoldings keep the base intact, unfold the sides outward, splayed around the base, and attach the top to the tip of some side rib. Our result answers a question for smooth prismatoids whose analog for polyhedral prismatoids remains unsolved.
Improving The Boosted Correlogram, Nicholas Howe, Amanda Ricketson
Improving The Boosted Correlogram, Nicholas Howe, Amanda Ricketson
Computer Science: Faculty Publications
Introduced seven years ago, the correlogram is a simple statistical image descriptor that nevertheless performs strongly on image retrieval tasks. As a result it has found wide use as a component inside larger systems for content-based image and video retrieval. Yet few studies have examined potential variants of the correlogram or compared their performance to the original. This paper presents systematic experiments on the correlogram and several variants under different conditions, showing that the results may vary significantly depending on both the variant chosen and its mode of application. As expected, the experimental setup combining correlogram variants with boosting shows …
Silhouette Lookup For Automatic Pose Tracking, Nicholas Howe
Silhouette Lookup For Automatic Pose Tracking, Nicholas Howe
Computer Science: Faculty Publications
Computers should be able to detect and track the articulated 3-D pose of a human being moving through a video sequence. Current tracking methods often prove slow and unreliable, and many must be initialized by a human operator before they can track a sequence. This paper introduces a simple yet effective algorithm for tracking articulated pose, based upon looking up observed silhouettes in a collection of known poses. The new algorithm runs quickly, can initialize itself without human intervention, and can automatically recover from critical tracking errors made while tracking previous frames in a video sequence.
The Structure Of Optimal Partitions Of Orthogonal Polygons Into Fat Rectangles, Joseph O'Rourke, Geetika Tewari
The Structure Of Optimal Partitions Of Orthogonal Polygons Into Fat Rectangles, Joseph O'Rourke, Geetika Tewari
Computer Science: Faculty Publications
Motivated by a VLSI masking problem, we explore partitions of an orthogonal polygon of n vertices into isothetic rectangles that maximize the shortest rectangle side over all rectangles. Thus no rectangle is "thin"; all rectangles are "fat". We show that such partitions have a rich structure, more complex than what one might at first expect. For example, for partitions all "cuts" of which are anchored on the boundary, sometimes cuts are needed 1/2 or 1/3 of the distance between two polygon edges, but they are never needed at fractions with a larger denominator. Partitions using cuts without any restrictions seem …
Real-Time 4d Tumor Tracking And Modeling From Internal And External Fiducials In Fluoroscopy, Johanna Brewer, Margrit Betke, David P. Gierga, George T.Y. Chen
Real-Time 4d Tumor Tracking And Modeling From Internal And External Fiducials In Fluoroscopy, Johanna Brewer, Margrit Betke, David P. Gierga, George T.Y. Chen
Computer Science: Faculty Publications
Fluoroscopy is currently used in treatment planning for patients undergoing radiation therapy. Radiation oncologists would like to maximize the amount of dose the tumor receives and minimize the amount delivered to the surrounding tissues. During treatment, patients breathe freely and so the tumor location will not be fixed. This makes calculating the amount of dose delivered to the tumor, and verifying that the tumor actually receives that dose, difficult. We describe a correlation- based method of tracking the two-dimensional (2D) motion of internal markers (surgical clips) placed around the tumor. We established ground truth and evaluated the accuracy of the …
A 2-Chain Can Interlock With A K-Chain, Julie Glass, Stefan Langerman, Joseph O'Rourke, Jack Snoeyink, Jianyuan K. Zhong
A 2-Chain Can Interlock With A K-Chain, Julie Glass, Stefan Langerman, Joseph O'Rourke, Jack Snoeyink, Jianyuan K. Zhong
Computer Science: Faculty Publications
One of the open problems posed in [3] is: what is the minimal number k such that an open, flexible k-chain can interlock with a flexible 2-chain? In this paper, we establish the assumption behind this problem, that there is indeed some k that achieves interlocking. We prove that a flexible 2-chain can interlock with a flexible, open 16-chain.
Better Foreground Segmentation Through Graph Cuts, Nicholas Howe, Alexandra Deschamps
Better Foreground Segmentation Through Graph Cuts, Nicholas Howe, Alexandra Deschamps
Computer Science: Faculty Publications
For many tracking and surveillance applications, background subtraction provides an effective means of segmenting objects moving in front of a static background. Researchers have traditionally used combinations of morphological operations to remove the noise inherent in the background-subtracted result. Such techniques can effectively isolate foreground objects, but tend to lose fidelity around the borders of the segmentation, especially for noisy input. This paper explores the use of a minimum graph cut algorithm to segment the foreground, resulting in qualitatively and quantitiatively cleaner segmentations. Experiments on both artificial and real data show that the graphbased method reduces the error around segmented …
Computational Geometry Column 45, Joseph O'Rourke
Computational Geometry Column 45, Joseph O'Rourke
Computer Science: Faculty Publications
The algorithm of Edelsbrunner for surface reconstruction by "wrapping" a set of points in R3 is described.
Interlocked Open And Closed Linkages With Few Joints, Erik D. Demaine, Stefan Langerman, Joseph O'Rourke, Jack Snoeyink
Interlocked Open And Closed Linkages With Few Joints, Erik D. Demaine, Stefan Langerman, Joseph O'Rourke, Jack Snoeyink
Computer Science: Faculty Publications
We study collections of linkages in 3-space that are interlocked in the sense that the linkages cannot be separated without one bar crossing through another. We explore pairs of linkages, one open chain and one closed chain, each with a small number of joints, and determine which can be interlocked. In particular, we show that a triangle and an open 4-chain can interlock, a quadrilateral and an open 3-chain can interlock, but a triangle and an open 3-chain cannot interlock.
Pushing Blocks Is Hard, Erik D. Demaine, Martin L. Demaine, Michael Hoffmann, Joseph O'Rourke
Pushing Blocks Is Hard, Erik D. Demaine, Martin L. Demaine, Michael Hoffmann, Joseph O'Rourke
Computer Science: Faculty Publications
We prove NP-hardness of a wide class of pushing-block puzzles similar to the classic Sokoban, generalizing several previous results [E.D. Demaine et al., in: Proc. 12th Canad. Conf. Comput. Geom., 2000, pp. 211-219; E.D. Demaine et al., Technical Report, January 2000; A. Dhagat, J. O'Rourke, in: Proc. 4th Canad. Conf. Comput. Geom., 1992, pp. 188-191; D. Dor, U. Zwick, Computational Geometry 13 (4) (1999) 215-228; J. O'Rourke, Technical Report, November 1999; G. Wilfong, Ann. Math. Artif. Intell. 3 (1991) 131-150]. The puzzles consist of unit square blocks on an integer lattice; all blocks are movable. The robot may move horizontally …
A Closer Look At Boosted Image Retrieval, Nicholas Howe
A Closer Look At Boosted Image Retrieval, Nicholas Howe
Computer Science: Faculty Publications
Margin-maximizing techniques such as boosting have been generating excitement in machine learning circles for several years now. Although these techniques offer significant improvements over previous methods on classification tasks, little research has examined the application of techniques such as boosting to the problem of retrieval from image and video databases. This paper looks at boosting for image retrieval and classification, with a comparative evaluation of several top algorithms combined in two different ways with boosting. The results show that boosting improves retrieval precision and recall (as expected), but that variations in the way boosting is applied can significantly affect the …
Open Problems From Cccg 2002, Erik D. Demaine, Joseph O'Rourke
Open Problems From Cccg 2002, Erik D. Demaine, Joseph O'Rourke
Computer Science: Faculty Publications
No abstract provided.
Efficient Computation Of Location Depth Contours By Methods Of Computational Geometry, Kim Miller, Suneeta Ramaswami, Peter Rousseeuw, J. Antoni Sellarès, Diane Souvaine, Ileana Streinu, Anja Struyf
Efficient Computation Of Location Depth Contours By Methods Of Computational Geometry, Kim Miller, Suneeta Ramaswami, Peter Rousseeuw, J. Antoni Sellarès, Diane Souvaine, Ileana Streinu, Anja Struyf
Computer Science: Faculty Publications
The concept of location depth was introduced as a way to extend the univariate notion of ranking to a bivariate configuration of data points. It has been used successfully for robust estimation, hypothesis testing, and graphical display. The depth contours form a collection of nested polygons, and the center of the deepest contour is called the Tukey median. The only available implemented algorithms for the depth contours and the Tukey median are slow, which limits their usefulness. In this paper we describe an optimal algorithm which computes all bivariate depth contours in O(n 2) time and space, using topological sweep …
The Foldings Of A Square To Convex Polyhedra, Rebecca Alexander, Heather Dyson, Joseph O'Rourke
The Foldings Of A Square To Convex Polyhedra, Rebecca Alexander, Heather Dyson, Joseph O'Rourke
Computer Science: Faculty Publications
The structure of the set of all convex polyhedra foldable from a square is detailed. It is proved that five combinatorially distinct nondegenerate polyhedra, and four different flat polyhedra, are realizable. All the polyhedra are continuously deformable into each other, with the space of polyhedra having the topology of four connected rings.
Partitioning Regular Polygons Into Circular Pieces I: Convex Partitions, Mirela Damian, Joseph O'Rourke
Partitioning Regular Polygons Into Circular Pieces I: Convex Partitions, Mirela Damian, Joseph O'Rourke
Computer Science: Faculty Publications
We explore an instance of the question of partitioning a polygon into pieces, each of which is as “circular” as possible, in the sense of having an aspect ratio close to 1. The aspect ratio of a polygon is the ratio of the diameters of the smallest circumscribing circle to the largest inscribed disk. The problem is rich even for partitioning regular polygons into convex pieces, the focus of this paper. We show that the optimal (most circular) partition for an equilateral triangle has an infinite number of pieces, with the lower bound approachable to any accuracy desired by a …
Computational Geometry Column 44, Joseph O'Rourke
Computational Geometry Column 44, Joseph O'Rourke
Computer Science: Faculty Publications
The open problem of whether or not every pair of equal-area polygons has a hinged dissection is discussed.
On The Development Of The Intersection Of A Plane With A Polytope, Joseph O'Rourke
On The Development Of The Intersection Of A Plane With A Polytope, Joseph O'Rourke
Computer Science: Faculty Publications
Define a “slice” curve as the intersection of a plane with the surface of a polytope, i.e., a convex polyhedron in three dimensions. We prove that a slice curve develops on a plane without self-intersection. The key tool used is a generalization of Cauchy's arm lemma to permit nonconvex “openings” of a planar convex chain.
The Zigzag Path Of A Pseudo-Triangulation, Oswin Aichholzer, Günter Rote, Bettina Speckmann, Ileana Streinu
The Zigzag Path Of A Pseudo-Triangulation, Oswin Aichholzer, Günter Rote, Bettina Speckmann, Ileana Streinu
Computer Science: Faculty Publications
We define the zigzag path of a pseudo-triangulation, a concept generalizing the path of a triangulation of a point set. The pseudotriangulation zigzag path allows us to use divide-and-conquer type of approaches for suitable (i.e., decomposable) problems on pseudo-triangulations. For this we provide an algorithm that enumerates all pseudotriangulation zigzag paths (of all pseudo-triangulations of a given point set with respect to a given line) in O(n2) time per path and O(n2) space, where n is the number of points. We illustrate applications of our scheme which include a novel algorithm to count the number of pseudotriangulations of a point …
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.
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.
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.
Fast Implementation Of Depth Contours Using Topological Sweep, Kim Miller, Suneeta Ramaswami, Peter Rousseeuw, Toni Sellarès, Diane Souvaine, Ileana Streinu, Anja Struyf
Fast Implementation Of Depth Contours Using Topological Sweep, Kim Miller, Suneeta Ramaswami, Peter Rousseeuw, Toni Sellarès, Diane Souvaine, Ileana Streinu, Anja Struyf
Computer Science: Faculty Publications
The concept of location depth was introduced in statistics as a way to extend the univariate notion of ranking to a bivariate configuration of data points. It has been used successfully for robust estimation, hypothesis testing, and graphical display. These reguire the computation of depth regions, which form a collection of nested polygons. The center of the deepest region is called the Tukey median. The only available implemented algorithms for the depth contours and the Tukey median are slow, which limits their usefulness. In this paper we describe an optimal algorithm which computes all depth contours in &Ogr;(n 2) time …
Polygonal Chains Cannot Lock In 4d, Roxana Cocan, Joseph O'Rourke
Polygonal Chains Cannot Lock In 4d, Roxana Cocan, Joseph O'Rourke
Computer Science: Faculty Publications
We prove that, in all dimensions d ≥ 4, every simple open polygonal chain and every tree may be straightened, and every simple closed polygonal chain may be convexified. These reconfigurations can be achieved by algorithms that use polynomial time in the number of vertices, and result in a polynomial number of “moves.” These results contrast to those known for d = 2, where trees can “lock,” and for d = 3, where open and closed chains can lock.
Computational Geometry Column 42, Joseph S. B. Mitchell, Joseph O'Rourke
Computational Geometry Column 42, Joseph S. B. Mitchell, Joseph O'Rourke
Computer Science: Faculty Publications
A compendium of thirty previously published open problems in computational geometry is presented.