trees inside delaunay triangulation

[Joseph O'Rourke]

On Wed, 17 Dec 2003, Raimund Seidel wrote:

> If I am not mistaken, then this is not true in general.
> If it were true, the boundary of the tree triangles would
> form a hamiltonian circuit.
> If I remember correctly Mike Dillencourt showed that there
> are Delaunay triangulations that are not Hamiltonian.


Raimund is correct.  I raised this question in an old paper,
and Dillencourt resolved it negatively.  References below.  :-j

@article{obw-cdnh-87
, author =      "J. O'Rourke and H. Booth and R. Washington"
, title =       "Connect-the-dots: {A} new heuristic"
, journal =     "Comput. Vision Graph. Image Process."
, volume =      39
, year =        1987
, pages =       "258--266"
, keywords =    "pattern recognition, Delaunay triangulations, Hamiltonian 
cycles
"
}

@article{d-nhndt-87
, author =      "M. B. Dillencourt"
, title =       "A non-{Hamiltonian}, nondegenerate {Delaunay} 
triangulation"
, journal =     "Inform. Process. Lett."
, volume =      25
, year =        1987
, pages =       "149--151"
}



-------------
The compgeom mailing lists: see
http://netlib.bell-labs.com/netlib/compgeom/readme.html
or send mail to compgeom-request at research.bell-labs.com with the line:
send readme
Now archived at http://www.uiuc.edu/~sariel/CG/compgeom/maillist.html.