trees inside delaunay triangulation

[Stephen Vavasis]

Dear colleagues,

I have the following conjecture based on trying some examples.  I'm wondering if anyone knows whether it is true.

Conjecture.  Let S be a set of n points in general position in the plane.  Let T be the Delaunay triangulation of these points.  Then there exists a subset T_1,...,T_{n-2} of n-2 triangles from T such that
 (1) These triangles form a tree in the dual graph of the Delaunay triangulation
and
 (2) Every one of the n original points is adjacent to at least one of the n-2 triangles.

Remark 1.  This conjecture is obviously true if the n points are in convex position, since in this case the DT has exact n-2 triangles and they form a tree.

Remark 2.  The assumption of general position is necessary, since I thought of a counterexample for points not in general position.  Specifically, consider a 3-by-3 evenly spaced rectangular lattice of nine points.  There are many DT's for these points, but select the one in which the central point is adjacent to only four edges.  This triangulation does not have the conjectured subtree.

Thanks,
Steve Vavasis

-------------
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.