From:           "Thomas A. McGlynn" <tam@silk.gsfc.nasa.gov>
Date:           Tue, 11 Feb 1997 17:26:13 -0500
Newsgroups:     sci.math
Subject:        Delauney triangulation and points of intersections of lines

I've been building a method for resample pixel data which uses
the Delauney triangulation of a set of points, but I have
not been able to prove that it will work properly in a
general case and I'd be interested if anyone could point
me to appropriate references.

The Delauney triangulation (i.e., the creation of triangular tiles
with vertices at each of the points which cover the region in
which the points are contained) has the property that
the circumscribing circle for each triangle contains no
other vertices of the triangulation within it.  It's frequently
used to do interpolations of irregularly sampled data, but
that's not my interest.  

Suppose I have a Deluaney triangulation, T, of
the set of points which comprise all the intersections between
a set, L, of lines.  T is a set of triangular tiles.
What I need to show is that there is no triangle in T
which is crossed by any of the lines L.

Empirically I've found this to be true for the cases
that I use, but I'm not clear how I'd prove
it generally -- or if it is not true generally, whether
there are any restrictions I can place on L to ensure
that it is true.

If anyone has any comments or can point me to appropriate 
references I'd be very grateful.

			Yours,

			Tom McGlynn
			tam@silk.gsfc.nasa.gov

From:           Hans Kristian Ruud <hkr@ifi.uio.no>
Date:           19 Feb 1997 15:34:48 +0100
Newsgroups:     sci.math
Subject:        Re: Delauney triangulation and points of intersections of lines

> Suppose I have a Deluaney triangulation, T, of                          
> the set of points which comprise all the intersections between          
> a set, L, of lines.  T is a set of triangular tiles.                    
> What I need to show is that there is no triangle in T                   
> which is crossed by any of the lines L. 

Well, I managed to come up with the following counterexample:
draw 4 lines forming an elongated diamond, such that their
intersection points are ABCD.

                 A

            B         C

                 D                 

Then draw a new line EF:

                 A
                  E

            B         C

                F
                 D

The triangles BFC and BCE will belong to the
Delauney triangulation, yet the line EF will
intersect them.                          
              

--
* Hans Kr. Ruud						The noble art    *
* Kristine Bonnevies vei 15				of losing face   *
* 0592 ÅRVOLL						may one day save *
* Tlf. 22 65 22 34 (hjemme) 22 77 05 35 (jobb)  	the human race   *