On edge-unfolding one-layer lattice polyhedra with cubic holes

Meng Huan Liou, Sheung Hung Poon, Yu Jie Wei

Research output: Chapter in Book/Conference proceedingConference contributionpeer-review

8 Citations (Scopus)

Abstract

An edge-unfolding of a polyhedron is a cutting of the polyhedron's surface along its edges so that its surface can be flattened into a single connected flat patch on the plane without any self-overlapping. A one-layer lattice polyhedron is a polyhedron of height one, whose surface faces are grid squares. We consider the edge-unfolding problem on several classes of one-layer lattice polyhedra with cubic holes. We propose linear-time algorithms for one-layer lattice polyhedra with rectangular external boundary and cubic holes, one-layer lattice polyhedra with cubic holes strictly enclosed by an orthogonally convex polygon, and one-layer lattice polyhedra with sparse cubic holes, respectively. The algorithms use two different novel techniques to cut the edges of cubic holes of the given polyhedron so that no self-overlapping can occur in the flattened patch. Our algorithms are the first algorithms especially designed to edge-unfold a polyhedron of genus greater than zero to a single connected flattened patch. We leave open the question whether any of these edge-cutting methods can be extended to edge-unfold general one-layer lattice polyhedra with cubic holes.

Original languageEnglish
Title of host publicationComputing and Combinatorics - 20th International Conference, COCOON 2014, Proceedings
PublisherSpringer Verlag
Pages251-262
Number of pages12
ISBN (Print)9783319087825
DOIs
Publication statusPublished - 2014
Externally publishedYes
Event20th International Computing and Combinatorics Conference, COCOON 2014 - Atlanta, GA, United States
Duration: 4 Aug 20146 Aug 2014

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8591 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference20th International Computing and Combinatorics Conference, COCOON 2014
Country/TerritoryUnited States
CityAtlanta, GA
Period4/08/146/08/14

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science (all)

Fingerprint

Dive into the research topics of 'On edge-unfolding one-layer lattice polyhedra with cubic holes'. Together they form a unique fingerprint.

Cite this