On unfolding trees and polygons on various lattices

S.H. Poon

On unfolding trees and polygons on various lattices

S.H. Poon

Algorithms

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › 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(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 language	English
Title of host publication	Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG 2007) 20-22 August 2007, Ottawa, Canada
Editors	P. Bose
Publisher	The CCCG Library
Pages	69-72
ISBN (Print)	978-0-7709-0520-0
Publication status	Published - 2007
Event	conference; CCCG 2007, Ottawa, Canada; 2007-08-20; 2007-08-22 - Duration: 20 Aug 2007 → 22 Aug 2007

Conference

Conference	conference; CCCG 2007, Ottawa, Canada; 2007-08-20; 2007-08-22
Period	20/08/07 → 22/08/07
Other	CCCG 2007, Ottawa, Canada

Cite this

@inproceedings{f79d11f950664d41b7d345cc7e082a63,

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 = "S.H. Poon",

year = "2007",

language = "English",

isbn = "978-0-7709-0520-0",

pages = "69--72",

editor = "P. Bose",

booktitle = "Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG 2007) 20-22 August 2007, Ottawa, Canada",

publisher = "The CCCG Library",

note = "conference; CCCG 2007, Ottawa, Canada; 2007-08-20; 2007-08-22 ; Conference date: 20-08-2007 Through 22-08-2007",

}

TY - GEN

T1 - On unfolding trees and polygons on various lattices

AU - Poon, S.H.

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.

M3 - Conference contribution

SN - 978-0-7709-0520-0

SP - 69

EP - 72

BT - Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG 2007) 20-22 August 2007, Ottawa, Canada

A2 - Bose, P.

PB - The CCCG Library

T2 - conference; CCCG 2007, Ottawa, Canada; 2007-08-20; 2007-08-22

Y2 - 20 August 2007 through 22 August 2007

ER -

On unfolding trees and polygons on various lattices

Abstract

Conference

Fingerprint

Cite this