Open Access. Powered by Scholars. Published by Universities.®

Geometry and Topology Commons™

Open Access. Powered by Scholars. Published by Universities.®

Computer Sciences

Institution
Keyword
Publication Year
Publication
Publication Type
File Type

Articles 61 - 90 of 106

Full-Text Articles in Geometry and Topology

Highway Hull Revisited, Greg Aloupis, Jean Cardinal, Sébastien Collette, Ferran Hurtado, Stefan Langerman, Joseph O'Rourke, Belén Palop Feb 2010

Highway Hull Revisited, Greg Aloupis, Jean Cardinal, Sébastien Collette, Ferran Hurtado, Stefan Langerman, Joseph O'Rourke, Belén Palop

Computer Science: Faculty Publications

A highway H is a line in the plane on which one can travel at a greater speed than in the remaining plane. One can choose to enter and exit H at any point. The highway time distance between a pair of points is the minimum time required to move from one point to the other, with optional use of H. The highway hull H(S,H) of a point set S is the minimal set containing S as well as the shortest paths between all pairs of points in H(S,H), using the highway time distance. We provide a Θ(nlogn) worst-case …

Go to article

Morphing Of Triangular Meshes In Shape Space, Stefanie Wuhrer, Prosenjit Bose, Chang Shu, Joseph O'Rourke, Alan Brunton Jan 2010

Morphing Of Triangular Meshes In Shape Space, Stefanie Wuhrer, Prosenjit Bose, Chang Shu, Joseph O'Rourke, Alan Brunton

Computer Science: Faculty Publications

We present a novel approach to morph between two isometric poses of the same non-rigid object given as triangular meshes. We model the morphs as linear interpolations in a suitable shape space S. For triangulated 3D polygons, we prove that interpolating linearly in this shape space corresponds to the most isometric morph in R3 . We then extend this shape space to arbitrary triangulations in 3D using a heuristic approach and show the practical use of the approach using experiments. Furthermore, we discuss a modified shape space that is useful for isometric skeleton morphing. All of the newly presented …

Go to article

Some Properties Of Yao Y4 Subgraphs, Joseph O'Rourke May 2009

Some Properties Of Yao Y4 Subgraphs, Joseph O'Rourke

Computer Science: Faculty Publications

The Yao graph for k = 4, Y4, is naturally partitioned into four subgraphs, one per quadrant. We show that the subgraphs for one quadrant differ from the subgraphs for two adjacent quadrants in three properties: planarity, connectedness, and whether the directed graphs are spanners.

Go to article

Topological Structures In The Equities Market Network, Gregory Leibon, Scott Pauls, Daniel Rockmore, Robert Savell Dec 2008

Topological Structures In The Equities Market Network, Gregory Leibon, Scott Pauls, Daniel Rockmore, Robert Savell

Dartmouth Scholarship

We present a new method for articulating scale-dependent topological descriptions of the network structure inherent in many complex systems. The technique is based on “partition decoupled null models,” a new class of null models that incorporate the interaction of clustered partitions into a random model and generalize the Gaussian ensemble. As an application, we analyze a correlation matrix derived from 4 years of close prices of equities in the New York Stock Exchange (NYSE) and National Association of Securities Dealers Automated Quotation (NASDAQ). In this example, we expose (i) a natural structure composed of 2 interacting partitions of …

Go to article

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

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

Computer Science: Faculty Publications

We extend the notion of a star unfolding to be based on a simple quasigeodesic loop Q rather than on a point. This gives a new general method to unfold the surface of any convex polyhedron P to a simple, planar polygon: shortest paths from all vertices of P to Q are cut, and all but one segment of Q is cut.

Go to article

Unfolding Manhattan Towers, Mirela Damian, Robin Flatland, Joseph O'Rourke Jul 2008

Unfolding Manhattan Towers, Mirela Damian, Robin Flatland, Joseph O'Rourke

Computer Science: Faculty Publications

We provide an algorithm for unfolding the surface of any orthogonal polyhedron that falls into a particular shape class we call Manhattan Towers, to a nonoverlapping planar orthogonal polygon. The algorithm cuts along edges of a 4×5×1 refinement of the vertex grid.

Go to article

Cauchy’S Arm Lemma On A Growing Sphere, Zachary Abel, David Charlton, Sébastien Collette, Erik D. Demaine, Martin L. Demaine, Stefan Langerman, Joseph O'Rourke, Val Pinciu, Godfried Toussaint Apr 2008

Cauchy’S Arm Lemma On A Growing Sphere, Zachary Abel, David Charlton, Sébastien Collette, Erik D. Demaine, Martin L. Demaine, Stefan Langerman, Joseph O'Rourke, Val Pinciu, Godfried Toussaint

Computer Science: Faculty Publications

We propose a variant of Cauchy's Lemma, proving that when a convex chain on one sphere is redrawn (with the same lengths and angles) on a larger sphere, the distance between its endpoints increases. The main focus of this work is a comparison of three alternate proofs, to show the links between Toponogov's Comparison Theorem, Legendre's Theorem and Cauchy's Arm Lemma.

Go to article

Grid Vertex-Unfolding Orthogonal Polyhedra, Mirela Damian Mar 2008

Grid Vertex-Unfolding Orthogonal Polyhedra, Mirela Damian

Computer Science: Faculty Publications

No abstract provided.

Go to article

A Class Of Convex Polyhedra With Few Edge Unfoldings, Alex Benton, Joseph O'Rourke Jan 2008

A Class Of Convex Polyhedra With Few Edge Unfoldings, Alex Benton, Joseph O'Rourke

Computer Science: Faculty Publications

We construct a sequence of convex polyhedra on n vertices with the property that, as n -> infinity, the fraction of its edge unfoldings that avoid overlap approaches 0, and so the fraction that overlap approaches 1. Nevertheless, each does have (several) nonoverlapping edge unfoldings.

Go to article

Band Unfoldings And Prismatoids: A Counterexample, Joseph O'Rourke Oct 2007

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.

Go to article

Unfolding Restricted Convex Caps, Joseph O'Rourke Sep 2007

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.

Go to article

Epsilon-Unfolding Orthogonal Polyhedra, Mirela Damian, Robin Flatland, Joseph O'Rourke Jun 2007

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, …

Go to article

A New Lower Bound On Guard Placement For Wireless Localization, Mirela Damian, Robin Flatland, Joseph O'Rourke, Suneeta Ramswami Jan 2007

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.

Go to article

Connecting Polygonizations Via Stretches And Twangs, Mirela Damian, Robin Flatland, Joseph O'Rourke, Suneeta Ramswami Jan 2007

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.

Go to article

Partitioning Regular Polygons Into Circular Pieces Ii: Nonconvex Partitions, Mirela Damian, Joseph O'Rourke Dec 2004

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.

Go to article

Unfolding Smooth Prismatoids, Nadia Benbernou, Patricia Cahn, Joseph O'Rourke Oct 2004

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.

Go to article

A 2-Chain Can Interlock With A K-Chain, Julie Glass, Stefan Langerman, Joseph O'Rourke, Jack Snoeyink, Jianyuan K. Zhong Jan 2004

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.

Go to article

Computational Geometry Column 45, Joseph O'Rourke Jan 2004

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.

Go to article

Open Problems From Cccg 2002, Erik D. Demaine, Joseph O'Rourke Jun 2003

Open Problems From Cccg 2002, Erik D. Demaine, Joseph O'Rourke

Computer Science: Faculty Publications

No abstract provided.

Go to article

Partitioning Regular Polygons Into Circular Pieces I: Convex Partitions, Mirela Damian, Joseph O'Rourke Jan 2003

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 …

Go to article

Computational Geometry Column 44, Joseph O'Rourke Jan 2003

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.

Go to article

On The Development Of The Intersection Of A Plane With A Polytope, Joseph O'Rourke Jan 2003

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.

Go to article

Computational Geometry Column 43, Joseph O'Rourke Jun 2002

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.

Go to article

Nonorthogonal Polyhedra Built From Rectangles, Melody Donoso, Joseph O'Rourke May 2002

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].

Go to article

Enumerating Foldings And Unfoldings Between Polygons And Polytopes, Erik D. Demaine, Martin L. Demaine, Anna Lubiw, Joseph O'Rourke Mar 2002

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.

Go to article

Vertex-Unfoldings Of Simplicial Manifolds, Erik D. Demaine, David Eppstein, Jeff Erickson, George W. Hart, Joseph O'Rourke Jan 2002

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.

Go to article

Polygonal Chains Cannot Lock In 4d, Roxana Cocan, Joseph O'Rourke Nov 2001

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.

Go to article

Computational Geometry Column 42, Joseph S. B. Mitchell, Joseph O'Rourke Oct 2001

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.

Go to article

Computational Geometry Column 41, Joseph O'Rourke Apr 2001

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.

Go to article

Computational Geometry Column 40, Joseph O'Rourke Dec 2000

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.

Go to article

First Prev Next Last