dc.contributor.author |
Monroy, RF |
|
dc.contributor.author |
Urrutia, J |
|
dc.date.accessioned |
2011-01-22T10:26:35Z |
|
dc.date.available |
2011-01-22T10:26:35Z |
|
dc.date.issued |
2005 |
|
dc.identifier.issn |
0020-0190 |
|
dc.identifier.uri |
http://hdl.handle.net/11154/1493 |
|
dc.description.abstract |
Let P be a point set with n elements in general position. A triangulation T of P is a set of triangles with disjoint interiors such that their union is the convex hull of P, no triangle contains an element of P in its interior, and the vertices of the triangles of T are points of P. Given T we define a graph G(T) whose vertices are the triangles of T, two of which are adjacent if they share an edge. We say that T is hamiltonean if G(T) has a hamiltonean path. We prove that the triangulations produced by Graham's Scan are hamiltonean. Furthermore we prove that any triangulation T of a point set which has a point adjacent to all the points in P (a center of T) is hamiltonean. (C) 2004 Elsevier B.V. All rights reserved. |
en_US |
dc.language.iso |
en |
en_US |
dc.title |
Graham triangulations and triangulations with a center are hamiltonean |
en_US |
dc.type |
Article |
en_US |
dc.identifier.idprometeo |
1665 |
|
dc.identifier.doi |
10.1016/j.ipl.2004.12.001 |
|
dc.source.novolpages |
93(6):295-299 |
|
dc.subject.wos |
Computer Science, Information Systems |
|
dc.description.index |
WoS: SCI, SSCI o AHCI |
|
dc.subject.keywords |
algorithms |
|
dc.subject.keywords |
Graham's scan |
|
dc.subject.keywords |
triangulation |
|
dc.subject.keywords |
hamiltonean |
|
dc.subject.keywords |
point sets |
|
dc.relation.journal |
Information Processing Letters |
|