On unfolding 3D lattice polygons and 2D orthogonal trees

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

2 Citations (Scopus)

Abstract

We consider the problems of unfolding 3D lattice polygons embedded on the surface of some classes of lattice polyhedra, and of unfolding 2D orthogonal trees. During the unfolding process, all graph edges are preserved and no edge crossings are allowed. Let n be the number of edges of the given polygon or tree. We show that a lattice polygon embedded on an open lattice orthotube can be convexified in O(n) moves and time, and a lattice polygon embedded on a lattice Tower of Hanoi, a lattice Manhattan Tower, or an orthogonally-convex lattice polyhedron can be convexified in O(n2) moves and time. The main technique in our algorithms is to fold up the lattice polygon from the end blocks of the given lattice polyhedron. On the other hand, we show that a 2-monotone orthogonal tree on the plane can be straightened in O(n2) moves and time. We hope that our results shed some light on solving the more general conjectures, which we proposed, that a 3D lattice polygon embedded on any lattice polyhedron can always be convexified, and any 2D orthogonal tree can always be straightened.

Original languageEnglish
Title of host publicationComputing and Combinatorics - 14th Annual International Conference, COCOON 2008, Proceedings
Pages374-384
Number of pages11
DOIs
Publication statusPublished - 2008
Externally publishedYes
Event14th Annual International Conference on Computing and Combinatorics, COCOON 2008 - Dalian, China
Duration: 27 Jun 200829 Jun 2008

Publication series

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

Conference

Conference14th Annual International Conference on Computing and Combinatorics, COCOON 2008
Country/TerritoryChina
CityDalian
Period27/06/0829/06/08

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science (all)

Fingerprint

Dive into the research topics of 'On unfolding 3D lattice polygons and 2D orthogonal trees'. Together they form a unique fingerprint.

Cite this