Every Tetrahedron has a 3-vertex Quasigeodesic
We prove that every tetrahedron T has a simple, closed quasigeodesic that passes through three vertices of T. Equivalently, every T has a face whose "exterior angles" are at most pi.
Source author record
Joseph O'Rourke
Joseph O'Rourke appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.
ResearcherUnclaimed source record
Catalog footprint
What is connected
26works
5topics
4close collaborators
Research graph
See the researcher in context
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
Building this map preview
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
26 published item(s)
preprint2022arXiv
Reshaping Convex Polyhedra
Given a convex polyhedral surface P, we define a tailoring as excising from P a simple polygonal domain that contains one vertex v, and whose boundary can be sutured closed to a new convex polyhedron via Alexandrov's Gluing Theorem. In particular, a digon-tailoring cuts off from P a digon containing v, a subset of P bounded by two equal-length geodesic segments that share endpoints, and can then zip closed. In the first part of this monograph, we primarily study properties of the tailoring operation on convex polyhedra. We show that P can be reshaped to any polyhedral convex surface Q a subset of conv(P) by a sequence of tailorings. This investigation uncovered previously unexplored topics, including a notion of unfolding of Q onto P--cutting up Q into pieces pasted non-overlapping onto P, and to continuously folding P onto Q. In the second part of this monograph, we study vertex-merging processes on convex polyhedra (each vertex-merge being in a sense the reverse of a digon-tailoring), creating embeddings of P into enlarged surfaces. We aim to produce non-overlapping polyhedral and planar unfoldings, which led us to develop an apparently new theory of convex sets, and of minimal length enclosing polygons, on convex polyhedra. All our theorem proofs are constructive, implying polynomial-time algorithms.
0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv
Simple Closed Quasigeodesics on Tetrahedra
Pogorelov proved in 1949 that every every convex polyhedron has at least three simple closed quasigeodesics. Whereas a geodesic has exactly pi surface angle to either side at each point, a quasigeodesic has at most pi surface angle to either side at each point. Pogorelov's existence proof did not suggest a way to identify the three quasigeodesics, and it is only recently that a finite algorithm has been proposed. Here we identify three simple closed quasigeodesics on any tetrahedron: at least one through 1 vertex, at least one through 2 vertices, and at least one through 3 vertices. The only exception is that isosceles tetrahedra have simple closed geodesics but do not have a 1-vertex quasigeodesic. We also identify an infinite class of tetrahedra that each have at least 34 simple closed quasigeodesics.
0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv
Cut Locus Realizations on Convex Polyhedra
We prove that every positively-weighted tree T can be realized as the cut locus C(x) of a point x on a convex polyhedron P, with T weights matching C(x) lengths. If T has n leaves, P has (in general) n+1 vertices. We show there are in fact a continuum of polyhedra P each realizing T for some x on P. Three main tools in the proof are properties of the star unfolding of P, Alexandrov's gluing theorem, and a cut-locus partition lemma. The construction of P from T is surprisingly simple.
0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv
Edge-Unfolding Nearly Flat Convex Caps
The main result of this paper is a proof that a nearly flat, acutely triangulated convex cap C in R^3 has an edge-unfolding to a non-overlapping polygon in the plane. A convex cap is the intersection of the surface of a convex polyhedron and a halfspace. "Nearly flat" means that every outer face normal forms a sufficiently small angle phi < Phi with the z-axis orthogonal to the halfspace bounding plane. The size of Phi depends on the acuteness gap alpha: if every triangle angle is at most pi/2-alpha, then Phi ~= 0.36 sqrt(alpha) suffices; e.g., for alpha ~= 3deg, Phi = 5deg. Even if C is closed to a polyhedron by adding the convex polygonal base under C, this polyhedron can be edge-unfolded without overlap. The proof employs the recent concepts of angle-monotone and radially monotone curves. The proof is constructive, leading to a polynomial-time algorithm for finding the edge-cuts, at worst O(n^2); a version has been implemented.
0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv
A Note on Unbounded Polyhedra Derived from Convex Caps
The construction of an unbounded polyhedron from a "jagged'' convex cap is described, and several of its properties discussed, including its relation to Alexandrov's "limit angle."
0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv
Some Polycubes Have No Edge Zipper Unfolding
It is unknown whether every polycube (polyhedron constructed by gluing cubes face-to-face) has an edge unfolding, that is, cuts along edges of the cubes that unfolds the polycube to a single nonoverlapping polygon in the plane. Here we construct polycubes that have no *edge zipper unfolding* where the cut edges are further restricted to form a path.
0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv
Tailoring for Every Body: Reshaping Convex Polyhedra
Given any two convex polyhedra P and Q, we prove as one of our main results that the surface of P can be reshaped to a homothet of Q by a finite sequence of "tailoring" steps. Each tailoring excises a digon surrounding a single vertex and sutures the digon closed. One phrasing of this result is that, if Q can be "sculpted" from P by a series of slices with planes, then Q can be tailored from P. And there is a sense in which tailoring is finer than sculpting in that P may be tailored to polyhedra that are not achievable by sculpting P. It is an easy corollary that, if S is the surface of any convex body, then any convex polyhedron P may be tailored to approximate a homothet of S as closely as desired. So P can be "whittled" to e.g., a sphere S. Another main result achieves the same reshaping, but by excising more complicated shapes we call "crests," still each enclosing one vertex. Reversing either digon-tailoring or crest-tailoring leads to proofs that any Q inside P can be enlarged to P by cutting Q and inserting and sealing surface patches. One surprising corollary of these results is that, for Q a subset of P, we can cut-up Q into pieces and paste them non-overlapping onto an isometric subset of P. This can be viewed as a form of "unfolding" Q onto P. All our proofs are constructive, and lead to polynomial-time algorithms.
0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv
Unfolding Convex Polyhedra via Radially Monotone Cut Trees
A notion of "radially monotone" cut paths is introduced as an effective choice for finding a non-overlapping edge-unfolding of a convex polyhedron. These paths have the property that the two sides of the cut avoid overlap locally as the cut is infinitesimally opened by the curvature at the vertices along the path. It is shown that a class of planar, triangulated convex domains always have a radially monotone spanning forest, a forest that can be found by an essentially greedy algorithm. This algorithm can be mimicked in 3D and applied to polyhedra inscribed in a sphere. Although the algorithm does not provably find a radially monotone cut tree, it in fact does find such a tree with high frequency, and after cutting unfolds without overlap. This performance of a greedy algorithm leads to the conjecture that spherical polyhedra always have a radially monotone cut tree and unfold without overlap.
0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv
Unfolding Genus-2 Orthogonal Polyhedra with Linear Refinement
We show that every orthogonal polyhedron of genus at most 2 can be unfolded without overlap while using only a linear number of orthogonal cuts (parallel to the polyhedron edges). This is the first result on unfolding general orthogonal polyhedra beyond genus-0. Our unfolding algorithm relies on the existence of at most 2 special leaves in what we call the "unfolding tree" (which ties back to the genus), so unfolding polyhedra of genus 3 and beyond requires new techniques.
0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv
Hypercube Unfoldings that Tile R^3 and R^2
We show that the hypercube has a face-unfolding that tiles space, and that unfolding has an edge-unfolding that tiles the plane. So the hypercube is a "dimension-descending tiler." We also show that the hypercube cross unfolding made famous by Dali tiles space, but we leave open the question of whether or not it has an edge-unfolding that tiles the plane.
0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv
On Flat Polyhedra deriving from Alexandrov's Theorem
We show that there is a straightforward algorithm to determine if the polyhedron guaranteed to exist by Alexandrov's gluing theorem is a degenerate flat polyhedron, and to reconstruct it from the gluing instructions. The algorithm runs in O(n^3) time for polygons whose gluings are specified by n labels.
0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv
Spiral Unfoldings of Convex Polyhedra
The notion of a spiral unfolding of a convex polyhedron, resulting by flattening a special type of Hamiltonian cut-path, is explored. The Platonic and Archimedian solids all have nonoverlapping spiral unfoldings, although among generic polyhedra, overlap is more the rule than the exception. The structure of spiral unfoldings is investigated, primarily by analyzing one particular class, the polyhedra of revolution.
0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv
Unfolding Smooth Prismatoids
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.
0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv
A 2-chain can interlock with an open 10-chain
It is an open problem, posed in \cite{SoCG}, to determine the minimal $k$ such that an open flexible $k$-chain can interlock with a flexible 2-chain. It was first established in \cite{GLOSZ} that there is an open 16-chain in a trapezoid frame that achieves interlocking. This was subsequently improved in \cite{GLOZ} to establish interlocking between a 2-chain and an open 11-chain. Here we improve that result once more, establishing interlocking between a 2-chain and a 10-chain. We present arguments that indicate that 10 is likely the minimum.
0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv
From Pop-Up Cards to Coffee-Cup Caustics: The Knight's Visor
As a pedagogical exercise, we derive the shape of a particularly elegant pop-up card design, and show that it connects to a classically studied plane curve that is (among other interpretations) a caustic of a circle.
0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv
Source Unfoldings of Convex Polyhedra via Certain Closed Curves
We extend the notion of a source unfolding of a convex polyhedron P to be based on a closed polygonal curve Q in a particular class rather than based on a point. The class requires that Q "lives on a cone" to both sides; it includes simple, closed quasigeodesics. Cutting a particular subset of the cut locus of Q (in P) leads to a non-overlapping unfolding of the polyhedron. This gives a new general method to unfold the surface of any convex polyhedron to a simple, planar polygon.
0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv
Unfolding Prismatoids as Convex Patches: Counterexamples and Positive Results
We address the unsolved problem of unfolding prismatoids in a new context, viewing a "topless prismatoid" as a convex patch---a polyhedral subset of the surface of a convex polyhedron homeomorphic to a disk. We show that several natural strategies for unfolding a prismatoid can fail, but obtain a positive result for "petal unfolding" topless prismatoids. We also show that the natural extension to a convex patch consisting of a face of a polyhedron and all its incident faces, does not always have a nonoverlapping petal unfolding. However, we obtain a positive result by excluding the problematical patches. This then leads a positive result for restricted prismatoids. Finally, we suggest suggest studying the unfolding of convex patches in general, and offer some possible lines of investigation.
0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv
Common Edge-Unzippings for Tetrahedra
It is shown that there are examples of distinct polyhedra, each with a Hamiltonian path of edges, which when cut, unfolds the surfaces to a common net. In particular, it is established for infinite classes of triples of tetrahedra.
0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv
Convex Polyhedra Realizing Given Face Areas
Given n >= 4 positive real numbers, we prove in this note that they are the face areas of a convex polyhedron if and only if the largest number is not more than the sum of the others.
0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv
A Note on Solid Coloring of Pure Simplicial Complexes
We establish a simple generalization of a known result in the plane. The simplices in any pure simplicial complex in R^d may be colored with d+1 colors so that no two simplices that share a (d-1)-facet have the same color. In R^2 this says that any planar map all of whose faces are triangles may be 3-colored, and in R^3 it says that tetrahedra in a collection may be "solid 4-colored" so that no two glued face-to-face receive the same color.
0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv
Flat Zipper-Unfolding Pairs for Platonic Solids
We show that four of the five Platonic solids' surfaces may be cut open with a Hamiltonian path along edges and unfolded to a polygonal net each of which can "zipper-refold" to a flat doubly covered parallelogram, forming a rather compact representation of the surface. Thus these regular polyhedra have particular flat "zipper pairs." No such zipper pair exists for a dodecahedron, whose Hamiltonian unfoldings are "zip-rigid." This report is primarily an inventory of the possibilities, and raises more questions than it answers.
0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv
On Folding a Polygon to a Polyhedron
We show that the open problem presented in "Geometric Folding Algorithms: Linkages, Origami, Polyhedra" [DO07] is solved by a theorem of Burago and Zalgaller [BZ96] from more than a decade earlier.
0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv
Pi/2-Angle Yao Graphs are Spanners
We show that the Yao graph Y4 in the L2 metric is a spanner with stretch factor 8(29+23sqrt(2)). Enroute to this, we also show that the Yao graph Y4 in the Linf metric is a planar spanner with stretch factor 8.
0 citations0 reviewsNo code linkedOpen access
preprint2008arXiv
Morphing of Triangular Meshes in Shape Space
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 $\mathcal{S}$. For triangulated 3D polygons, we prove that interpolating linearly in this shape space corresponds to the most isometric morph in $\mathbb{R}^3$. 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 approaches solve the morphing problem without the need to solve a minimization problem.
0 citations0 reviewsNo code linkedOpen access
preprint2001arXiv
Vertex-Unfoldings of Simplicial Polyhedra
We present two algorithms for unfolding the surface of any polyhedron, all of whose faces are triangles, to a nonoverlapping, connected planar layout. The surface is cut only along polyhedron edges. The layout is connected, but it may have a disconnected interior: the triangles are connected at vertices, but not necessarily joined along edges.
0 citations0 reviewsNo code linkedOpen access