On unfolding trees and polygons on various lattices

S.H. Poon

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

Abstract

We consider the problem of unfolding lattice trees and polygons in hexagonal or triangular lattice in two dimensions. We show that a hexagonal/triangular lattice chain (resp. tree) can be straightened in O(n) (resp. O(n2)) moves and time, and a hexagonal/triangular lattice polygon can be convexified in O(n2) moves and time. We hope that the techniques we used shed some light on solving the more general conjecture that a unit tree in two dimensions can always be straightened.
Original languageEnglish
Title of host publicationProceedings of the 19th Canadian Conference on Computational Geometry (CCCG 2007) 20-22 August 2007, Ottawa, Canada
EditorsP. Bose
PublisherThe CCCG Library
Pages69-72
ISBN (Print)978-0-7709-0520-0
Publication statusPublished - 2007
Eventconference; CCCG 2007, Ottawa, Canada; 2007-08-20; 2007-08-22 -
Duration: 20 Aug 200722 Aug 2007

Conference

Conferenceconference; CCCG 2007, Ottawa, Canada; 2007-08-20; 2007-08-22
Period20/08/0722/08/07
OtherCCCG 2007, Ottawa, Canada

Fingerprint Dive into the research topics of 'On unfolding trees and polygons on various lattices'. Together they form a unique fingerprint.

Cite this