On unfolding trees and polygons on various lattices

S.H. Poon

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review


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-2Engels
TitelProceedings of the 19th Canadian Conference on Computational Geometry (CCCG 2007) 20-22 August 2007, Ottawa, Canada
RedacteurenP. Bose
UitgeverijThe CCCG Library
ISBN van geprinte versie978-0-7709-0520-0
StatusGepubliceerd - 2007
Evenementconference; CCCG 2007, Ottawa, Canada; 2007-08-20; 2007-08-22 -
Duur: 20 aug. 200722 aug. 2007


Congresconference; CCCG 2007, Ottawa, Canada; 2007-08-20; 2007-08-22
AnderCCCG 2007, Ottawa, Canada


Duik in de onderzoeksthema's van 'On unfolding trees and polygons on various lattices'. Samen vormen ze een unieke vingerafdruk.

Citeer dit