Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 6 of 6
Full-Text Articles in Mathematics
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.
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.
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.