On unfolding trees and polygons on various lattices

S.H. Poon

On unfolding trees and polygons on various lattices

S.H. Poon

Algorithms

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/Congresprocedure › Conferentiebijdrage › Academic › peer review

Samenvatting

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.

Originele taal-2	Engels
Titel	Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG 2007) 20-22 August 2007, Ottawa, Canada
Redacteuren	P. Bose
Uitgeverij	The CCCG Library
Pagina's	69-72
ISBN van geprinte versie	978-0-7709-0520-0
Status	Gepubliceerd - 2007
Evenement	conference; CCCG 2007, Ottawa, Canada; 2007-08-20; 2007-08-22 - Duur: 20 aug. 2007 → 22 aug. 2007

Congres

Congres	conference; CCCG 2007, Ottawa, Canada; 2007-08-20; 2007-08-22
Periode	20/08/07 → 22/08/07
Ander	CCCG 2007, Ottawa, Canada

Citeer dit

@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

Samenvatting

Congres

Vingerafdruk

Citeer dit