On unfolding trees and polygons on various lattices

Sheung Hung Poon

On unfolding trees and polygons on various lattices

Sheung Hung Poon

Research output: Contribution to conference › Paper › peer-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(n²)) moves and time, and a hexagonal/triangular lattice polygon can be convexified in O(n²) 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 language	English
Pages	69-72
Number of pages	4
Publication status	Published - 2007
Externally published	Yes
Event	19th Annual Canadian Conference on Computational Geometry, CCCG 2007 - Ottawa, ON, Canada Duration: 20 Aug 2007 → 22 Aug 2007

Conference

Conference	19th Annual Canadian Conference on Computational Geometry, CCCG 2007
Country/Territory	Canada
City	Ottawa, ON
Period	20/08/07 → 22/08/07

ASJC Scopus subject areas

Geometry and Topology

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

Cite this

@conference{a8cbe6a5a3cf4f55bf6770b38551c377,

title = "On unfolding trees and polygons on various lattices",

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.",

author = "Poon, {Sheung Hung}",

year = "2007",

language = "English",

pages = "69--72",

note = "19th Annual Canadian Conference on Computational Geometry, CCCG 2007 ; Conference date: 20-08-2007 Through 22-08-2007",

}

TY - CONF

T1 - On unfolding trees and polygons on various lattices

AU - Poon, Sheung Hung

PY - 2007

Y1 - 2007

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84893426757&partnerID=8YFLogxK

M3 - Paper

AN - SCOPUS:84893426757

SP - 69

EP - 72

T2 - 19th Annual Canadian Conference on Computational Geometry, CCCG 2007

Y2 - 20 August 2007 through 22 August 2007

ER -

On unfolding trees and polygons on various lattices

Abstract

Conference

ASJC Scopus subject areas

UN SDGs

Other files and links

Fingerprint

Cite this