On unfolding lattice polygons/trees and diameter-4 trees

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

4 Citations (Scopus)

Abstract

We consider the problems of straightening polygonal trees and convexifying polygons by continuous motions such that rigid edges can rotate around vertex joints and no edge crossings are allowed. A tree can be straightened if all its edges can be aligned along a common straight line such that each edge points "away" from a designated leaf node. A polygon can be convexified if it can be reconfigured to a convex polygon. A lattice tree (resp. polygon) is a tree (resp. polygon) containing only edges from a square or cubic lattice. We first show that a 2D lattice chain or a 3D lattice tree can be straightened efficiently in O(n) moves and time, where n is the number of tree edges. We then show that a 2D lattice tree can be straightened efficiently in O(n2) moves and time. Furthermore, we prove that a 2D lattice polygon or a 3D lattice polygon with simple shadow can be convexified efficiently in O(n2) moves and time. Finally, we show that two special classes of diameter-4 trees in two dimensions can always be straightened.

Original languageEnglish
Title of host publicationComputing and Combinatorics - 12th Annual International Conference, COCOON 2006, Proceedings
PublisherSpringer Verlag
Pages186-195
Number of pages10
ISBN (Print)3540369252, 9783540369257
DOIs
Publication statusPublished - 2006
Externally publishedYes
Event12th Annual International Conference on Computing and Combinatorics, COCOON 2006 - Taipei, Taiwan, Province of China
Duration: 15 Aug 200618 Aug 2006

Publication series

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

Conference

Conference12th Annual International Conference on Computing and Combinatorics, COCOON 2006
Country/TerritoryTaiwan, Province of China
CityTaipei
Period15/08/0618/08/06

Keywords

  • Comput. geom
  • Convexifying
  • Straightening
  • Unfolding

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science (all)

Fingerprint

Dive into the research topics of 'On unfolding lattice polygons/trees and diameter-4 trees'. Together they form a unique fingerprint.

Cite this