On unfolding trees and polygons on various lattices

Sheung Hung Poon

Research output: Contribution to conferencePaperpeer-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
Pages69-72
Number of pages4
Publication statusPublished - 2007
Externally publishedYes
Event19th Annual Canadian Conference on Computational Geometry, CCCG 2007 - Ottawa, ON, Canada
Duration: 20 Aug 200722 Aug 2007

Conference

Conference19th Annual Canadian Conference on Computational Geometry, CCCG 2007
Country/TerritoryCanada
CityOttawa, ON
Period20/08/0722/08/07

ASJC Scopus subject areas

  • Geometry and Topology

Fingerprint

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

Cite this