DROPS

Document

DOI: 10.4230/LIPIcs.FUN.2022.6

Rolling Polyhedra on Tessellations

Authors: Akira Baes, Erik D. Demaine, Martin L. Demaine, Elizabeth Hartung, Stefan Langerman, Joseph O'Rourke, Ryuhei Uehara, Yushi Uno, and Aaron Williams

Published in: LIPIcs, Volume 226, 11th International Conference on Fun with Algorithms (FUN 2022)

Abstract

We study the space reachable by rolling a 3D convex polyhedron on a 2D periodic tessellation in the xy-plane, where at every step a face of the polyhedron must coincide exactly with a tile of the tessellation it rests upon, and the polyhedron rotates around one of the incident edges of that face until the neighboring face hits the xy plane. If the whole plane can be reached by a sequence of such rolls, we call the polyhedron a plane roller for the given tessellation. We further classify polyhedra that reach a constant fraction of the plane, an infinite area but vanishing fraction of the plane, or a bounded area as hollow-plane rollers, band rollers, and bounded rollers respectively. We present a polynomial-time algorithm to determine the set of tiles in a given periodic tessellation reachable by a given polyhedron from a given starting position, which in particular determines the roller type of the polyhedron and tessellation. Using this algorithm, we compute the reachability for every regular-faced convex polyhedron on every regular-tiled (≤ 4)-uniform tessellation.

Cite as

Akira Baes, Erik D. Demaine, Martin L. Demaine, Elizabeth Hartung, Stefan Langerman, Joseph O'Rourke, Ryuhei Uehara, Yushi Uno, and Aaron Williams. Rolling Polyhedra on Tessellations. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 6:1-6:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{baes_et_al:LIPIcs.FUN.2022.6,
  author =	{Baes, Akira and Demaine, Erik D. and Demaine, Martin L. and Hartung, Elizabeth and Langerman, Stefan and O'Rourke, Joseph and Uehara, Ryuhei and Uno, Yushi and Williams, Aaron},
  title =	{{Rolling Polyhedra on Tessellations}},
  booktitle =	{11th International Conference on Fun with Algorithms (FUN 2022)},
  pages =	{6:1--6:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-232-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{226},
  editor =	{Fraigniaud, Pierre and Uno, Yushi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.6},
  URN =		{urn:nbn:de:0030-drops-159761},
  doi =		{10.4230/LIPIcs.FUN.2022.6},
  annote =	{Keywords: polyhedra, tilings}
}

Document

DOI: 10.4230/LIPIcs.SoCG.2018.64

Edge-Unfolding Nearly Flat Convex Caps

Authors: Joseph O'Rourke

Published in: LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018)

Abstract

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 f < F with the z^-axis orthogonal to the halfspace bounding plane. The size of F depends on the acuteness gap a: if every triangle angle is at most pi/2 {-} a, then F ~~ 0.36 sqrt{a} suffices; e.g., for a=3°, F ~~ 5°. 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.

Cite as

Joseph O'Rourke. Edge-Unfolding Nearly Flat Convex Caps. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 64:1-64:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{orourke:LIPIcs.SoCG.2018.64,
  author =	{O'Rourke, Joseph},
  title =	{{Edge-Unfolding Nearly Flat Convex Caps}},
  booktitle =	{34th International Symposium on Computational Geometry (SoCG 2018)},
  pages =	{64:1--64:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-066-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{99},
  editor =	{Speckmann, Bettina and T\'{o}th, Csaba D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.64},
  URN =		{urn:nbn:de:0030-drops-87777},
  doi =		{10.4230/LIPIcs.SoCG.2018.64},
  annote =	{Keywords: polyhedra, unfolding}
}

Document

DOI: 10.4230/LIPIcs.STACS.2008.1345

Connecting Polygonizations via Stretches and Twangs

Authors: Mirela Damian, Robin Flatland, Joseph O'Rourke, and Suneeta Ramaswani

Published in: LIPIcs, Volume 1, 25th International Symposium on Theoretical Aspects of Computer Science (2008)

Abstract

We show that the space of polygonizations of a fixed planar point set $S$ of $n$ points is connected by $O(n^2)$ ``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.

Cite as

Mirela Damian, Robin Flatland, Joseph O'Rourke, and Suneeta Ramaswani. Connecting Polygonizations via Stretches and Twangs. In 25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 1, pp. 217-228, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{damian_et_al:LIPIcs.STACS.2008.1345,
  author =	{Damian, Mirela and Flatland, Robin and O'Rourke, Joseph and Ramaswani, Suneeta},
  title =	{{Connecting Polygonizations via Stretches and Twangs}},
  booktitle =	{25th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{217--228},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-06-4},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{1},
  editor =	{Albers, Susanne and Weil, Pascal},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2008.1345},
  URN =		{urn:nbn:de:0030-drops-13457},
  doi =		{10.4230/LIPIcs.STACS.2008.1345},
  annote =	{Keywords: Polygons, polygonization, random polygons, connected configuration space}
}

Search Results

Documents authored by O'Rourke, Joseph

Rolling Polyhedra on Tessellations

Abstract

Cite as

Edge-Unfolding Nearly Flat Convex Caps

Abstract

Cite as

Connecting Polygonizations via Stretches and Twangs

Abstract

Cite as

Thanks for your feedback!

Could not send message